Source and (Brief) Overview by GRAHAM STALKER-WILDE <[email protected]>

Java source code �Graham Stalker-Wilde 1996

Used and Distributed on the Alan Turing website maintained by Andrew Hodges,
http://www.turing.org.uk/turing/

---------------------------------------------------------------------------

TuringMachineApplet.class
This Assembles the components. It creates a TuringMachine object, reads the
Tape, Alphabet and State parameters from the PARAM tags, and controls the
animation, stepping and resetting.
It creates an animation thread, and uses a StatesPainter and TapePainter to
display the state of the machine after every step.
This could be rewritten to allow viewers to edit or create machines. (Tapes,
symbol sets, State sets.)

source: TuringMachineApplet.java
----------------------------------------------------------------------------
TuringMachine.class
This mantains the internal state of the machine. It contains a vector of
states, knows what the current state is (by index) and current position on
the tape.
It does not know the details of any of the states.
When asked to "Step" all it does is pass the current state the tape position
and tell it (the State) to act.

source: TuringMachine.java
----------------------------------------------------------------------------
Tape.class
Our friend the bidirectional infinite tape.
Just a vector of Integers. The TapeIter does all the work.

source: Tape.java
----------------------------------------------------------------------------
TapeIter.class
This takes care of the bidirectional infinite bit. It is an iterator over a
Tape. It maintains a position on the tape, knows what symbol it is at, and
how to move left or right.

source: TapeIter.java
----------------------------------------------------------------------------
State.class
An array of M * N 3-tuples, where N is the number of characters in the
symbol set (Alphabet) and M is the number of states. The first N 3-tuples
represent state 0, etc.
Each 3-tuples describes the symbol to write, the direction to move, and the
new state (which may be STOP).
The first 3-tuple of set J of N 3-tuples (yeuch) describes what state J does
on reading symbol 0, etc.
This is the ugliest code, I think. This class also takes care of parsing the
applet state parameters.

source: State.java
----------------------------------------------------------------------------
StateException.class
One of these gets thrown if the parameter describing a state is screwed, or
if the state set is inconsistent (this happens a lot when I try to write
state sets!)

source: StateException.java
----------------------------------------------------------------------------
StatesPainter.class
This is a rudimentary way of depicting the state set and the current state.
This is the class one would rewrite to draw pretty graphic state
representations.
As long as the interface was the same (and it is a subclass of Component)
nothing else would be affected.

source: StatesPainter.java
----------------------------------------------------------------------------
TapePainter.class
A rudimentary depiction of the tape, including the current position on the
tape.
As with the StatesPainter, this could be rewritten without impacting the
rest of the code.

source: TapePainter.java
----------------------------------------------------------------------------
Alphabet.class
This is used solely by the TapePainter and the StatesPainter as a mapping
from the number of the symbol to the actual symbol to display. This way all
states and tapes can be internally described using numerical indexes (symbol
0, 1, 2, 3, ...) but the applet can display any character set)

source: Alphabet.java
----------------------------------------------------------------------------

// package TuringMachine;

import java.awt.*;
import java.applet.*;
import java.io.*;
import java.util.*;

public class TuringMachineApplet extends Applet implements Runnable
{
   private TuringMachine m_theMachine;
   private TapePainter   m_tapePainter;
   private StatesPainter m_statesPainter;
   private Button        m_btnStep;
   private Button        m_btnAnimate;
   private Button        m_btnReset;

   private Alphabet      m_alphabet;

   private long          m_lSleep;  // how long to sleep for

   private boolean       m_fAnimate;
   private Thread        m_thread;

   public void init()
   {
       m_theMachine = new TuringMachine();

       readAlphabet();
       readTapeParameters();
       readStateParameters();
       readSleepParameter();

       // save original state information for Restart
       m_theMachine.saveState();
       m_fAnimate = false;

       m_tapePainter   = new TapePainter(m_theMachine, m_alphabet);
       m_statesPainter = new StatesPainter(m_theMachine, m_alphabet);
       m_btnStep       = new Button("Step");
       m_btnAnimate    = new Button("Run");
       m_btnReset      = new Button("Reset");





       // Symantec's ugly ol' component layout

       //{{INIT_CONTROLS
       setLayout(null);
       addNotify();
       resize(insets().left + insets().right + 252, insets().top + insets().bottom + 274);
       label1=new Label("State : Read : Write : Move : NewState");
       add(label1);
       label1.reshape(insets().left + 7,insets().top + 38,217,15);

       add(m_tapePainter);
       m_tapePainter.reshape(insets().left + 7,insets().top + 8,256,15);

       m_statesPainter.setFont(new Font("Courier",Font.PLAIN,10));
       add(m_statesPainter);
       m_statesPainter.reshape(insets().left + 12,insets().top + 67,214,103);

       add(m_btnAnimate);
       m_btnAnimate.reshape(insets().left + 133,insets().top + 180,63,23);

       add(m_btnStep);
       m_btnStep.reshape(insets().left + 42,insets().top + 180,63,23);

       add(m_btnReset);
      m_btnReset.reshape(insets().left + 42,insets().top + 210,63,23);
       //}}


       m_tapePainter.display();
       m_statesPainter.display();


   }

