Привет, Хабр! В свободное от работы время по вечерам мне нравится воплощать в жизнь свои сумасшедшие идеи. В один из таких вечеров родилась мысль реализовать компилятор кода в машину Тьюринга. Осознав всю тщетность бытия сложность реализации, было принято решение начать с чего-то более простого – симулятора простенького процессора со своим собственным ассемблером, в котором команды выполнялись бы с помощью различных состояний машины Тьюринга, а данные хранились бы на одной ленте. В конечном итоге удалось осуществить практически первоначальную задумку, а именно получить одну единственную машину Тьюринга, способную выполнять скомпилированную из NASM подобного ассемблера программу без какого-либо внешнего взаимодействия.

Напоминание о том, что такое машина Тьюринга

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

• бесконечная лента, состоящая из ячеек;

• головка для считывания/записи символов на ленте;

• устройство управления.

Бесконечная лента

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

Перед началом работы на ленту помещается входное слово. В процессе работы содержимое ленты модифицируется устройством управления и в результате на ленте остаётся выходное слово.

Считывающая / записывающая головка

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

Устройство управления

Под устройством управления понимается таблица состояний с правилами перехода. Состоянием называется строка таблицы, в которой в данный момент находится машина. Состояние, в котором находится машина перед запуском называется начальным, обычно обозначается именем q₀. Для завершения работы МТ используется специальное терминальное состояние, которое обозначается как HALT.

Таблица имеет размер Q|x|A|, где |Q| — количество состояний, а |A| — размерность алфавита, включая символ λ. В первой (заголовочной) строке записаны символы алфавита. В каждой ячейке таблицы строки состояния, располагаются тройки <char, action, state>, определяющие действие машины, которое необходимо сделать в том случае, если МТ находится в этом состоянии, а головка расположена на символе из заголовочной ячейки данного столбца:

• char – символ, который нужно записать на ленту;

• action – действие, которое нужно совершить после записи (одно из трёх действий: L – переместить головку на один символ влево, N – не перемещать головку, R– переместить головку на один символ вправо);

• state – состояние, в которое необходимо перейти после записи символа и действия перемещения.

Допускаются краткие записи для правил:

• Если необходимо выполнить только сдвиг, оставшись в том же состоянии, то достаточно записать только символ перемещения: L, N или R;

• Если нужно выполнить останов, то достаточно записать HALT;

Пример простейшей машины Тьюринга

В слове из алфавита {a, b} инвертировать символы. В начальный момент головка находится в начале слова.

Пока под головкой не окажется пустой символ (λ), вместо символа a записывается символ b, а вместо b записывается a и выполняется сдвиг головки вправо на очередной символ. При считывании пустого символа МТ переходит в терминальное состояние.

Первая версия симулятора - симулятор с машиной Тьюринга

В качестве базовых требований к симулятору процессора были поставлены следующие:

• произвольная разрядность процессора (bitDepth);

• несколько регистров общего назначения – A, B, C, D, E, F;

• поддержка только беззнаковых чисел;

• набор базовых команд вроде MOV, INC, DEC, ADD, AND, NOT, JMP и т.д.;

• поддержка флагов переноса (CF) и нуля (ZF), а также условных переходов;

• выполнение команд с помощью МТ.

Компиляция программы

При компиляции программа на ассемблере парсится в список инструкций выполняемой команды и её аргументов. Например, программа для вычисления 11-го числа Фибоначчи, записанная на ассемблере

MOV A, 11 ; номер числа Фибоначчи
MOV C, 1

.loop:
    MOV D, B
    ADD B, C
    MOV C, D
    DEC A
    JNZ .loop

HLT

превращается в такой список:

program = [
    { "command": "MOV", "args": ["A", "11"] },
    { "command": "MOV", "args": ["C", "1"] },
    { "command": "MOV", "args": ["D", "B"] },
    { "command": "ADD", "args": ["B", "C"] },
    { "command": "MOV", "args": ["C", "D"] },
    { "command": "DEC", "args": ["A"] },
    { "command": "JNZ", "args": [2] },
    { "command": "HLT", "args": [] }
]

