Какими будут эквиваленты ассемблера для операций на оригинальной машине Тьюринга? - PullRequest
Новая
       95

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

7 голосов
/ 21 августа 2010

Если исходное определение машины Тьюринга принять следующим образом:

... бесконечный объем памяти, полученный в виде бесконечной ленты, размеченной в квадраты, на каждом из которых символ можетбыть напечатанным.В любой момент в машине есть один символ;это называется отсканированным символом.Аппарат может изменять отсканированный символ, и его поведение частично определяется этим символом, но символы на ленте в другом месте не влияют на поведение аппарата.Однако лента может перемещаться вперед и назад через машину, что является одной из элементарных операций машины.Таким образом, любой символ на ленте может в конечном итоге иметь подачу.(Turing 1948, стр. 61)

Если вы хотите сопоставить эти операции операциям, выполняемым на процессоре, способном интерпретировать ассемблерные / двоичные инструкции - какие операции будут отображены?

(Мне известен переход от машин Тьюринга к машинам фон Неймана, свойственный этому вопросу)

Ответы [ 4 ]

7 голосов
/ 21 августа 2010

Чтение того, что вы написали, я бы сказал, что вам просто нужно:

  • Инструкция прямого приращения (для добавления к текущему местоположению ленты)
  • Инструкция косвенного приращения (переместить ленту)
  • Что-то, что должно действовать в ответ на текущее значение местоположения ленты

Например, в ARM-подобной сборке, если у вас есть R0, содержащий адрес налента, которую вам просто нужно 

ADDS r0, r0, #1 ;moves the tape forward
ADDS r0, r0, #-1 ;moves the tape backwards
ADDS [r0], [r0], #1 ;increments the value 'pointed by' the tape
ADDS [r0], [r0], #-1 ;decrements the value 'pointed by' the tape

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

BEQ Somewhere

Это более или менее, как работает Brainfuck.

3 голосов
/ 21 августа 2010

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

Давайте назовем это массивом int. int[] Symbols

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

int inxSym;
int scannedSymbol = Symbols[inxSym];

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

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

Symbols[inxSym] = newSymbol;

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

switch(scannedSymbol) {....}

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

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

Ничего там не делать.

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

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

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

1 голос
/ 22 августа 2010

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

  • Голова машины Тьюринга (та, которая «сканирует» символ в данный момент времени)будет эквивалентно указателю инструкций.
  • Следовательно, фазы извлечения и декодирования инструкций эквивалентны интерпретации отсканированного символа.
  • Выполнение будет представлено в виде более сложной последовательности операций TM.Давайте возьмем запись в память, например: переместим головку в определенную ячейку памяти, переместим данные из регистров в эту ячейку, вернемся к расположению, указанному в регистре IP, и увеличим его.

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

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

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

0 голосов
/ 21 августа 2010

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

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

Затем можно определить машину, записав ее

QnAi -> QmAoD

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

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

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

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

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

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

...