   public void stop()
   {
       if (m_thread != null )
       {
           m_thread.stop();
       }
       m_thread = null;
   }

   public void run()
   {
       while ( m_fAnimate )
       {
           if ( ! m_theMachine.isStopped() )
           {
               step();
               try
               {
                   Thread.sleep(m_lSleep);
               }
               catch ( InterruptedException e )
               {
                   // Do nothing
               }
           }
           else
           {
               m_fAnimate = false;
               m_btnAnimate.setLabel("Run");
               m_btnReset.enable();
           }
       }
   }

   public String getAppletInfo()
   {
       return "Demo of Turing Machine. rev 0.0\nGraham Stalker-Wilde <[email protected]>";
   }


   public String[][] getParameterInfo()
   {
       String info[][] = {
         {"Sleep",          "int",      "delay between tape moves for animated mode in milliseconds (default is 500)"},
         {"Tape",          "String",    "Starting Tape for Turing Machine, comma delimited, eg 1,0,1,1,0,0"},
         {"SymbolSet",     "String",    "characters to be used in the tape as single string, eg \" -12+=\" "},
         {"StartPosition", "int",       "Starting position in tape, from LHS"},
         {"State0",        "String",    "0-M parameters representing states as comma delimited strings"} ,
         {"State1",        "String",    "each parameter contains 3N values, where N is the number of symbols in the symbol set"} ,
         {"State2",        "String",    "each triplet (from i =0 to i = N-1) represents state behaviour on reading symbol i"} ,
         {"State3",        "String",    "i.e. write-on-ith-symbol,move-on-ith-symbol,newState-on-ith-symbol"},
         {"State4",        "String",    "write-on-ith-symbol is a numeral, j, representing the jth symbol in the symbol set"},
         {"State5",        "String",    "movements are L, R or N (for None), new state can be -1 (for Stop)"},
         {"State5",        "String",    "Note: if a non-existent state or symbol is referenced the applet will not run."}

       };
       return info;
   }


  public boolean action(Event evt, Object ob)
   {
       if ( evt.target == m_btnStep )
       {
           step();
           return true;
       }
       else if (evt.target == m_btnAnimate )
       {
           m_fAnimate = !m_fAnimate;
           if (m_fAnimate)
           {
               m_btnAnimate.setLabel("Stop");
               m_btnReset.disable();
               m_thread = new Thread(this);
               m_thread.start();
           }
           else
           {
               m_btnAnimate.setLabel("Run");
               m_btnReset.enable();
           }
           return true;
       }
       else if ( (evt.target == m_btnReset) && !m_fAnimate)
       {
           // Reset original state information
           m_theMachine.restoreState();
           m_btnAnimate.enable();
           m_btnStep.enable();
           showStatus("State: " + m_theMachine.CurrentState());

           m_tapePainter.display();
           m_statesPainter.display();
          return true;
       }
       return false;
   }

   private void step()
   {
           try
         {
               if ( !m_theMachine.isStopped() )
               {
                   m_theMachine.step();
                   m_tapePainter.display();
                   m_statesPainter.display();
                   if (!m_theMachine.isStopped())
                   {
                       showStatus("State: " + m_theMachine.CurrentState());
                   }
                   else
                   {
                       showStatus("State: Stopped");
                       m_btnAnimate.disable();
                       m_btnStep.disable();

                   }
               }
               else
              {
                   showStatus("State: Stopped");
               }
           }
           catch (StateException e)
           {
               showStatus("Error: " + e);
           }
   }


   private void readAlphabet()
   {

       String st = getParameter("Alphabet");
       if (st != null)
       {
           m_alphabet = new Alphabet(st);
       }
       else
      {
           m_alphabet = new Alphabet("-1");
       }
   }

