2

我正在研究图灵机的测试，但我遇到了一个问题，我必须创建一个图灵机作为函数计算器：

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 用于表示 0，而 0 不用作值，而是用作分隔符。

所以：

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

2 回答 2

4

我在这里猜测了一下，自从我玩图灵机模拟器以来已经有一段时间了。首先，我想将任务分为几个概念步骤：

  1. 将磁带上的数字增加磁带上另一个数字的值
  2. 将磁带上的一个数字乘以磁带上另一个数字的值 - 这可以通过重复执行步骤 1 来完成
  3. 在磁带上平方一个数字 - x ^ 2 是通过将 x 放在磁带上然后乘以它自己来计算的
  4. （最后一步）将磁带上的一个数字提高到磁带上另一个数字的值的幂 - 这可以通过重复执行步骤 2 来完成

要重复执行一项任务 N 次，将 N 放在磁带上，执行一次任务，然后从数字 N 的末尾减去 1。重复直到数字 N 从磁带上消失。

希望这足以让你开始。可以以这种方式或多或少地机械地构造状态机。

于 2009-06-23T01:47:16.990 回答
1

在我自己的图灵伪代码中：

  1. 将输入 A0B 复制到磁带 2
  2. 将 000010000 写入磁带 3
    • 将磁带 3 上的数字乘以磁带 2 中的 A
      1. 从 A 的开头开始
      2. 将 0 写入磁带 4
        • 复制数字 3 => 4
        • 在 Tape 3 (3++) 上前进一次
        • 除非 A 结束，否则进入第 3 步
        • 将答案从磁带 4 移动到磁带 3
    • 减少磁带 2 上的数字 B
  3. 如果磁带 2 上的 B 不为 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
#                          ^

请检查错误:)

于 2009-06-23T01:55:02.903 回答