Question

Построить стандартную Машину Тьюринга, дописывающую к двоичному числу слева его бит чётности (1, если число единичных битов нечётно, и ноль, если чётно).

Answer 1

Ответ:

Q0:

   R0 - бит четности

   R1 - число единичных битов

   R2 - входное число

   R3 - выходное число

   R4 - текущий бит числа

   R5 - флаг конца числа

   R6 - нулевой бит

Q1:

   READ R2, R4

   JUMPNEG R4, Q6

   INC R1

   JMP Q2

Q2:

   READ R2, R4

   JUMPNEG R4, Q6

   INC R1

   JMP Q2

Q3:

   READ R2, R4

   JUMPNEG R4, Q6

   INC R1

   JMP Q2

Q4:

   READ R2, R4

   JUMPNEG R4, Q6

   INC R1

   JMP Q2

Q5:

   READ R2, R4

   JUMPNEG R4, Q6

   INC R1

   JMP Q2

Q6:

   MOVE R1, R0

   JUMPEVEN R0, Q7

   MOVE 1, R0

   JMP Q8

Q7:

   MOVE 0, R0

Q8:

   MOVE R2, R3

   MOVE R0, R4

   WRITE R3, R4

   JMP Q9

Q9:

   HALT

Answer 2

Давайте построим стандартную Машину Тьюринга, которая будет дописывать бит четности к двоичному числу.

Сначала определим алфавит, состоящий из символов "0" и "1". Пусть символ "_" будет представлять пустую ячейку на ленте.

Создадим следующий список состояний:

• q0: начальное состояние, перемещение к самому левому символу
• q1: идти вправо до конца числа
• q2: проверка четности числа
• q3: дописывание бита четности
• q4: завершающее состояние

Определим функции перехода для каждого состояния:

• q0:

  • Если текущий символ равен "_", перейти в q4.
  • Если текущий символ равен "0" или "1", перейти в q1.

• q1:

  • Если текущий символ равен "_", перейти в q2.
  • Если текущий символ равен "0" или "1", перейти вправо.

• q2:

  • Если текущий символ равен "_", перейти в q3.
  • Если текущий символ равен "0" или "1", перейти вправо.

• q3:

  • Записать на ленту бит четности (1 или 0).
  • Перейти в q4.

• q4:

  • Завершение работы.

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

1. Поместите головку чтения-записи Машины Тьюринга в начальное состояние q0.
2. Переместите головку влево до тех пор, пока не встретите символ "_".
3. Перейдите в состояние q1.
4. Перемещайтесь вправо по ленте до тех пор, пока не достигнете символа "_".
5. Перейдите в состояние q2.
6. Перемещайтесь вправо по ленте до тех пор, пока не достигнете символа "_".
7. Перейдите в состояние q3.
8. Запишите на ленту бит четности (1 или 0) в ячейку, следующую сразу за текущей позицией головки чтения-записи.
9. Перейдите в состояние q4.
10. Машина Тьюринга остановится, и на ленте будет результат с добавленным битом четности.

Обратите внимание, что данная реализация представляет ли