Что будет эквивалентно языку ассемблера операций над будет ли оригинальная машина Тьюринга?

бесконечный объем памяти, полученный в виде бесконечной ленты, размеченной на квадраты, на каждом из которых может быть напечатан символ.

Назовем это массивом int. int [] Symbols

В любой момент в машине есть один символ; он называется отсканированным символом.

int inxSym;
int scannedSymbol = Symbols[inxSym]; 

(На уровне ЦП это известно как «основная память» или в современной системе «программный сегмент».

Машина может изменять отсканированный символ

Symbols[inxSym] = newSymbol;

, и его поведение частично определяется этим символом,

switch(scannedSymbol) {....}

(На уровне ЦП это «выполнение инструкции». Нет операционного кода, чтобы сообщить ему об этом; это просто то, что делает ЦП.)

но символы на ленте в другом месте не влияют на поведение машины.

Здесь нечего делать.

Однако ленту можно перемещать вперед и назад через машину, что является одной из элементарных операций машины.

  ++inxSym;
  --inxSym
   inxSym +=10;
 // etc.

(На уровне ЦП, это дескриптор с кодами операций JMP)

Я не уверен, что это на 100% верно, но это будет выглядеть примерно так:

• Головка машины Тьюринга (та, которая "сканирует" символ в определенный момент времени) будет эквивалентна указателю инструкций.
• Фазы выборки и декодирования инструкций эквивалентны интерпретации отсканированного символа.
• Выполнение будет представлено как более сложная последовательность операций TM. Возьмем, например, запись в память: перемещение головки в заданное место памяти, перемещение данных из регистров в это место, возврат в место, адресуемое регистром IP, и его инкремент.

Обратите внимание, что управление перемещением головки эквивалентно инструкциям управления потоком, то есть JMP и его собратьям.

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

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

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

Назовем состояния Qn, буквы алфавита Ai, считанные с ленты. Машина определяет следующее состояние из таблицы переходов и записывает Ao на ленту и движется в направлении D : L/R

. Затем машина может быть определена записью ее

QnAi -> QmAoD

добавление программы из Википедии тогда станет

QbA0 -> QbA1R
QbA1 -> QbA1R
Q0A- -> Q0A-L
Q1A0 -> QrA-L
Q1A1 -> QaA-L
Q1A- -> QrA-L 

с состоянием принятия и состоянием отклонения. Это довольно компактное и удобочитаемое представление матрицы перехода.

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

Чтобы реализовать это, у вас есть слева кортеж, а справа тройка, поэтому это сопоставляется с поиском в 2D-массиве для чтения тройки. Сдвиньте состояние с битами символа на ленте и соедините их вместе. Умножьте (хорошо, еще одна операция сдвига), чтобы освободить место для триплета, и используйте это как смещение в таблице, чтобы прочитать триплет.

Запишите новое состояние в регистр состояния, символ на ленту и прибавьте декремент, если найдете данные в триплете, или стоп, если там нет данных. Должно быть весело в сборке.