   private void readStateParameters()
   {
       for (int i =0; true; i++)
       {
           Integer I = new Integer(i);
           String stState = "State"+I;
           try
           {
               String st = getParameter(stState);
               if (st == null)
               {
                   break;
               }

               State state = new State(st);
               m_theMachine.addState(i, state);
           }
           catch (StateException se)
           {
               break;
           }
       }
   }

   private void readTapeParameters()
   {
       // ugly stuff
       Tape tp = new Tape();
       TapeIter ti= new TapeIter(tp);

       try
       {
           String stZERO = "0";

           String stTape = getParameter("Tape");
           StringTokenizer st = new StringTokenizer(stTape, ", ");


           int i = 0;
            while (st.hasMoreTokens() )
           {
               ti.write( new Integer (st.nextToken()) );
               ti.moveRight();
               i++;
           }
           int nStart = 0;
           String stStartingPosition = getParameter("StartPosition");
           if ( stStartingPosition != null)
           {
               try
               {
                   Integer startingPosition = new Integer(stStartingPosition);
                  nStart = startingPosition.intValue();
               }
               catch(Exception e)
               {
                   // do nothing, nStart will be 0
               }
           }

           for ( ; i > nStart; i--)
           {
               ti.moveLeft();
           }
           m_theMachine.setTape(tp, ti);

       }
       catch (Exception e)
       {
           // if tape is bad then we're dead
       }
   }

   private void readSleepParameter()
   {
       m_lSleep = 500;   // default
       String stSleep = getParameter("Sleep");
       if ( stSleep != null)
       {
           try
           {
               m_lSleep = Long.parseLong( stSleep );
           }
           catch(Exception e)
           {
               // do nothing, default will be 500
           }
       }
   }
   //{{DECLARE_CONTROLS
   Label label1;
   //}}

}



// package TuringMachine;
import java.util.*;

class TuringMachine
{
   private Tape m_Tape;
   private TapeIter m_CurrentPosition;

   // for restore
   private Tape     m_SavedTape;
   private TapeIter m_SavedPosition;

   private Vector  m_States;
   private Integer m_CurrentState;

   public TuringMachine()
   {
       m_Tape = new Tape();
       m_CurrentPosition = new TapeIter(m_Tape);
       m_States = new Vector();
       m_CurrentState = new Integer(0);
   }

   public void addState(Integer nStateNumber, Vector state)
   {
       State st = new State( state);
       pad(nStateNumber.intValue());

       m_States.setElementAt(st, nStateNumber.intValue());
   }

   public boolean isStopped()
   {
       return m_CurrentState.intValue() == State.STOP.intValue();
   }
   private void pad(int n)
   {
       while (m_States.size() <= n)
       {
           m_States.addElement(new Integer(0));
       }
   }

   public void setTape(Tape tp)
   {
       m_Tape = new Tape(tp);
       m_CurrentPosition = new TapeIter(m_Tape);
   }

   public void setTape(Tape tp, TapeIter ti)
   {
       m_Tape = new Tape(tp);
       m_CurrentPosition = new TapeIter(ti);
   }

   public void addState(int nStateNumber, State st)
   {
       pad(nStateNumber);
       m_States.setElementAt(st, nStateNumber);
   }

   public void step() throws StateException
   {
       if ( ((Integer)m_CurrentState).intValue() != State.STOP.intValue())
       {
           State st = (State)m_States.elementAt( m_CurrentState.intValue());
           m_CurrentState = st.act(m_CurrentPosition);
       }
   }
   public Integer CurrentState()
   {
       return m_CurrentState;
   }

   public Enumeration states()
   {
       return m_States.elements();
   }

   public TapeIter clonePosition()
   {
       return new TapeIter(m_CurrentPosition);
   }

   // not working
   public void saveState()
   {
       m_SavedTape = new Tape(m_Tape);
       m_SavedPosition = new TapeIter(m_CurrentPosition);
   }

   // not working
   public void restoreState()
   {
       m_Tape = new Tape(m_SavedTape);
       m_CurrentPosition = new TapeIter(m_SavedPosition);
       m_CurrentState = new Integer(0);
   }

}


// package TuringMachine;

import java.util.*;

