Алгоритмы машины Тьюринга

Question

Я пытаюсь определить, как машина Тьюринга (состоящая только из 0 и 1, без пробелов) может распознавать последовательность из 8 1. Каждый алгоритм, который я обнаружил, имеет TM, ищущий неопределенное число 1 или 0, а не конкретное число.

По сути, если у вас есть эта лента:

1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1

Как вы можете узнать, что 8 1 представляют собой сложение, и вы хотите добавить 0 0 0 1 и 0 0 0 1?

Answer 1

Я так понимаю, что 11111111 это как код операции и 0001, 0001 операнды для этого кода операции. По крайней мере, это единственная интерпретация, которую я вижу.

ТМ может искать фиксированное конечное число символов, используя аналогичное фиксированное конечное число состояний, единственной целью каждого из которых является распознавание другого ожидаемого символа. Например, вот ТМ с четырьмя лентами, который распознает сложение и выполняет двоичное сложение:

|----|----|----|----|----||----|-----|-----|-----|-----|----|----|----|----|
| Q  | T1 | T2 | T3 | T4 || Q' | T1' | T2' | T3' | T4' | D1 | D2 | D3 | D4 |
|----|----|----|----|----||----|-----|-----|-----|-----|----|----|----|----|
// read the opcode /////////////////////////////////////////////////////////
| qA | 1  | x  | y  | z  || qB | 1   | x   | y   | z   | R  | S  | S  | S  |
| qB | 1  | x  | y  | z  || qC | 1   | x   | y   | z   | R  | S  | S  | S  |
| qC | 1  | x  | y  | z  || qD | 1   | x   | y   | z   | R  | S  | S  | S  |
| qD | 1  | x  | y  | z  || qE | 1   | x   | y   | z   | R  | S  | S  | S  |
| qE | 1  | x  | y  | z  || qF | 1   | x   | y   | z   | R  | S  | S  | S  |
| qF | 1  | x  | y  | z  || qG | 1   | x   | y   | z   | R  | S  | S  | S  |
| qG | 1  | x  | y  | z  || qH | 1   | x   | y   | z   | R  | S  | S  | S  |
| qH | 1  | x  | y  | z  || qI | 1   | x   | y   | z   | R  | S  | S  | S  |
// read the first addend ///////////////////////////////////////////////////
| qI | w  | x  | y  | z  || qJ | w   | w   | y   | z   | R  | R  | S  | S  |
| qJ | w  | x  | y  | z  || qK | w   | w   | y   | z   | R  | R  | S  | S  |
| qK | w  | x  | y  | z  || qL | w   | w   | y   | z   | R  | R  | S  | S  |
| qL | w  | x  | y  | z  || qM | w   | w   | y   | z   | R  | R  | S  | S  |
// read the second addend //////////////////////////////////////////////////
| qM | w  | x  | y  | z  || qN | w   | x   | w   | z   | R  | S  | R  | S  |
| qN | w  | x  | y  | z  || qO | w   | x   | w   | z   | R  | S  | R  | S  |
| qO | w  | x  | y  | z  || qP | w   | x   | w   | z   | R  | S  | R  | S  |
| qP | w  | x  | y  | z  || qQ | w   | x   | w   | z   | R  | S  | R  | S  |
// prepare the output tape /////////////////////////////////////////////////
| qQ | w  | x  | y  | z  || qR | w   | x   | y   | z   | S  | S  | S  | R  |
| qR | w  | x  | y  | z  || qS | w   | x   | y   | z   | S  | S  | S  | R  |
| qS | w  | x  | y  | z  || qT | w   | x   | y   | z   | S  | S  | S  | R  |
| qT | w  | x  | y  | z  || qU | w   | x   | y   | z   | S  | S  | S  | R  |
// handle addition when no carry ///////////////////////////////////////////
| qU | w  | 0  | 0  | z  || qU | w   | 0   | 0   | 0   | S  | L  | L  | L  |
| qU | w  | 0  | 1  | z  || qU | w   | 0   | 1   | 1   | S  | L  | L  | L  |
| qU | w  | 1  | 0  | z  || qU | w   | 1   | 0   | 1   | S  | L  | L  | L  |
| qU | w  | 1  | 1  | z  || qV | w   | 1   | 1   | 0   | S  | L  | L  | L  |
| qU | w  | B  | B  | B  || hA | w   | B   | B   | B   | S  | R  | R  | R  |
// handle addition when carry //////////////////////////////////////////////
| qV | w  | 0  | 0  | z  || qU | w   | 0   | 0   | 1   | S  | L  | L  | L  |
| qV | w  | 0  | 1  | z  || qV | w   | 0   | 1   | 0   | S  | L  | L  | L  |
| qV | w  | 1  | 0  | z  || qV | w   | 1   | 0   | 0   | S  | L  | L  | L  |
| qV | w  | 1  | 1  | z  || qV | w   | 1   | 1   | 1   | S  | L  | L  | L  |
| qV | w  | B  | B  | B  || hA | w   | B   | B   | B   | S  | R  | R  | R  |
|----|----|----|----|----||----|-----|-----|-----|-----|----|----|----|----|

Условные обозначения:

• Q: текущее состояние
• T1: текущий символ ленты, входная лента
• T2: текущий символ ленты, скретч #1
• T3: текущий символ ленты, скретч #2
• T4: текущий символ ленты, выходная лента (не используется)
• Q ': состояние для перехода в
• T1': символ для записи на ленту ввода (не используется)
• T2 ': символ для записи на скретч #1
• T3 ': символ для записи на скотч #2
• T4 ': символ для записи на выходную ленту
• D1: направление перемещения входной ленты
• D2: направление перемещения скретча #1
• D3: направление перемещения скретча #2
• D4: направление перемещения головки выходной ленты

Условные обозначения:

• w, x, y и z являются переменными и представляют либо 0, либо 1. Переход, использующий все четыре из них, можно рассматривать как сокращенную запись для написания шестнадцати (2^4) конкретных переходов.
• направления: L= слева, S= то же самое, R= справа.
• B - пустой символ; с этим можно обойтись, если вы добавите больше состояний, чтобы помочь U и V в добавлении.