Как создать машину Тьюринга, которая служит калькулятором функций для 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 для представления 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 на ленту, выполните задачу один раз, затем отнимите 1 от конца числа N. Повторяйте, пока число N не исчезнет с ленты.

Надеюсь, этого достаточно, чтобы вы все равно начали. Таким образом, конечный автомат можно построить более или менее механически.

Answer 2

В моем собственном псевдокоде Тьюринга:

1. копировать ввод A0B на ленту 2
2. записать 000010000 на ленту 3
   • умножьте число на Ленте 3 на А из Ленты 2 на
     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
#                          ^

Пожалуйста, проверьте на ошибки:)