構建一個圖靈機來將二進位制自然數加2？

圖靈機(TM)可以形式化地描述為七元組：

(Q,X, ∑, δ,q0,B,F)

其中：

• Q 是有限狀態集。

• X 是帶字母表。

• ∑ 是輸入字母表。

• δ 是轉移函式：δ:QxX->QxXx{左移，右移}。

• q0 是初始狀態。

• B 是空白符號。

• F 是最終狀態。

輸入 - n 一個自然數

輸出 - n + 2

讓我們用一元形式表示自然數（例如，3 = 111，5 = 11111），0用空符號表示。

演算法

將磁帶頭移動到第一個1的左側（如果存在）。

將該空單元格更改為1。

左移並重復。

停止

我們只需要3個狀態：0（初始）、1和停止；以及三個指令：

(1): (0, 1, 1, L, 0) 向左移動到空白單元格。

(2): (0, , 1, L, 1) 在單元格中寫入1並向左移動。

(3): (1, ❑, 1, S, 停止) 在單元格中寫入1並停止。

圖形化表示如下

瞬時描述

狀態 0：❑ 1 1 1 ❑ 從狀態 0 開始

狀態 0：❑ 1 1 1 ❑ (1)

狀態 1：❑ 1 1 1 1 ❑ (2)

停止：❑ 1 1 1 1 1 ❑ (3)

Bhanu Priya

更新於：2021年6月16日

702 次瀏覽

啟動你的職業生涯

透過完成課程獲得認證

開始