Building an inline Turing Machine for C++

Introduction

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:

  1. sequential: to reach a specific place in the tape, you have to go through all the locations from the source to the destination.
  2. 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:

  1. traversing the memory
  2. reading from the memory
  3. writing to the memory
  4. 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).

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Typical Use-Cases

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.


Getting Started

The project is availible on github. Modular examples can be found here.


Cite:

Naveen Venkat (2016). Building an Inline Turing Machine for C++. Retrieved from http://www.naveenvenkat.com


Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s