資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究請給出圖靈機的實現級描述？
圖靈機（TM）可以形式化地描述為七元組 -
(Q,X,∑,δ,q0,B,F)
其中，
Q 是狀態的有限集合。
X 是帶字母表。
∑ 是輸入字母表。
δ 是轉移函式：δ𝛿:QxX->QxXx{左移，右移}。
q0 是初始狀態。
B 是空白符號。
F 是最終狀態。
圖靈機 T 識別字符串 x（在 ∑ 上）當且僅當 T 從初始位置開始，x 寫在磁帶上，
T 在最終狀態下停止。
如果 x 被 T 識別，當且僅當 x 屬於 A，則稱 T 識別語言 A。
請注意，在執行 TM 時，您還可以從磁帶上讀/寫其他符號，而不僅僅是字母表 A 中的符號。
如果 T 沒有在非最終狀態下停止，則圖靈機 T 不會識別字符串 x。
有一些 TM 對於某個輸入根本不會停止，並且會永遠執行。
示例 1
實現級描述一個圖靈機，該圖靈機確定在字母表 {0, 1} 上的以下語言。
{w|w 包含相同數量的 0 和 1}
M = “在輸入字串 w 上 -
掃描磁帶並標記第一個尚未標記的 0。如果未找到未標記的 0，則轉到步驟 4。否則，將磁頭移回磁帶的開頭。
掃描磁帶並標記第一個尚未標記的 1。如果未找到未標記的 1，則拒絕。
將磁頭移回磁帶的開頭，然後轉到步驟 1。
將磁頭移回磁帶的開頭。掃描磁帶以檢視是否仍有未標記的 1 存在。如果未找到，則接受；否則，拒絕。”
示例 2
給出 TM 的高階描述，該 TM 接受語言 A，其中 A 包含所有表示無向圖連通的字串。
A = {<G>|G 是一個連通的無向圖}
A = {<G>|G 是一個連通的無向圖}
M = “在輸入字串 <G> 上 -
選擇 G 的第一個節點並標記它。
重複以下步驟，直到沒有新的節點被標記 -
對於 G 中的每個節點，如果它透過邊連線到已標記的節點，則標記它。
掃描 G 的所有節點以確定它們是否都已標記。如果它們都已標記，則接受；否則，拒絕。”
3K+ 瀏覽量