Для управления выполняемой инструкцией программы используется целочисленный индекс – programIndex, изначально равный нулю. При выполнении операций перехода этот индекс заменяется номером инструкции, которому соответствует метка переданного аргумента, получаемая из предварительно заполненного словаря "метка" - "номер инструкции". После того, как programIndex выходит за границы списка инструкций или выполняется инструкция останова (HLT), программа завершает своё выполнение.

Хранение значений

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

registers = {
    "A": "00000000",
    "B": "01011001",
    "C": "00110111",
    "D": "00110111",
    "E": "00000000",
    "F": "00000000",
}

flags = {
    "ZF": false
    "CF": false
}

Команды для АЛУ

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

Примеры нескольких команд АЛУ:

Выполнение команды

При выполнении команды пересылки переданное значение копируется в результирующий регистр.

Операции безусловного перехода, как было сказано ранее, просто обновляют индекс выполняемой инструкции. Инструкции условного перехода работают аналогичным образом, предварительно проверяя на соответствующее условие значения флагов ZF и CF.

При выполнении очередной команды АЛУ, не являющейся операцией перехода или пересылки значения (MOV), выполняются следующие действия:

• Если команда использует один аргумент, то его значение помещается на ленту машины Тьюринга как есть. Если же команда использует два аргумента, то на ленту помещается слово из значений аргументов, разделённых символом #;

• Машина Тьюринга запускается из состояния, соответствующего выполняемой команде;

• По достижении терминального состояния слово на ленте извлекается, проверяется значение на равенство нулю и наличие переноса для установки флагов ZF и CF. Если при проверке было обнаружено наличие переноса, то из слова удаляется первый символ;

• Обработанное слово записывается в результирующий аргумент.

Недостатки первой версии симулятора

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

Вторая версия симулятора - полноценная машина Тьюринга

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

Дополнительные требования к симулятору

• поддержка как беззнаковых чисел, так и чисел со знаком;

• в дополнение к имеющимся флагам добавить флаги переполнения (OF) и знака (SF);

• условные переходы знакового сравнения – JL, JLE, JG, JGE и т.д.;

• возможность подсветить на ленте значения регистров и флагов;

• память с произвольным количеством ячеек;

• использование адресов для обращения к памяти – [12] или [A];

• (условно) бесконечный стек;

• подпрограммы (команды CALL и RET).

Для реализации МТ с учётом всех требований, определимся с форматом размещения на ленте основных блоков:

• выполняемая программа;

• регистры;

• АЛУ и флаги;

• память;

• стек.

Размещаем на ленте программу

Для определения границ начала и конца программы введём соответствующие символы (здесь и далее под символом будет пониматься строка, длина которой может быть больше одного – это требуется ради наглядности и никак не влияет на алгоритм работы МТ, поскольку всегда можно выполнить замену таких строк на очередной неиспользованный символ):

const PROGRAM_CHAR = 'PRG'
const PROGRAM_END_CHAR = 'END'

Первым символом на ленте будет идти символ начала программы PROGRAM_CHAR. После него необходимо разместить max(programDepth, bitDepth) + 1 пустых символов λ, где programDepth – минимальное число бит, необходимых для получения любого числа от 0 до количества инструкций без единицы. Это место впоследствии будет использоваться для записи адреса перехода.

После места для адреса размещаются инструкции программы, разделённые символом #. При этом первая и последняя команды также отделяются #. В конце последней решётки записывается символ конца программы – PROGRAM_END_CHAR.

Размещение команд на ленте

Размещение команд перехода

• Команды безусловного перехода записываются в виде JMP b₀ b₁ b₂ ... bₙ , где b₀, b₁, b₂, bₙ – биты адреса перехода.

• Команды условного перехода, а также команда CALL записываются в виде J__ λ b₀ b₁ b₂ ... bₙ , где J__ – команда условного перехода, например, JZ, а b₀, b₁, b₂, bₙ – биты адреса перехода.

Перевод адреса в аргумент

Для записи адреса как аргумента команды на ленте, используется символ &. После этого идёт или регистр, если использовался регистровый адрес, либо двоичная константа, если использовался адрес в виде константы.

Размещение команд пересылки (MOV)

Записывается первый аргумент:

• если регистр, размещается его имя и затем 0;

• если адрес, он переводится в аргумент, и добавляется λ.

