如何创建一个图灵机，作为功能的计算器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是在录像带(s)?(它可以是一个多录音机) 会是什么样的状态图看起来像什么？

注：我使用的是一元与1用于表示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
   • 乘上的数字磁带3由一个从磁带2
     1. 开始开始
     2. 写0至4带
        • 复制数3=>4
        • 向前迈进一带3(3++)
        • 要步骤3，除非结束
        • 搬回答带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
#                          ^

请检查错误:)