Geekly Articles each Day
📜 ⬆️ ⬇️

Turing machine and assembler

There is such a thing - the Turing machine . It is the simplest computer, but writing under it is worse than on brainfuck. I decided to indulge here the other day, but the interpreter is not a sport, but these interpreters are a car. Then an even stranger idea came to me - why not do it on Asma? (I know him lousy, just decided to practice, so do not kick much).


So, let's make a code generator.

Accepts an input file that lists the rules in a row as
Initial_State Initial_Symbol Final_State Final_Symbol Transition (l / r / p - stay in place).
There is nothing special there, so I bring it as it is, without comments:
')
Generator
#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); }



It turns out.cpp with this code:
(comments added separately)

Result
 #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(); }



The input is input.txt

1 line - input data, in this case -
1010 + 10 + 110110101 + 11101101011110101 + 1 + 10110100101100110110101 + 10101011011011

then the initial state, the state of completion and the initial position of the head (actuator)
80 99 0

Now it remains only to compile the finished application - take
VS20XX x86 Native Tools Command Prompt

pushd d: \ turing
cl out.cpp / nologo


run
out.exe


as expected, we get

10111000110000101000111

Here is the addition algorithm itself

Pretty messy notes during the writing process.
80 - we crawl to the right to the first +,
change it to _ and go left

0 go right to +, change to _
and begin to add discharges
1x - right digit = x
2x - to the left of _, bit = x

n = null
l = 1
t = 2

5x - whether we transfer 1 from the previous digit


Addition in 2 system
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 lr
0 t 0 tr
0 n 0 nr
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 nr
20 1 0 lr
20 # 0 nr
20 t 20 tl
20 l 20 ll
20 n 20 nl
20 @ 20 @ l

21 0 0 lr
21 1 0 tr
21 # 0 lr
21 t 21 tl
21 l 21 ll
21 n 21 nl
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

Source: https://habr.com/ru/post/154669/

More articles:


All Articles