Записывается второй аргумент

• если регистр, размещается его имя;

• если константа, она переводится в двоичный вид длины bitDepth;

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

После этого размещается λ, MOV и ещё один символ λ.

Размещение стековых команд

Записывается имя команды - POP или PUSH

• если аргумент константа, она переводится в двоичный вид длины bitDepth;

• если адрес, он переводится в аргумент;

• если регистр, записывается его имя;

В конце добавляется символ λ.

Размещение унарных команд

• записывается единственный аргумент как есть (поскольку является регистром);

• записывается λ;

• записывается имя команды;

• записывается заключительная λ;

Размещение бинарных команд

• записывается первый аргумент (так как всегда регистр);

• записывается 1;

• в зависимости от типа второго аргумента, аналогично стековым командам;

• записывается λ;

• записывается имя команды;

• записывается заключительная λ;

Размещение команд без аргументов (RET и HLT)

Символ команды просто записывается на ленту.

Пример размещения программы на ленте 3-битного процессора:

MOV A, 4
DEC A
ADD A, 3

Размещаем на ленте регистры

После программы расположены регистры. Каждый регистр начинается со своего имени, затем идут bitDepth нулей и завершающая λ, после чего начинается новый регистр.

Размещаем на ленте АЛУ и флаги

Для определения начала АЛУ и флагов на ленте аналогично программе необходимо ввести дополнительные символы:

const ALU_CHAR = 'ALU' // символ АЛУ
const ALU_CARRY_CHAR = '$' // символ АЛУ с переносом

const OVERFLOW_FLAG_CHAR = 'OF' // флаг переполнения
const SIGN_FLAG_CHAR = 'SF' // флаг знака
const ZERO_FLAG_CHAR = 'ZF' // флаг нуля
const CARRY_FLAG_CHAR = 'CF' // флаг переноса

В процессе разработки состояний для выполнения команд было выявлено, что для самых длинных с точки зрения ячеек операций – MUL и DIV требуется 3·(bitDepth+1) ячеек ленты. Именно столько пустых ячеек будет расположено после символа начала АЛУ – ALU_CHAR.

Сразу после АЛУ будут идти флаги. Каждый флаг занимает две ячейки - имя флага и 0. В процессе работы арифметико-логических команд эти значения будут модифицироваться в конце выполнения:

Размещаем на ленте память

Для памяти заведём дополнительный символ MEMORY_CHAR:

const MEMORY_CHAR = 'MEM'

Для индексации аналогично программе после символа начала памяти выделим место для записи номера ячейки. Количество бит – max(memoryDepth, bitDepth), где memoryDepth – минимальное число бит для получения всех чисел от 0 до количества ячеек памяти без единицы (memoryCount). После этого в количестве memoryCount будут записаны нулевые слова длины bitDepth, начинающиеся с символа #:

Размещаем на ленте стек

Изначально, поскольку стек пуст, на ленте будет записан только символ начала стека – STACK_CHAR:

const STACK_CHAR = 'STK'

В процессе размещения на нём значений на ленту будут записываться символы битов размещаемого значения и дополнительно символ # для разделения ячеек между собой. Таким образом лента может расти в правую сторону и такой стек можно считать условно бесконечным, пока хватит памяти компьютера, на котором запущен симулятор.

Лента МТ перед началом работы

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

DEC A
NEG A

на 3-х битном процессоре будет выглядеть следующим образом:

Алгоритм работы МТ-симулятора

Изначально считывающая головка находится на самом первом символе программы –PROGRAM_CHAR, а сама машина Тьюринга находится в состоянии RUN. Симулятор последовательно выполняет команду за командой и по достижении терминального состояния HALT прекращает свою работу.

Алгоритм последовательного выполнения инструкций

Состояние RUN выполняет следующие действия:

• если встречается символ #, он заменяется на символ @, головка сдвигается на один символ вправо и МТ переходит в состояние декодирования инструкции FETCH;

• если встречается символ PROGRAM_END_CHAR, машина переходит в терминальное состояние;

• если встречается любой другой символ, головка сдвигается вправо на одну ячейку.

В процессе выполнения команд для перехода к следующей команде используется состояние RETURN-RUN:

