Как стать автором
Обновить

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

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


Сложение в 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
Теги:
Хабы:
-3
Комментарии 10
Комментарии Комментарии 10

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн