Есть такая штука — машина Тьюринга. Представляет собой простейший компьютер, однако писать под него хуже, чем на brainfuck'е. Решил я тут на днях побаловаться, но делать интерпретатор — не спортивно, да интерпретаторов этих — вагон. Потом меня посетила еще более странная идея — а чего бы не сделать это на Асме? (я его знаю паршиво, как раз решил потренироваться, так что сильно не пинайтесь).
Итак, сделаем генератор кода.
Принимает на вход файл, в котором перечислены подряд правила в виде
начальное_состояние начальный_символ конечное_состояние конечный_символ переход(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>nn");
fprintf(output, "char tape[0x7fffff];nn");
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 --)ntt*q = '#';n");
fprintf(output, "tfor (char * q = &tape[strlen(tape)]; q <= &tape[0x7fffff]; q ++)n");
fprintf(output, "tt*q = '#';n");
fprintf(output, "t_asmnt{n");
fprintf(output, "ttxor eax, eaxn");
fprintf(output, "tttmov eax, posn");
fprintf(output, "tttmov ecx, staten");
fprintf(output, "tttmov edx, final_statenn");
fprintf(output, "BEG:n");
fprintf(output, "ttcmp ecx, edxn");
fprintf(output, "tttje EXITnn");
}
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, "ttcmp ecx, %in", o_state);
fprintf(output, "tttjne R%in", number+1);
fprintf(output, "tttcmp [eax], '%c'n", o_char);
fprintf(output, "tttjne R%in", number+1);
fprintf(output, "tttmov [eax], '%c'n", d_char);
if (dir == 'r')
fprintf(output, "tttadd eax, 1n");
if (dir == 'l')
fprintf(output, "tttsub eax, 1n");
fprintf(output, "tttmov ecx, %in", d_state);
fprintf(output, "tttjmp ENDnn");
number++;
}
{
fprintf(output, "R%i:n", number);
fprintf(output, "ttjmp ENDnn");
fprintf(output, "END:n");
fprintf(output, "ttjmp BEGnn");
fprintf(output, "EXIT:nttnopnnt}nn");
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, "ttprintf("%%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
Вот сам алгоритм сложения
меняем его на _ и уходим влево
0 идем вправо до +, меняем на _
и начинаем складывать разряды
1x — правый разряд = x
2x — слева от _, разряд = x
n = null
l = 1
t = 2
5x — переносим ли 1 из предыдущего разряда
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
Автор: Delphist2008