• по символам PROGRAM_CHAR и @ выполняется сдвиг вправо и переход в состояние RUN;

• по символу ~ выполняется запись символа λ и сдвиг вправо, после чего выполняется переход в состояние FETCH для декодирования следующей части команды (этот символ служит признаком того, что была обработана часть команды и требуется сделать дополнительные действия прежде чем переходить к следующей команде);

• для всех остальных символов алфавита выполняется перемещение головки влево.

Декодирование инструкций

Для декодирования инструкций и их аргументов используется состояние FETCH. В этом состоянии могут произойти следующие ситуации в зависимости от символа под головкой:

• символы 0 и 1 – выполняется запись константы на АЛУ, после чего записывается символ ~, для обработки следующего аргумента во время возврата к выполнению;

• символ регистра – выполняется сдвиг вправо для проверки типа команды:

  Если правее находится символ 0, то значение регистра никуда записывать не нужно, оно используется только для записи результата, поэтому символ заменяется на λ, головка сдвигается на символ правее и выполняется декодирование следующей инструкции;

  Если же правее регистра находится символ λ, то необходимо записать содержимое регистра на АЛУ;

  Если правее находится символ 1, то тоже нужно записать значение регистра на АЛУ, но в конце дополнительно добавить символ #для разделения двух аргументов;

  Аналогично записи константы после аргумента записывается символ ~, для обработки следующего аргумента во время возврата к выполнению.

• символ & – адресный аргумент, необходима проверка, первый ли это аргумент. Если первый (левее находится символ @), то это команда MOV и необходимо подготовить ячейку памяти для записи в неё второго аргумента. Если же это второй аргумент, то необходимо пометить ячейку памяти и записать из неё данные в конец АЛУ;

• символ # – означает, что команда была обработана полностью, выполняется переход влево и МТ переход в состояние записи результата – WRITE-BACK;

• символ конца программы – выполняется переход в состояние останова;

• команда перехода – выполняется сдвиг вправо и МТ переходит в одноимённое состояние команды перехода;

• стековые команды – выполняется переход в состояние PUSH или POP для соответствующего декодированного символа;

• команда пересылки MOV – выполняется возвращение в исходное состояние аргументов команды с последующей записью результата;

• остальные команды – с помощью дополнительного состояния справа символ заменяется на ~, после чего головка перемещается на следующий символ за символом начала АЛУ и производится переход в состояние выполняемой команды.

Выполнение команд на АЛУ

При обработке символа команды, выполняемой на АЛУ, МТ перемещается на первый символ, следующий за ALU_CHAR и переходит в состояние, соответствующее исполняемой команде. Это очень похоже на работу первой версии симулятора, однако в этом случае в конце вычислений вместо терминального состояния машина Тьюринга переходит в состояние записи флагов. После записи всех флагов симулятор переходит в состояние RETURN-RUN и возвращается к выполнению инструкции для записи результата.

Запись флагов

Все флаги кроме флага переполнения (OF) можно автоматически проставить, проанализировав результат, записанный на АЛУ:

• Флаг знака (SF) – следующий символ за символом АЛУ равен записываемому значению флага;

• Флаг переноса (CF) – специально для этого флага помимо символа ALU_CHAR введён дополнительный ALU_CARRY_CHAR, который записывается вместо ALU_CHAR, если в процессе выполнения команды возник перенос разряда. Поэтому значение флага CF равно 1, если АЛУ начинается с символа ALU_CARRY_CHAR и 0, если с ALU_CHAR;

• флаг нуля (ZF) – последовательно проходя по записанному на ленте слову в случае считывания ненулевого символа в значение флага записывается 0, в противном случае, дойдя до λ записывается 1.

• флаг переполнения (OF) должен анализироваться для каждой из операций независимо, а потому по окончании выполнения инструкции МТ анализирует полученный результат и аргументы и переходит в одно из двух состояний – OVERFLOW или NO-OVERFLOW, которые записывают 1 и 0 соответственно в значение флага OF.

Таким образом состояние для записи флага переполнения автоматически переходит в состояние записи флага SF. Из записи знака МТ переходит в состояние проверки переноса и записи флага CF, из которого переходит в проверку знака и запись флага ZF, после чего выполнение операции считается завершённым.

