資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究設計用於乘法的圖靈機
圖靈機是一個七元組
(Q, Σ, Γ, δ, q0, qacc, qrej)
其中，
Q 是一個有限的狀態集；
Σ 是輸入字母表，不包含空格符號 t；
Γ 是帶字母表，其中 t ∈ Γ 且 Σ ⊆ Γ；
δ: (Q × Γ) → (Q × Γ × {L, R}) 是轉移函式；
q0 ∈ Q 是起始狀態；
qacc ∈ Q 是接受狀態；
qrej ∈ Q 是拒絕狀態，其中 qrej ≠ qacc。
問題
構建用於兩個一元整數相乘的圖靈機 (TM)。
解決方案
Multiplication of two unary integers 3*2=6 In Turing Machine 3 represents − 111 2 represents − 11
令 ‘M’ 為用於分隔兩個整數的符號
| B | 1 | 1 | 1 | M | 1 | 1 | B |
這裡 B= 空格
M= 用於分隔兩個整數的符號
⇑= 磁頭
執行乘法後，輸出如下：
| B | 1 | 1 | 1 | 1 | 1 | 1 | B |
乘法的 TM 如下所示：
解釋
q0 - 查詢輸入中的第一個未使用的符號。
q0 - 查詢輸入中的第一個未使用的符號。
q1 - 在第一個因子中找到一個 1；跳到 x 符號
q2 - 找到 x
q4 - 在第二個因子中找到一個 1；將其更改為 Y；跳到 =
q3 - 使用了第二個因子中的所有 1；將 Y 轉換回 1
q5 - 跳到磁帶末尾
q6 - 跳回 =
q7 - 跳回第二個因子
q8 - 找到 Y，標記第二個因子中先前使用的 1
q9 - 跳回第一個因子中的 1
q12 - 消耗了整個第一個因子；將 x 轉換回 1
q11 - 找到 ⊔
更新於： 2021年6月14日
10K+ 次觀看
廣告