Simple_Universal_Turing_Machine.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.wikipedia.org/wiki/Wolfram%27s_2-state_3-symbol_Turing_machine"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "           A          B\n",
      "0  [1, R, B]  [2, L, A]\n",
      "1  [2, L, A]  [2, R, B]\n",
      "2  [1, L, A]  [0, R, A]\n"
     ]
    }
   ],
   "source": [
    "#define a 2-state, 3-symbol, Turing Machine with no halt state (one-dimensional tape)\n",
    "#this may not be the traditional 7-tuple TM design\n",
    "\n",
    "#states A and B\n",
    "#with three symbols (0,1,2) in language which correstpond to dataframe row index\n",
    "#Given a state(column) and read symbol(row)...\n",
    "#Each cell of the dataframe defines the TM rules for what to Write, how to Move, and what the next State should be\n",
    "d = {'A': [['1','R','B'], ['2','L','A'], ['1','L','A']], 'B': [['2','L','A'], ['2','R','B'], ['0','R','A']]} \n",
    "\n",
    "df = pd.DataFrame(data=d)\n",
    "print(df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "def run_Turing_machine(program, TM_rules, steps):\n",
    "    \n",
    "    #append enough tape to the left and right of the program defined by the user\n",
    "    #since we are only running it a fixed number of steps\n",
    "    #and the tape head can only move one space left or right at a time\n",
    "    #the program below is sufficient amount of \"blank\" tape to append\n",
    "    #technically, can 0 be considered \"blank\" if it is a symbol allowed in the program input language?\n",
    "    #from the Wolfram-Smith (2-state, 3-symbol) TM wikipedia page:\n",
    "    #\"More generally, almost all formal definitions of Turing machines differ in details irrelevant to their power, \n",
    "    #but perhaps relevant to what can be expressed using a given number of states and symbols; \n",
    "    #there is no single standard formal definition.\"\n",
    "    tape = program.rjust(steps + len(program),'0').ljust(2*steps + len(program),'0') \n",
    "    print(tape)\n",
    "    \n",
    "    #state initializtation of the Turing Machine\n",
    "    state = 'A'\n",
    "    \n",
    "    #set the index that will represent the tape head to start on the progam's first symbol\n",
    "    i = steps \n",
    "    \n",
    "    for counter in range(steps):\n",
    "            \n",
    "            current_rule_set = TM_rules[state][eval(tape[i])]\n",
    "            \n",
    "            #write\n",
    "            tape = tape[:i] + current_rule_set[0] + tape[i+1:]\n",
    "            \n",
    "            #move\n",
    "            if current_rule_set[1] == 'R':\n",
    "                i = i+1 \n",
    "            else:\n",
    "                i = i-1\n",
    "                \n",
    "            #next state    \n",
    "            state = current_rule_set[2] \n",
    "             \n",
    "            print(tape)\n",
    "    \n",
    "    return tape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000000012000000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000000022000000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000000122000000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000000102000000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000000101000000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000000111000000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000000112000000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000000112200000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000000111200000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000000121200000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000000221200000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001221200000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001021200000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001011200000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001111200000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001121200000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122200000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122000000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122010000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122012000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122022000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122122000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122102000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122101000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122111000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122112000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122112200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122111200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122121200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001122221200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001121221200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001111221200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000001211221200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000002211221200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000012211221200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000010211221200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000010111221200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000011111221200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000011211221200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000011221221200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000011222221200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000011222021200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000011222011200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000011222111200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000011222121200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000011222122200000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000011222122000000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000011222122010000000000000000000000000000000000000000000\n",
      "0000000000000000000000000000000000000000000000011222122012000000000000000000000000000000000000000000\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'0000000000000000000000000000000000000000000000011222122012000000000000000000000000000000000000000000'"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = ''\n",
    "run_Turing_machine(p,df,50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "#given the right program input p, this virtual universal Turing machine can do anything\n",
    "#it could simulate the operating system on your phone with all the apps you have running on it\n",
    "#for more fun, check out \"Digital Physics\" the movie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}