圖靈機MOD功能

Question

誰能explaine我怎麼做圖靈機爲以下：

Y = X模3，其中（X，Y）與最小的時間複雜度二進制數10

Answer 1

我做到了。

這裏是工作機器）

Answer 2

好吧，你理解了算法，現在我們必須建立機器。

我們將與數111010（58）開始，由左到右，與機頭開始向左閱讀。有兩種模式：向右掃描以查看內容，並在重寫時移動到左側。

| 
v 
x111010m 
abcdefgh 

（我已經爲我們的談話標記了位置a-h）機器應該做什麼？

在圖靈機，一個國家有一些規則，使機器可以決定由符號它看到的事情。狀態A的規則可能如下所示：
「如果我看到符號x，我將擦除它並寫入符號v，向左移動一步並進入狀態B.」
「如果我看到符號y，我會不受干擾地向右移動一步並進入狀態D.」
「如果我看到符號w，我會清除它並寫入符號z，向左移動一步進入狀態A（保持此狀態）。」

一般來說，它掃描到右邊，以發現數量是否開始於11，100或101。這涉及兩個不同的狀態。然後它移動到左側，重寫11-> xx，100-> xx1,101-> x10。這涉及幾個州。 （a）在狀態1中，讀取x，使其不受干擾，向右移動，保持狀態1.（查找1）
（b）在狀態1中，讀取1，使其不受干擾，向右移動，轉到狀態2.（接下來是什麼？）
（c）在狀態2中，讀取1,寫入x，向左移動，進入狀態3（必須重寫這個符號爲x和前一個爲x）
（b）在狀態3，讀1，寫X，向右移動，進入狀態1（再次尋找1 ）

（如果你很聰明，你可以不用狀態3，但讓我們的機器第一個工作日）。

所以，我可以寫一些像這樣的規則：

1 x x right 1 
1 1 1 right 2 
2 1 x left 3 
3 1 x right 1 

你必須寫夠了規則機器總是知道該怎麼做，如果你想在機器停止（是的！）必須有一個規則 - 或者許多規則 - 就像這樣：

5 m m right halt 

這是否足以讓你站起來rted？