Prihlásenie Registrácia  

Turingov stroj

Turing machines, first described by Alan Turing, are simple abstract computational devices intended to help investigate the extent and limitations of what can be computed. To read more about Turing machines theory, visit Stanford site or this site.

Our turing machine simulator uses following 5-tuple formulation: State0ld, SymbolOld, SymbolNew, Movement, StateNew, where:

  • If StateOld = ActualState and SymbolOld = ActualTapeSymbol then machine will write SymbolNew over ActualTapeSymbol, change ActualState to StateNew and move head according to Movement.
  • Movement can be either R - move to the right, L - move to the left or N - don't move at all.
  • There can't be any two instruction with same StateOld and SymbolOld.
  • State can be any string up to 32 characters.
  • Symbol is only one character. Allowed characters will be defined in problem descriptions.
Some examples:
  • s0 0 1 N s0
    Change 0 to 1, leave the state and don't move
  • s0 0 0 R s1
    Don't change symbol, change state to s1 and move to the right
  • s1 1 0 L s0
    Change symbol from 1 to 0, change state from s1 to s0 and move to the left
Program for Turing machine:
s0 1 1 R s1
s1 1 1 R s2
s2 1 1 N sOK

This program ends in state sOK if there are at least three 1 symbols.

You can assume, that tape is infinite. But it is possible, that for some problems, there will be constraints. It is possible to use left constraint - tape will be infinite only to the right, or to use both left and right constraints - tape will be finite and its length is same as memory limit for that problem.

All numbers are natural or zero (no negative numbers) and are unary encoded. So 0 = '1', 1 = '11', 2 = '111' etc. So the number n will be encoded as n+1 successive 1s.

There are several facts, that can be assumed true if not defined in problem description:

  • Starting state is s0
  • Head is positioned on the first character of tape
  • Tape is infinite and except input contains only zeros
  • All numbers are unary encoded and have one zero symbol between them
  • Maximal count of states is 2048
  • Maximal count of instructions is 2048
  • Time limit is number of allowed steps
  • Memory limit is number of used (visited) tape blocks

Simulátor si môžeš stiahnuť tu:

júl 2017

PoUtStŠtPiSoNe
     12
3456789
10111213141516
17181920212223
24252627282930
31      

august 2017

PoUtStŠtPiSoNe
 123456
78910111213
14151617181920
21222324252627
28293031