Машина Тьюринга и ассемблер

в 16:16, , рубрики: Алгоритмы, ассемблерная вставка, генератор кода, машина Тьюринга, ненормальное программирование, метки: , ,

Есть такая штука — машина Тьюринга. Представляет собой простейший компьютер, однако писать под него хуже, чем на 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

Вот сам алгоритм сложения

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

80 — ползем вправо до первого +,
меняем его на _ и уходим влево

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

Автор: Delphist2008

Поделиться

* - обязательные к заполнению поля