資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究解釋圖靈機的基本特性？
圖靈機比有限自動機 (FA) 和下推自動機 (PDA) 都更強大。它們與我們構建的任何計算機一樣強大。
圖靈機相較於 PDA 的主要改進如下所示：
無限“全部”可訪問記憶體（以磁帶的形式）——可以選擇讀取和寫入。
讀寫頭可以在輸入磁帶上向左和向右移動（或不改變位置）。
圖靈機的工作原理是：一個無限的磁帶被分成單元格（雙向無限），每個單元格包含字母表中的一個符號或空白符號。（磁帶上只寫有限數量的非空白符號。）
圖靈機始終處於有限數量的狀態之一。
讀寫頭讀取“當前單元格”中的符號，並根據符號和當前狀態：
更改狀態
向任一方向移動磁頭或不移動
重寫“當前符號”或保持不變
預設情況下，我們討論的是確定性圖靈機。
在磁帶上移動
在每個步驟中，磁頭有三種可能的移動方式，如下所示：
“從當前單元格向左移動一個單元格”，
“停留在當前單元格”，或
“向右移動一個單元格”，
我們將用字母 L、S 和 R 表示它們。
圖靈機指令（轉移函式）
每個圖靈機 (TM) 指令包含五個部分：
輸入 - 當前機器狀態。（來自 Q）
輸入 - 從當前磁帶單元格讀取的磁帶符號（可能是空白符號）（來自 Γ）
輸出 - 要寫入當前磁帶單元格的磁帶符號（可能是空白符號或其他符號）（來自 Γ）
輸出 - 下一個機器狀態（來自 Q）
輸出 - 磁頭移動的方向 {L, R, S}。
T : Q × Γ → Γ × Q × {L, R, S}
兩個輸入，三個輸出：T(i, a) = (b, j, R)
Γ 包含 ∑（語言的字母表）、“空磁帶符號”–，但也包含其他符號。
指令的圖形形式如下所示：
這與之前的意思相同：
如果機器的當前狀態為 i，並且如果當前磁帶單元格中的符號為 a，
↓
然後，將 b 寫入當前磁帶單元格，向左移動一個單元格，並轉到狀態 j。
輸入字串在磁帶上表示為將字串的字母（來自 ∑）放置到相鄰的磁帶單元格中。
磁帶的所有其他單元格都包含空白符號，我們將其表示為 。
磁頭通常位於輸入字串的最左側單元格（最左側的非空白磁帶符號）上。
3K+ 瀏覽量
