Turing Machines are mathematical abstractions of a computing systems. Suppose you are given an input string of letters of a given alphabet, and you want to do some computation on it, then given enough time and memory, a Turing Machine can do the job for you. The only caveat is, the language that you want to compute upon should be “computable”. What this means is, there are certain languages that are not computable in reasonable time by a Turing Machine. Such languages are called “hard”, because it is hard to write an algorithm to compute in reasonable time. This is a very abstract version of what a Turing Machine is. Let us explore it in brief.
Turing Machines in Brief
In a Turing Machine, we define an input tape, which is some form of a memory device. Consider the cassette tapes that were introduced around the 1960s. We call such a memory model as a sequential linear memory, because:
- sequential: to reach a specific place in the tape, you have to go through all the locations from the source to the destination.
- linear: because the traversal is only in one “linear” dimension.
Now, given this memory unit, we need a computing unit that could perform operations on this memory. We achieve this by defining a computing machine that has the capability of:
- traversing the memory
- reading from the memory
- writing to the memory
- make decisions based on some algorithm / set of rules
Given these four abilities (or operations), our machine will be able to compute anything (almost!).
Defining the Turing Machine in C++
The infinite tape is handled by allocating an arbitrarily large array of integers. Simply put, we use the array as an abstract version of the infinite tape, and reallocate memory as required. For this demonstration, we fix a length for the array (buffer size), and point to the current cell using a data pointer variable (DP).
- Traversing the memory: We can only move left or right on the tape. Thus we define two functions _L() and _R() that decrease and increase the DP. We map the function calls to the macros L and R to avoid repeated parenthesis.
- Reading the memory: Accessing the memory can be simply done by de-referencing the data pointer (*DP). This is equivalent to the current data value (CDV). We also define a macro O to output the CDV.
- Writing to the memory: We can modify the memory by either incrementing / decrementing the current cell using macros U and D respectively, or take an input directly into the cell using I.
- Make decisions based on rules: To have a control structure, we define a LOOP macro that simply loops the block of code following it, until the data pointed by the DP is 0 at the beginning of an iteration.
These functions are summarized in the following table:
|L||Move the pointer to the left (Left)|
|R||Move the pointer to the right (Right)|
|U||Increment the current pointed cell by 1 (Up)|
|D||Decrement the current pointer cell by 1 (Down)|
|I||Read a single character into the current cell (Input)|
|O||Print the character at the current cell (Output)|
|LOOP||The block following it will be looped until a 0 occurs at the current cell when loop condition is checked|
Ability to perform complex algorithms
Since the framework is written in C++, we can leverage the function definition capabilities of the language. In version 0.2, we also implement a macro TM that let’s us define a void function as a turing machine that works directly on the tape. Since the tape is global, we do not worry about the inputs and the outputs of the function, and keep empty parameters. Some examples can be found here.
This framework lets us run an inline Turing Machine in the C++ code, adding meta coding capabilities. This Turing Machine can be used as an auxiliary memory. Some examples can be, using it as an inline version control system, using it for policy agnostic programming, or even writing complex Turing Machines in a modular design.
Naveen Venkat (2016). Building an Inline Turing Machine for C++. Retrieved from http://www.naveenvenkat.com