Demonstration of adding 3 on a Turing machine
The alphabet for my Turing machine consists of the symbols 0,1 and *, and the states of that are START, ADD, DOUBLE_CARRY, CARRY, DOUBLE_OVERFLOW, OVERFLOW, RETURN, and HALT.
All of the instructions are listed below.
START * * L ADD
ADD 1 0 L DOUBLE_CARRY
ADD 0 1 L CARRY
DOUBLE_CARRY 1 1 L CARRY
DOUBLE_CARRY 0 0 L CARRY
DOUBLE_CARRY * 0 DOUBLE_OVERFLOW
CARRY 1 0 L CARRY
CARRY 0 1 R RETURN
CARRY * 1 L OVERFLOW
DOUBLE_OVERFLOW (ignored) 1 L OVERFLOW
OVERFLOW (ignored) * R RETURN
RETURN 1 1 R RETURN
RETURN 0 0 R RETURN
RETURN * * N HALT
the first part of the instruction represents the current state of the Turing machine, followed by the current cell content on the tape. The next means the value to write on the tape, which replaces the previous one. The remaining parts are the direction to move and new state to enter, respectively.
Execute the following program to see the detailed process of performing the operation of adding three to a given number. Entering any positive integer, and just with a push on the ‘Enter’ bottom on the keyboard, you will start a journey through the secrets of Turing machine.
In addition, in case you don’t have a computing device at hand, I provide some examples of the results of the program.
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define f(i,l,r) for(i=(l);i<=(r);i++)
#define ff(i,r,l) for(i=(r);i>=(l);i--)
using namespace std;
const int MAXN=10;
string map[MAXN+5];
int a;
int b[MAXN];
int pos,loc;
int arrow;
string sta;
void print()
{
int i;
f(i,loc,b[0]+2){
cout<<map[i]<<" ";
if(i<pos) arrow+=map[i].length()+1;;
}
cout<<map[b[0]+3]<<endl;
return;
}
void print_arrow()
{
int i;
f(i,1,arrow){
cout<<" ";
}
cout<<"↑"<<endl;
return;
}
void Init()
{
int i;
map[0]=map[1]="NULL";
map[2]="*";
loc=2;
cin>>a;
while(a){
b[++b[0]]=a%2;
a/=2;
}
map[2+b[0]+1]="*";
f(i,3,b[0]+2){
map[i]='0'+b[b[0]-i+3];
}
sta="START";
pos=b[0]+3;
return;
}
int main()
{
int i,j;
cout<<"请输入一个正整数："<<endl;
Init();
cout<<"START:"<<endl;
printf("%s\n","-------");
print();
print_arrow();
while(sta!="HALT"){
if(sta=="START"){
if(map[pos]=="*"){ // START * * L ADD
map[pos]="*";
pos--;
sta="ADD";
}
}
else if(sta=="ADD"){
if(map[pos]=="1"){ // ADD 1 0 L DOUBLE_CARRY
map[pos]="0";
pos--;
sta="DOUBLE_CARRY";
}
else if(map[pos]=="0"){ // ADD 0 1 L CARRY
map[pos]="1";
pos--;
sta="CARRY";
}
}
else if(sta=="DOUBLE_CARRY"){
if(map[pos]=="1"){ // DOUBLE_CARRY 1 1 L CARRY
map[pos]="1";
pos--;
sta="CARRY";
}
else if(map[pos]=="0"){//DOUBLE_CARRY 0 0 L CARRY
map[pos]="0";
pos--;
sta="CARRY";
}
else if(map[pos]=="*"){
//DOUBLE_CARRY * 0 DOUBLE_OVERFLOW
map[pos]="0";
pos--;
loc=pos;
sta="DOUBLE_OVERFLOW";
}
}
else if(sta=="CARRY"){
if(map[pos]=="1"){ // CARRY 1 0 L CARRY
map[pos]="0";
pos--;
sta="CARRY";
}
else if(map[pos]=="0"){ // CARRY 0 1 R RETURN
map[pos]="1";
pos++;
sta="RETURN";
}
else if(map[pos]=="*"){ // CARRY * 1 L OVERFLOW
map[pos]="1";
pos--;
loc=pos;
sta="OVERFLOW";
}
}
else if(sta=="DOUBLE_OVERFLOW"){
//DOUBLE_OVERFLOW (ignored) 1 L OVERFLOW
map[pos]="1";
pos--;
loc=pos;
sta="OVERFLOW";
}
else if(sta=="OVERFLOW"){
//OVERFLOW (ignored) * R RETURN
map[pos]="*";
pos++;
sta="RETURN";
}
else if(sta=="RETURN"){
if(map[pos]=="1"){ // RETURN 0 1 R RETURN
map[pos]="1";
pos++;
sta="RETURN";
}
else if(map[pos]=="0"){ // RETURN 0 0 R RETURN
map[pos]="0";
pos++;
sta="RETURN";
}
else if(map[pos]=="*"){
map[pos]="*"; // RETURN * * not_move HALT
sta="HALT";
break;
}
}
arrow=0;
print();
print_arrow();
}
return 0;
}