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.

• 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

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:

• Win32 binary + source ZIP
• Source ZIP
• Source TAR.BZ2