如何創建一個圖靈機，作爲功能計算器爲x^y

Question

我正在學習圖靈機的測試，我堅持一個問題，我必須創建一個圖靈機，作爲對於函數計算器：

f(x,y) = x^y 

我明白我的磁帶輸入會來分隔這樣的：

1's of base 0 1's of exponent 

隨着我的磁帶輸出是一樣

1's of base 0 1's of exponent 0 1's of the computed result 

我會如何將X和Y放在磁帶上？ （它可以是多磁帶機） 狀態圖是什麼樣的？

注意：我使用1代表1和0代表0和0，它們不是用作值而是用作分隔符。

所以：

0 = delimiter 
    1 = 0 
    11 = 1 
    111 = 2 
    1111= 3 
    11111= 4 
    etc. 

Answer 1

我在這裏猜測一下，它是一段時間，因爲我與圖靈機模擬器玩了一點點。首先，我會想起來劃分任務分成幾個概念上的步驟：

1. 增量由另一個數字磁帶
2. 的價值磁帶的數量由值乘以磁帶上的數 - 可以通過重複執行步驟1來完成此操作
3. 正方形磁帶上的一個數字-x^2通過將x放在磁帶上然後將其自身相乘來計算
4. （最後一步）將磁帶上的數字提高到磁帶上另一個數字的值 - 這可以通過重複執行步驟2來完成

要重複執行N次任務，請將N放到磁帶上，執行一次任務，然後從數字N的末尾減去1。重複直到數字N從磁帶中消失。

希望這足以讓你無論如何開始。狀態機可以用這種方式或多或少機械地構建。

Answer 2

在我自己的圖靈僞代碼：

1. 拷貝輸入A0B到磁帶2
2. 寫000010000到磁帶3
   • 由A從磁帶2乘上帶3的數量由
     1. 從A開始處開始
     2. 將0寫入磁帶4
        • 拷貝次數3 => 4
        • 向前移動一次在磁帶3（3 ++）
        • 去到步驟3，除非A結束
        • 從磁帶4移動答案帶3
   • 減量磁帶上數B 2
3. 如果B於磁帶2不爲0時，轉到步驟2
4. 答案複製從磁帶3到磁帶1

這裏是圖靈代碼應該工作（磁帶像指針，小寫字母，輸入帶i）：

# At the start for 2^3 
# i: 000111011110000 
#  ^

_start_ -> *a = 0, start2 
start2 [*i==0] -> i++, *a++ = 0, *b++ = 0, start4 
start2 [*i==1] -> i++, *a++ = 1, start2 
start4 [*i==0] -> *b-- = 0, b--, initc 
start4 [*i==1] -> i++, *b++ = 1, start4 
initc -> *c++ = 0, *c++ = 1, *c++ = 1, *c-- = 0, mult 

# example 
# i: 00011101111000 
#   ^
# a: 001110000 
#  ^
# b: 001111000 
#  ^
# c: 00011000 
#  ^

mult[*b==0]: lastcpy 
mult[*b==1]: b--, *d++ = 0, *d++ = 1, rewa 
rewa[*a==0]: a++, a++, multcpy 
rewa[*a==1]: a--, rewa 

multcpy[*c==1]: c++, multcpy2 
multcpy[*c==0]: multcpy3 
multcpy2[*a==0]: multcpy 
multcpy2[*a==1]: *d++ = 1, multcpy2 
multcpy3: *d-- = 0, *c = 0, cpydtoc 

cpydtoc[*d==1]: d--, *c++ = 1, cpydtoc 
cpydtoc[*d==0]: *c-- = 0, mult 

lastcpy[*c==1]: *i++ = 1, c--, lastcpy 
lastcpy[*c==0]: *i = 0, _finish_ 

# Should end with 
# i: 00011101111011111111100 
#      ^

請檢查錯誤:)