Есть такая штука — машина Тьюринга. Представляет собой простейший компьютер, однако писать под него хуже, чем на brainfuck'е. Решил я тут на днях побаловаться, но делать интерпретатор — не спортивно, да интерпретаторов этих — вагон. Потом меня посетила еще более странная идея — а чего бы не сделать это на Асме? (я его знаю паршиво, как раз решил потренироваться, так что сильно не пинайтесь).
Итак, сделаем генератор кода.
Принимает на вход файл, в котором перечислены подряд правила в виде
начальное_состояние начальный_символ конечное_состояние конечный_символ переход(l / r / p — остаться на месте).
Тут ничего особого нет, поэтому привожу как есть, без комментов:
Получается out.cpp с вот таким-вот кодом:
(комменты добавлены отдельно)
На вход подается input.txt
1 строка — входные данные, в данном случае —
1010+10+110110101+11101101011110101+1+10110100101100110110101+10101011011011
потом начальное состояние, состояние завершения и начальное положение головки(исполнительного устройства)
80 99 0
Теперь остается только скомпилировать готовое приложение — берем
VS20XX x86 Native Tools Command Prompt
pushd d:\turing
cl out.cpp /nologo
запускаем
out.exe
как и ожидалось, получаем
10111000110000101000111
Вот сам алгоритм сложения
Итак, сделаем генератор кода.
Принимает на вход файл, в котором перечислены подряд правила в виде
начальное_состояние начальный_символ конечное_состояние конечный_символ переход(l / r / p — остаться на месте).
Тут ничего особого нет, поэтому привожу как есть, без комментов:
Генератор
#include <conio.h>
#include <stdio.h>
#include <iostream>
void main()
{
FILE *input = fopen("rules.txt", "r");
FILE *output = fopen("out.cpp", "w+");
int number = 0;
int o_state, d_state;
char o_char, d_char, dir;
{
fprintf(output, "#include <stdio.h>\n#include <conio.h>\n#include <iostream>\n\n");
fprintf(output, "char tape[0x7fffff];\n\n");
fprintf(output, "void main()\n{\n");
fprintf(output, "\tFILE *input = fopen(\"input.txt\", \"r\");\n");
fprintf(output, "\tfscanf(input, \"%%s\", &tape[0x3FFFFF]);\n");
fprintf(output, "\tint state, final_state, p;\n");
fprintf(output, "\tfscanf(input, \"%%i %%i %%i\", &state, &final_state, &p);\n");
fprintf(output, "\tchar * pos = &tape[0x3FFFFF+p];\n");
fprintf(output, "\tfor (char * q = &tape[0x3FFFFF-1]; q >= &tape[0]; q --)\n\t\t*q = '#';\n");
fprintf(output, "\tfor (char * q = &tape[strlen(tape)]; q <= &tape[0x7fffff]; q ++)\n");
fprintf(output, "\t\t*q = '#';\n");
fprintf(output, "\t_asm\n\t{\n");
fprintf(output, "\t\txor eax, eax\n");
fprintf(output, "\t\t\tmov eax, pos\n");
fprintf(output, "\t\t\tmov ecx, state\n");
fprintf(output, "\t\t\tmov edx, final_state\n\n");
fprintf(output, "BEG:\n");
fprintf(output, "\t\tcmp ecx, edx\n");
fprintf(output, "\t\t\tje EXIT\n\n");
}
while (!feof(input))
{
fscanf(input, "%i %c %i %c %c", &o_state, &o_char, &d_state, &d_char, &dir);
fprintf(output, "R%i:\n", number);
fprintf(output, "\t\tcmp ecx, %i\n", o_state);
fprintf(output, "\t\t\tjne R%i\n", number+1);
fprintf(output, "\t\t\tcmp [eax], '%c'\n", o_char);
fprintf(output, "\t\t\tjne R%i\n", number+1);
fprintf(output, "\t\t\tmov [eax], '%c'\n", d_char);
if (dir == 'r')
fprintf(output, "\t\t\tadd eax, 1\n");
if (dir == 'l')
fprintf(output, "\t\t\tsub eax, 1\n");
fprintf(output, "\t\t\tmov ecx, %i\n", d_state);
fprintf(output, "\t\t\tjmp END\n\n");
number++;
}
{
fprintf(output, "R%i:\n", number);
fprintf(output, "\t\tjmp END\n\n");
fprintf(output, "END:\n");
fprintf(output, "\t\tjmp BEG\n\n");
fprintf(output, "EXIT:\n\t\tnop\n\n\t}\n\n");
fprintf(output, "\tint begin, end;\n");
fprintf(output, "\tbegin = strspn(tape,\"#\");\n");
fprintf(output, "\tend = strcspn(&tape[begin],\"#\");\n");
fprintf(output, "\tfor (int k = 0; k < end; k++)\n");
fprintf(output, "\t\tprintf(\"%%c\", tape[begin + k]);\n");
fprintf(output, "\t_getch();\n}\n");
}
fclose(input);
fclose(output);
}
Получается out.cpp с вот таким-вот кодом:
(комменты добавлены отдельно)
Результат
#include <stdio.h>
#include <conio.h>
#include <iostream>
char tape[0x7fffff];
//псевдобесконечная лента
//по 0x3fffff в обе стороны должно хватить
void main()
{
FILE *input = fopen("input.txt", "r");
fscanf(input, "%s", &tape[0x3FFFFF]);
int state, final_state, p;
//текущее состояние, конечное, начальная
//позиция "головки"
fscanf(input, "%i %i %i", &state, &final_state, &p);
char * pos = &tape[0x3FFFFF+p];
//указатель на "головку"
for (char * q = &tape[0x3FFFFF-1]; q >= &tape[0]; q --)
*q = '#';
for (char * q = &tape[strlen(tape)]; q <= &tape[0x7fffff]; q ++)
*q = '#';
//остаток ленты заполняем
//пустым символом - #
_asm
{
xor eax, eax
mov eax, pos
mov ecx, state
mov edx, final_state
//помещаем в регистры
//позицию и состояния
BEG:
cmp ecx, edx
je EXIT
//если уже в конечном состоянии
//незачем проверять правила
//уходим отсюда
R0:
cmp ecx, 80
jne R1
cmp [eax], '1'
jne R1
mov [eax], '1'
add eax, 1
mov ecx, 80
jmp END
//правило 0 : 80 1 -> 80 1 r
R1:
cmp ecx, 80
jne R2
cmp [eax], '0'
jne R2
mov [eax], '0'
add eax, 1
mov ecx, 80
jmp END
//80 0 -> 80 0 r
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//еще сколько-то правил
R60:
cmp ecx, 70
jne R61
cmp [eax], '0'
jne R61
mov [eax], '0'
mov ecx, 99
jmp END
R61:
jmp END
//правила кончились,
//идем на новую итерацию
END:
jmp BEG
EXIT:
nop
}
int begin, end;
begin = strspn(tape,"#");
end = strcspn(&tape[begin],"#");
for (int k = 0; k < end; k++)
printf("%c", tape[begin + k]);
//находим последнюю #
//слева и первую справа,
//выводим все, что между ними
_getch();
}
На вход подается input.txt
1 строка — входные данные, в данном случае —
1010+10+110110101+11101101011110101+1+10110100101100110110101+10101011011011
потом начальное состояние, состояние завершения и начальное положение головки(исполнительного устройства)
80 99 0
Теперь остается только скомпилировать готовое приложение — берем
VS20XX x86 Native Tools Command Prompt
pushd d:\turing
cl out.cpp /nologo
запускаем
out.exe
как и ожидалось, получаем
10111000110000101000111
Вот сам алгоритм сложения
Довольно сумбурные заметки в ходе его написания
80 — ползем вправо до первого +,
меняем его на _ и уходим влево
0 идем вправо до +, меняем на _
и начинаем складывать разряды
1x — правый разряд = x
2x — слева от _, разряд = x
n = null
l = 1
t = 2
5x — переносим ли 1 из предыдущего разряда
меняем его на _ и уходим влево
0 идем вправо до +, меняем на _
и начинаем складывать разряды
1x — правый разряд = x
2x — слева от _, разряд = x
n = null
l = 1
t = 2
5x — переносим ли 1 из предыдущего разряда
Сложение в 2 системе
80 1 80 1 r
80 0 80 0 r
80 + 0 _ l
0 1 0 1 r
0 0 0 0 r
0 _ 0 _ r
0 # 1 # l
0 l 0 l r
0 t 0 t r
0 n 0 n r
0 @ 0 @ r
0 + 1 + l
1 0 10 @ l
1 1 11 @ l
1 _ 50 @ l
1 @ 1 @ l
10 0 10 0 l
10 1 10 1 l
10 _ 20 _ l
10 @ 10 @ l
11 0 11 0 l
11 1 11 1 l
11 _ 21 _ l
11 @ 11 @ l
20 0 0 n r
20 1 0 l r
20 # 0 n r
20 t 20 t l
20 l 20 l l
20 n 20 n l
20 @ 20 @ l
21 0 0 l r
21 1 0 t r
21 # 0 l r
21 t 21 t l
21 l 21 l l
21 n 21 n l
21 @ 21 @ l
50 t 51 0 l
50 l 50 1 l
50 1 50 1 l
50 n 50 0 l
50 0 50 0 l
50 @ 50 @ l
51 n 50 1 l
51 0 50 1 l
51 l 51 0 l
51 1 51 0 l
51 t 51 1 l
51 @ 51 @ l
50 # 60 # r
51 # 60 1 r
60 1 60 1 r
60 0 60 0 r
60 @ 60 @ r
60 + 0 _ r
60 # 70 # l
70 @ 70 # l
70 1 99 1 p
70 0 99 0 p
80 0 80 0 r
80 + 0 _ l
0 1 0 1 r
0 0 0 0 r
0 _ 0 _ r
0 # 1 # l
0 l 0 l r
0 t 0 t r
0 n 0 n r
0 @ 0 @ r
0 + 1 + l
1 0 10 @ l
1 1 11 @ l
1 _ 50 @ l
1 @ 1 @ l
10 0 10 0 l
10 1 10 1 l
10 _ 20 _ l
10 @ 10 @ l
11 0 11 0 l
11 1 11 1 l
11 _ 21 _ l
11 @ 11 @ l
20 0 0 n r
20 1 0 l r
20 # 0 n r
20 t 20 t l
20 l 20 l l
20 n 20 n l
20 @ 20 @ l
21 0 0 l r
21 1 0 t r
21 # 0 l r
21 t 21 t l
21 l 21 l l
21 n 21 n l
21 @ 21 @ l
50 t 51 0 l
50 l 50 1 l
50 1 50 1 l
50 n 50 0 l
50 0 50 0 l
50 @ 50 @ l
51 n 50 1 l
51 0 50 1 l
51 l 51 0 l
51 1 51 0 l
51 t 51 1 l
51 @ 51 @ l
50 # 60 # r
51 # 60 1 r
60 1 60 1 r
60 0 60 0 r
60 @ 60 @ r
60 + 0 _ r
60 # 70 # l
70 @ 70 # l
70 1 99 1 p
70 0 99 0 p