/** Tape is bidirectionally infinite
   It is accessed by creating iterators,
   any number of which might be active on the
   Tape at one time.
   Iterators are used to read and write to the tape.

   One will be used by the TapePainter, another will
   represent the Current Position of the machine on
   the tape and will be used for read write and movement

   tape is represented as a vector with (conceptually)
   odd numbers increasing the right, even numbers increasing
   to the left. i.e.

    ... 12 10 8 6 4 2 0 1 3 5 7 9 11 13 ....
*/
public class Tape
{
   // these constants should be moved to an Alphabet structure
   // and accessed by ordinal (alph[0], alph[1], etc.)
   // this allows machines to be defined with any combination of
   // symbols

   private Vector m_tape;

   public Tape()
   {
       m_tape = new Vector(40);
   }

     public Tape(Tape tp)
   {
       m_tape = new Vector();
       for (Enumeration e = tp.m_tape.elements() ; e.hasMoreElements() ;)
       {
           m_tape.addElement( new Integer( ( (Integer)e.nextElement() ).intValue() ) );
       }
   }
   protected void writeAt(Integer i, int nIndex)
   {
       while (m_tape.size() <= nIndex)
       {
           m_tape.addElement(new Integer(0) );
       }
       m_tape.setElementAt(i, nIndex);
   }

   protected Integer readAt(int nIndex)
   {
       try
       {
           return (Integer) m_tape.elementAt(nIndex);
       }
       catch (ArrayIndexOutOfBoundsException e)
       {
           return new Integer(0);
       }
   }
}



// package TuringMachine;


import java.util.*;

public class TapeIter
{

   private Tape m_theTape;
   private int  m_nIndex;

   public TapeIter(Tape tp)
   {
      m_theTape = tp;
      m_nIndex = 0;
   }

   /** references the same tape and indexes the
   same position
   Not thread safe.*/
   public TapeIter(TapeIter ti)
   {
      m_theTape = new Tape(ti.m_theTape);
      m_nIndex = ti.m_nIndex;
   }

   /** indexes map to tape positions like this
   ... 12 10 8 6 4 2 0 1 3 5 7 9 11 13 ....
   so indexing them requires some fairly ugly arithmetic
   */
   public void moveLeft()
   {   // ugly bit
       if (m_nIndex%2 == 0)
       { // even index
           m_nIndex += 2;
       }
       else
       {   // odd index
           m_nIndex -= 2;

           if (m_nIndex < 0 )
           {
               m_nIndex = 0;
           }
       }
   }
   /** @see TapeIter#moveLeft()
   */
   public void moveRight()
   {  // ugly bit
      if ( m_nIndex%2 == 1)
      {    // odd index
           m_nIndex += 2;
      }
      else
      {
          m_nIndex -= 2;
           if (m_nIndex < 0)
          {
               m_nIndex = 1;
           }
      }
   }

   /** usage iter.read();
   reads at current position
   */
   public Integer read()
   {
       return m_theTape.readAt(m_nIndex);
   }

   /** usage iter.write( new Integer(1));
   */
   public void write(Integer s)
   {
        m_theTape.writeAt(s, m_nIndex);
   }

}


// package TuringMachine;

import java.util.*;

public class State
{
   // belongs here
   public static final Integer STOP = new Integer(-1);

   public static final Integer LEFT  = new Integer(0);
   public static final Integer RIGHT = new Integer(1);
   public static final Integer NONE  = new Integer(2);

   Vector m_state;

   public State(Vector state )
   {
      setProperties( state );
   }

   /** this will be used to createStates from PARAM strings
   */
   public State (String st) throws StateException
   {
       StringTokenizer strtok = new StringTokenizer(st, ", ");
       try
       {
           Vector v = new Vector();
           String stNext = strtok.nextToken();

           while ( stNext != "" )
           {
              Vector vi = new Vector(3);

               vi.addElement( new Integer( stNext ) );

               String stTemp = strtok.nextToken();
               vi.addElement( stTemp.equals("L") ? State.LEFT :
                              stTemp.equals("R") ? State.RIGHT : State.NONE );

               vi.addElement(new Integer ( strtok.nextToken() ) );

               v.addElement(vi);
               if (strtok.hasMoreTokens())
               {
                   stNext = strtok.nextToken();
               }
               else
               {
                   stNext = "";
               }
           }
           setProperties( v );
       }
       catch (Exception e)
       {
           throw new StateException("Bad State");
       }
   }

   public void setProperties(Vector state)
   {
       // performs a deep copy of state
       m_state = new Vector();

       for (Enumeration e = state.elements(); e.hasMoreElements(); )
       {
           Vector vi = new Vector(3);
           Vector v = (Vector)e.nextElement();

           vi.addElement(new Integer(((Integer)v.elementAt(0)).intValue()));
           vi.addElement(v.elementAt(1)); // note no copy, this is an enumeration
           vi.addElement(new Integer(((Integer)v.elementAt(2)).intValue()));
           m_state.addElement(vi);
       }
   }

