解釋理論計算機科學（TOC）中的通用圖靈機

圖靈機 (TM) 相當於數字計算機的機器級別。

它是由數學家圖靈在1930年提出的，並且已成為可計算性和複雜性理論中最廣泛使用的計算模型。

該模型由輸入和輸出組成。輸入以二進位制格式提供到機器的磁帶上，輸出包括機器停止時磁帶的內容。

圖靈機的缺點是，必須為每個要執行的新計算（針對每個輸入輸出關係）構建不同的機器。

這就是引入通用圖靈機的原因，它除了磁帶上的輸入外，還包含機器 M 的描述。

通用圖靈機可以繼續模擬 M 對輸入磁帶其餘內容的操作。

因此，通用圖靈機可以模擬任何其他機器。

連線多個圖靈機的想法給了圖靈一個想法——

• 能否建立一個可以“模擬”其他機器的通用機器？

• 這臺機器被稱為通用圖靈機。

這臺機器將為它模擬的機器提供三條資訊：

• 機器的基本描述。
• 機器磁帶的內容。
• 機器的內部狀態。

通用機器將透過檢視磁帶上的輸入和機器的狀態來模擬機器。

它將透過根據輸入更改其狀態來控制機器。這導致了“計算機執行另一臺計算機”的想法。

它將透過根據輸入更改其狀態來控制機器。這導致了“計算機執行另一臺計算機”的想法。

通用圖靈機的示意圖如下：

Bhanu Priya

更新於：2023年10月31日

57K+ 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始