Таблица состояний для записи флагов

0

1

λ

OF

SF

ZF

CF

ALU

$

OVERFLOW

R

R

R

OF,R,OVRFLOW-WRITE

NO-OVERFLOW

R

R

R

OF,R,NO-OVRFLOW-WRITE

OVERFLOW-WRITE

1,L,BEGIN-SIGN

1,L,BEGIN-SIGN

NO-OVERFLOW-WRITE

0,L,BEGIN-SIGN

0,L,BEGIN-SIGN

BEGIN-SIGN

L

L

L

L

ALU,R,CHECK-SIGN

$,R,CHECK-SIGN

CHECK-SIGN

0,R,NO-SIGN

1,R,SIGN

SIGN

R

R

R

R

SF,R,SIGN-WRITE

NO-SIGN

R

R

R

R

SF,R,NO-SIGN-WRITE

SIGN-WRITE

1,L,BEGIN-CARRY

1,L,BEGIN-CARRY

NO-SIGN-WRITE

0,L,BEGIN-CARRY

0,L,BEGIN-CARRY

BEGIN-CARRY

L

L

L

L

L

ALU,R,NO-CARRY

ALU,R,CARRY

CARRY

R

R

R

R

R

R

CF,R,CARRY-WRITE

NO-CARRY

R

R

R

R

R

R

CF,R,NO-CARRY-WRITE

CARRY-WRITE

1,L,BEGIN-ZERO

1,L,BEGIN-ZERO

NO-CARRY-WRITE

0,L,BEGIN-ZERO

0,L,BEGIN-ZERO

BEGIN-ZERO

L

L

L

L

L

L

L

R,CHECK-ZERO

CHECK-ZERO

R

1,R,NO-ZERO

λ,R,ZERO

ZERO

R

R

R

R

R

ZF,R,ZERO-WRITE

R

NO-ZERO

R

R

R

R

R

ZF,R,NO-ZERO-WRITE

R

ZERO-WRITE

1,L,RETURN-RUN

1,L,RETURN-RUN

NO-ZERO-WRITE

0,L,RETURN-RUN

0,L,RETURN-RUN

Работа с памятью

Для выполнения операций с памятью необходимо уметь перемещаться в ячейку с заданным номером. Именно для этого на ленте после символа MEMORY_CHAR находится пустое место. Для того, чтобы пометить ячейку памяти по заданному индексу, в это пустое место записывается номер ячейки (это может быть как константа, так и значение регистра). После этого адрес уменьшается на единицу. Если в процессе уменьшения произошло переполнение (головка переместилась на символ памяти), то искомая ячейка найдена, в противном случае МТ идёт вправо, пока не встретит первый символ #, который затем заменяется на @ и производится возвращение в состояние декремента адреса.

После того как ячейка помечена, в неё можно записывать информацию (команда MOV address value), поместить это значение в стек (PUSH address) или же поместить значение из памяти на АЛУ ( ADD register address). Для всех этих трёх ситуаций, используются свои независимые состояния пометки ячейки.

Работа со стеком

В случае выполнения команды PUSH value всё довольно просто:

• если в стек кладётся константа, последовательно переписывается значение из аргумента в конец стека;

• если в стек кладётся значение регистра, то МТ перемещается на регистр и выполняет практически то же самое перемещение бита за битом в конец стека;

• если в стек кладётся значение из памяти, ячейка помечается, после чего аналогично регистру копируются биты.

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

Если же выполняется операция извлечения из стека POP register, то МТ перемещается на последний символ стека и проверяет, что левее находится # или STACK_CHAR. Если обнаруживается символ STACK-CHAR, это означает, что стек пуст, а потому машина переходит в терминальное состояние UNDERFLOW, а симулятор сигнализирует об ошибке. В противном случае # удаляется, а затем, последовательно удаляя бит за битом и копируя его на регистр, значение на вершине стека полностью перемещается на регистр.

Работа с командами перехода

