Building a compiler Part. 3 of 4 Turing Machine

"The limits of my language mean the limits of my world."

— Ludwig Wittgenstein

Now that we have an idea about the basic structure of LEX and YACC files and what each does, let us understand what instructions our programming language will support and why that is in theory enough to write a program to solve any problem which can so be done by any other programming language out there.

Turing Machine

We take inspiration from the most minimalistic (and also complete) machine, standard Turing Machine which consists of an infinitely long tape with cells which hold data (analogous to modern CPU memory) and a read write head which points to the current cell.

Single tape Turing machine

Mathematically, it is a 7-tuple (Q, Σ, Γ, δ, q₀, B, F) where

Q is the set of all states

Σ is the set of input symbols

Γ is the set of tape symbols (input, output and B blank symbol)

δ is the transition function, given by δ : Q x Γ -> Q x Γ x {L, R}

q₀ is the start state

B is the blank symbol

F is the set of all final states

A Turing machine can be an acceptor meaning returning if the input string belongs to a given language or a transducer meaning producing a result by performing some transformation to input string.

Let us take an example of 0ⁿ1ⁿ language acceptor, for this the TM is as follows:

Turing machine for language acceptance

Here, the steps followed are:

1. If 0 is encountered write as X and move right, else if Y is encountered, goto step 4, else if B, goto step 5

2. Move right until 1 is encountered, goto step 3 when scanned

3. Return to the left end of the string, goto step 1

4. Run through all the Y until B is encountered, when B is scanned goto step 5

5. Accepted state

The final read/write pointer will be located at end of string

Now lest take an example of a transducer, where we will be transforming a binary representation of a number to its ones and twos complement

Turing machine as a transducer

Here we rewrite 0s in place of 1s and vice versa for 1s complement, for 2s' complement we observe the pattern that all bits from the LSB to the leftmost 1 are unchanged and any other bit to the left of it is reversed, the machine does the same.

Variations

Based on the number of directions in which the R/W pointer can move and the number of tapes and R/W pointers, the Turing machine can be classified into:

1. Muti-tape TM: Multiple tapes for input, compute and output

2. Multi-head TM: Multiple pointers

3. Multi-tape Multi-head TM

4. K-dimension TM: Tape can be 2D and operations can include up and down

Completeness

So, what does it mean by saying a machine is Turing complete? How do we even know that all problems solvable by a computer of highest compute capacity can be solved by a TM? The answer is that there is no proof otherwise, meaning no one has come up with a problem which can be solved by a computer program, but not a TM. Hence the Church-Turing thesis:

Anything that can be computed by any algorithm can be computed by a Turing machine.

In our programming language we will be implementing a TM, with the instructions

print        print contents of the cell to stdout

read         read a value from stdin to the cell

while       loop over a set of commands

if             conditional statement

right        move RW pointer to right

left          move RW pointer to left

inc          increase value at current cell by an integer

dec         decrease value at current cell by an integer

halt         terminate program

This takes inspiration from BrainF**k, which is based on only 8 instructions and is the minimalistic compiler. We will be writing a compiler which converts these instructions into assembly which will then be assembled by NASM and linked using ld.