   public Integer act(TapeIter ti) throws StateException
   {
       Vector v = (Vector)m_state.elementAt( ti.read().intValue() );
       ti.write((Integer)v.elementAt(0));

       if ( State.LEFT == (Integer)v.elementAt(1))
       {
           ti.moveLeft();
       }
       else if ( (Integer)v.elementAt(1) == State.RIGHT )
       {
           ti.moveRight();
       }
       else
       {
           // Do nothing
       }
       return (Integer)v.elementAt(2);
   }

   /** returns a vector describing the internal representation of the
   states. This is designed for read only access by State painters
   */
   public Vector describe()
   {
       return m_state;
   }

}

// package TuringMachine;


public class StateException extends Exception
{
   public StateException(String st)
   {
       super(st);
  }
}

// package TuringMachine;

import java.awt.*;
import java.util.*;

public class StatesPainter extends List
{
   private TuringMachine m_theMachine;
   private Alphabet alphabet;

   public StatesPainter(TuringMachine tm, Alphabet alph)
   {
       m_theMachine = tm;
       alphabet = alph;
   }

   public void display()
   {
       // clear() doesn't seem to work
       delItems(0, countItems() - 1);



       int i = 0;
       int nCurrent = m_theMachine.CurrentState().intValue();
       for ( Enumeration e = m_theMachine.states(); e.hasMoreElements(); i++ )
       {
             State state = (State)e.nextElement();


              String stMarker;
              Vector v = state.describe();
              if (i == nCurrent)
              {
                   stMarker = "**";
              }
              else
              {
                   stMarker = "  ";
              }
              // we loop through each entry for the state
              for (int j = 0; j < alphabet.size(); j++)
              {
                  String stSpacer = "   ";
                  Vector vi = (Vector) v.elementAt(j);
                  String st = "";
                  st =  "  "  +
                        i + stSpacer +
                        alphabet.getSymbol( new Integer(j) ) + stSpacer  + // read
                        alphabet.getSymbol(vi.elementAt(0)) + stSpacer + // write
                       ( (Integer)vi.elementAt(1) == State.LEFT  ? "L" :
                         (Integer)vi.elementAt(1) == State.RIGHT ? "R" : "-" )  + stSpacer;// move
                  if ( ((Integer)vi.elementAt(2)).intValue() == State.STOP.intValue() )// new state
                  {
                       st = st +  "Stop" + " " + stMarker;
                  }
                  else
                  {
                       st = st + (Integer)vi.elementAt(2)  + " " + stMarker;
                  }
                  addItem(st);
              }
       }
       makeVisible(alphabet.size() * nCurrent);
   }
}


// package TuringMachine;

// a more sophisticated TapePainter would be like this:
// have an off-screen image buffer
import java.awt.*;

public class TapePainter extends Label
{
   int     nCharsShown;
   private TuringMachine m_theMachine;
   private Alphabet alphabet;

   public TapePainter(TuringMachine tm, Alphabet alph)
   {
       super();
       m_theMachine = tm;
       alphabet = alph;
       nCharsShown = 8;
       // the number of characters shown will be 2* nCharsShown + 1;
   }

   public void display()
   {
       TapeIter  ti = m_theMachine.clonePosition();
       for (int i = 0; i < nCharsShown ; i++)
       {
           ti.moveLeft();
       }
       String st = "";

       for (int i = 0; i < nCharsShown ; i++)
       {
           st += alphabet.getSymbol(ti.read());
           st += "   ";
           ti.moveRight();
       }
       // show current position
       st += "[";
       st += alphabet.getSymbol(ti.read());
       st += "]";
       ti.moveRight();

       for (int i = 0; i < nCharsShown ; i++)
       {
           st += "   ";
           st += alphabet.getSymbol(ti.read());
           ti.moveRight();
       }

       super.setText(st);
   }
}



import java.awt.*;
import java.util.*;

public class Alphabet
{
   String m_st;

   public char getSymbol(Object obj)
   {
       return  m_st.charAt(((Integer)obj).intValue() );
   }

   public Alphabet(String st)
   {
       m_st = st;


  }
   public int size()
   {
       return m_st.length();
   }
}

You are viewing proxied material from gopher.quux.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.