Если встречена команда безусловного перехода JMP, то головка перемещается вправо и последовательно копирует адрес команды в пустое место после символа начала программы. После того, как адрес скопирован, головка перемещается в начало программы, а все символы @ заменяются на #, тем самым снимая пометки с пройденных команд. Дойдя до PROGRAM_CHAR, аналогично работе с памятью, скопированное значение адреса уменьшается и на каждой итерации команда помечается путём последовательной замены # на @. Как только адрес "обнулится", МТ переходит в состояние RUN, тем самым переходя на первую непомеченную инструкцию.

В случае команд условного перехода предварительно проверяются условия перехода путём проверки значения флагов и их комбинаций. Результат проверки записывает правее команды перехода символ 0 или 1, означающий выполнение или невыполнение условия перехода. Если условие выполнено, МТ переходит в состояние безусловного перехода, копируя адрес. В противном случае выполняется переход на следующую команду путём перехода в состояние RUN.

Вызов подпрограмм – CALL и RET

При обработке команды вызова подпрограммы МТ необходимо получить адрес следующей инструкции для возможности последующего перехода на него. Для этого симулятор использует следующий алгоритм:

• правее команды CALL записывается символ ~ и выполняется переход на символ начала программы;

• выполняется увеличение числа адреса на 1 (первый раз λ будет заменена на 0, затем 0 на 1, в следующий раз адрес запишется как 10, тем самым обеспечивая автоматический сдвиг всех бит при необходимости переноса на символ PROGRAM_CHAR);

• после каждого инкремента адреса симулятор перемещается по ленте вправо, пока не встретит символ #, после чего, начнёт движение влево до символа @, который будет заменён на # и машина Тьюринга вернётся в начало программы для очередного инкремента адреса;

• как только все метки инструкций (@) закончатся, машина перейдёт в состояние переноса адреса на стек. Это действие полностью аналогично команде PUSH с тем отличием, что после выполнения этого действия, симулятор вернётся на проставленный символ ~, заменит его на λ и перейдёт в состояние безусловного перехода.

Когда же симулятор встречает команду RET, выполняются обратные действия:

• машина Тьюринга перемещается на последний символ в стеке, предварительно проверяя, что стек не пуст, после чего смещается на первый символ последнего значения и заменяет его на O или I в зависимости от числа и переходит в состояние добавления считанного символа к адресу программы;

• как только в адрес программы записано число, МТ возвращается на первый символ O или I, заменяет его на пустой символ и переносит следующий символ;

• после переноса адреса целиком, симулятор переходит в состояние перемещения на инструкцию по заданному адресу, записанному в самом начале программы, как это делается в безусловном переходе.

Подробнее о переносе значений

Для того, чтобы отличать перенесённые биты от неперенесённых, во всех операциях перемещения значений используются символы O и I. Как только необходимо перенести символ 0, он заменяется на O и выполняется перенос нуля. Аналогично, когда нужно перенести 1, выполняется замена на I и переносится единица. Для возвращения обратно не нужно предварительно перемещаться на блок, из которого производится перенос, так как достаточно дойти до первого символа O или I, после чего сдвинуть головку и продолжить перенос значения дальше.

Параметры полученной машины Тьюринга

• 75 символов алфавита (λ, 0, 1, O, I, #, @, &, ~, символы начала блоков (10), имена регистров (6) и команды (50));

• 641 состояние;

• 15694 действия;

• полностью автономна после единственной записи на ленту и запуска.

Внешний вид симулятора

С точки зрения интерфейса симулятор разделён на две части:

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

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

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

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

При запуске симулятора есть возможность изменять тип шагов:

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

• по состояниям - содержимое ленты будет обновляться каждый раз, когда один шаг МТ привёл к изменению состояния;

• по ячейкам – самый медленный, но зато самый подробный и наглядный вариант выполнения. Содержимое ленты обновляется после каждого элементарного шага машины.

Для более быстрого погружения в симуляторе доступны несколько примеров программ:

• вычисление числа Фибоначчи (используется по умолчанию);

• проверка гипотезы Коллатца для заданного числа;

• вычисление НОД двух чисел по алгоритму Евклида;

• пример работы с памятью и стеком.

Спасибо, что дочитали до конца! Если Вам интересно посмотреть на код проекта и самостоятельно запустить симулятор, то это можно сделать здесь: TuringCpu. В ридми репозитория описаны все используемые команды, формат команд и констант, а также другие полезные данные о симуляторе.