Turing Machine

Introduction

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.

The machine operates on an infinite memory tape(though i have used a finitely large number) divided into discrete cells. Each cell contains a symbol from some finite alphabet. The tape head is positioned at a cell and can read or write a symbol on the cell. The tape head can move left or right one cell at a time or even stay at that cell. The machine is in a particular state from a finite set of states. The machine can change state and move the tape head based on the symbol read from the tape.

The machine is said to accept an input string if it halts in an accepting state. The machine is said to reject an input string if it halts in a non-accepting state. The machine is said to loop if it never halts.

Steps to create algo for this machine

  1. start by giving the machine a name (optional)
    name: even length checker

  2. then give the machine initial tape sequence
    note: the tape sequence should not have space you can specify empty block by '_'
    tape: 0101010101

  3. then give the machine initial state
    note: statenames should of single word
    initialState: oddPosition

  4. then give the machine accepting state
    acceptingState: even

  5. then give the machine rules or transition functions
    syntax for defining transition functions is
    ( currentState, currentSymbol ) : ( nextState, updateSymbol, directionOfHeadMovement )
    transition functions work as follows

    • if the current state is currentState and the current symbol is currentSymbol then the machine will change its state to nextState, update the current symbol to updateSymbol and move the tape head in the direction specified by directionOfHeadMovement
    • currentSymbol can take following values
      • specified character symbol
      • '*' : any symbol except empty block
      • '_' : empty block
      note: currentSymbol should be a single character
    following is the example of transition functions for even length checking turing machine
    transitionFunctions: {
    (evenPosition, *): (oddPosition, *, R)
    (oddPosition, *): (evenPosition, *, R)
    (evenPosition, _): (odd, _, S)
    (oddPosition, _): (even, _, S)
    }

  6. now the script should look like this
    name: even length checker

    tape: 0101010101
    initialState: oddPosition
    acceptingState: even

    transitionFunctions: {
    (evenPosition, *): (oddPosition, *, R)
    (oddPosition, *): (evenPosition, *, R)
    (evenPosition, _): (odd, _, S)
    (oddPosition, _): (even, _, S)
    }
    and you can run the machine by clicking the run button