11/10/2021, 21:52 Coding tool: Computing Theory (2150)
Coding tool
I mentioned to someone recently that it may be helpful to have a tool which will translate between the encoded form of a Turing machine (using the encoding on page 4 of the Tutorial 5 exercises (https://rmit.instructure.com/courses/79563/files/20012625?wrap=1) ). So I have written some rudimentary Prolog code to do this.
To access this, download the file coding.pl. (https://rmit.instructure.com/courses/79563/files/20258355?wrap=1) (https://rmit.instructure.com/courses/79563/files/20258355/download?download_frd=1) Save this file somewhere appropriate, open SWI-Prolog and consult this file.
To encode a particular machine, you will first need to specify one. There are some predefined machines you can use for this (numbered 0 to 4 inclusive like any good computer scientist :-))
For example, to encode machine 1, use the following. ?- machine(1,M), encode(M, C).
This generates the following output. Note that the internal representation of the machine requires quotation marks around B, L and R. We use B to represent the blank.
Machine transitions: delta(q0, B) = [q1,B,R] delta(q1, 1) = [q1,0,R] delta(q1, 0) = [q1,0,R] delta(q1, B) = [q2,B,R] delta(q2, 0) = [q3,0,R] delta(q3, B) = [q2,B,L] delta(q2, 1) = [q4,1,R] Transition delta(q0, B) = [q1,B,R] encoded as 101110110111011
Transition delta(q1, 1) = [q1,0,R] encoded as 1101101101011
Transition delta(q1, 0) = [q1,0,R] encoded as 110101101011
Transition delta(q1, B) = [q2,B,R] encoded as 11011101110111011
Transition delta(q2, 0) = [q3,0,R] encoded as 111010111101011
Transition delta(q3, B) = [q2,B,L] encoded as 111101110111011101
Transition delta(q2, 1) = [q4,1,R] encoded as 111011011111011011
Machine encoded as 000101110110111011001101101101011001101011010110011011101110111011001110101 111010110011110111011101110100111011011111011011000
M = [t(q0, ‘B’, q1, ‘B’, ‘R’), t(q1, 1, q1, 0, ‘R’), t(q1, 0, q1, 0, ‘R’), t(q1, ‘B’, q2, ‘B’, ‘R’), t(q2, 0, q3, 0, ‘R’), t(q3, ‘B’, q2, ‘B’, ‘L’), t(q2, 1, q4, 1, ‘R’)],
C= “00010111011011101100110110110101100110101101011001101110111011101100111010 1111010110011110111011101110100111011011111011011000” .
For the reverse process, you will need to specify a correctly formatted code, which will then be interpreted as a machine. Again, there are some pre-defined codes you can use if you wish. There are 6 codes, numbered 0 to 5; numbers 0 to 4 inclusive are correctly formatted, and number 5 is incorrectly formatted.
For example, to decode code 2, use the following.
https://rmit.instructure.com/courses/79563/pages/coding-tool
1/3
11/10/2021, 21:52 Coding tool: Computing Theory (2150)
?- code(2,C), decode(C,M).
This generates the following output.
Encoded Machine is 000111011011111011011001111011101110111010011101011110101100110111011101110 110011010110101100110110110101100101110110111011000
Formatting is correct
The string 111011011111011011 encodes the transition delta(q2, 1) = [q4,1,R]
The string 111101110111011101 encodes the transition delta(q3, B) = [q2,B,L]
The string 111010111101011 encodes the transition delta(q2, 0) = [q3,0,R]
The string 11011101110111011 encodes the transition delta(q1, B) = [q2,B,R]
The string 110101101011 encodes the transition delta(q1, 0) = [q1,0,R]
The string 1101101101011 encodes the transition delta(q1, 1) = [q1,0,R]
The string 101110110111011 encodes the transition delta(q0, B) = [q1,B,R]
Machine is delta(q2, 1) = [q4,1,R] delta(q3, B) = [q2,B,L] delta(q2, 0) = [q3,0,R] delta(q1, B) = [q2,B,R] delta(q1, 0) = [q1,0,R] delta(q1, 1) = [q1,0,R] delta(q0, B) = [q1,B,R]
C= “00011101101111101101100111101110111011101001110101111010110011011101110111 0110011010110101100110110110101100101110110111011000”,
M = [t(q2, 1, q4, 1, ‘R’), t(q3, ‘B’, q2, ‘B’, ‘L’), t(q2, 0, q3, 0, ‘R’), t(q1, ‘B’, q2, ‘B’, ‘R’), t(q1, 0, q1, 0, ‘R’), t(q1, 1, q1, 0, ‘R’), t(q0, ‘B’, q1, ‘B’, ‘R’)] .
To encode your own machine, use something like this. I suggest that you don’t type this directly but copy it from a text file that you edit.
?- encode( [t(q0, ‘B’, q1, ‘B’, ‘R’), t(q1, 1, q1, 0, ‘R’), t(q1, 0, q1, 1, ‘R’), t(q1, ‘B’, q2, ‘B’, ‘R’), t(q2, 0, q3, 0, ‘R’), t(q3, ‘B’, q3, ‘B’, ‘L’), t(q2, 0, q4, 1, ‘R’)], C).
This generates the following output.
Machine transitions: delta(q0, B) = [q1,B,R] delta(q1, 1) = [q1,0,R] delta(q1, 0) = [q1,1,R] delta(q1, B) = [q2,B,R] delta(q2, 0) = [q3,0,R] delta(q3, B) = [q3,B,L] delta(q2, 0) = [q4,1,R] Transition delta(q0, B) = [q1,B,R] encoded as 101110110111011
Transition delta(q1, 1) = [q1,0,R] encoded as 1101101101011
Transition delta(q1, 0) = [q1,1,R] encoded as 1101011011011
Transition delta(q1, B) = [q2,B,R] encoded as 11011101110111011
Transition delta(q2, 0) = [q3,0,R] encoded as 111010111101011
Transition delta(q3, B) = [q3,B,L] encoded as 1111011101111011101
Transition delta(q2, 0) = [q4,1,R] encoded as 11101011111011011
Machine encoded as 000101110110111011001101101101011001101011011011001101110111011101100111010 1111010110011110111011110111010011101011111011011000
C= “00010111011011101100110110110101100110101101101100110111011101110110011101 01111010110011110111011110111010011101011111011011000” .
https://rmit.instructure.com/courses/79563/pages/coding-tool
2/3
11/10/2021, 21:52 Coding tool: Computing Theory (2150)
You can also decode your own code, using something like what follows. Again, copy your input from a text file (unless you are really confident about not missing a single character!).
?- decode(“0001011101101110110011011011010110011010110101100110111011101101100 111010111101110110011110111011011101001101110111101011000”, M).
This generates the following output.
Encoded Machine is 000101110110111011001101101101011001101011010110011011101110110110011101011 1101110110011110111011011101001101110111101011000
Formatting is correct
The string 101110110111011 encodes the transition delta(q0, B) = [q1,B,R]
The string 1101101101011 encodes the transition delta(q1, 1) = [q1,0,R]
The string 110101101011 encodes the transition delta(q1, 0) = [q1,0,R]
The string 1101110111011011 encodes the transition delta(q1, B) = [q2,1,R]
The string 11101011110111011 encodes the transition delta(q2, 0) = [q3,B,R]
The string 11110111011011101 encodes the transition delta(q3, B) = [q1,B,L]
The string 1101110111101011 encodes the transition delta(q1, B) = [q3,0,R]
Machine is delta(q0, B) = [q1,B,R] delta(q1, 1) = [q1,0,R] delta(q1, 0) = [q1,0,R] delta(q1, B) = [q2,1,R] delta(q2, 0) = [q3,B,R] delta(q3, B) = [q1,B,L] delta(q1, B) = [q3,0,R]
M = [t(q0, ‘B’, q1, ‘B’, ‘R’), t(q1, 1, q1, 0, ‘R’), t(q1, 0, q1, 0, ‘R’), t(q1, ‘B’, q2, 1, ‘R’), t(q2, 0, q3, ‘B’, ‘R’), t(q3, ‘B’, q1, ‘B’, ‘L’), t(q1, ‘B’, q3, 0, ‘R’)] .
Just to show what happens with incorrectly formatted codes, see below.
?- decode(“0001011101101110110011011011010110011010110101100110111011101101100 11101011110111011001111011101101110100110111011110101100”, M).
This generates the following output.
Encoded Machine is 000101110110111011001101101101011001101011010110011011101110110110011101011 110111011001111011101101110100110111011110101100
Formatting is incorrect — I don’t understand this machine
Enjoy!
https://rmit.instructure.com/courses/79563/pages/coding-tool
3/3