Skip to content

Instantly share code, notes, and snippets.

@wridgers
Created December 10, 2011 18:18
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save wridgers/1455834 to your computer and use it in GitHub Desktop.
Save wridgers/1455834 to your computer and use it in GitHub Desktop.
Rules for C/C++ Turing Machine contest
-- RULES --
~ should be a single .c or .cpp file
~ must be written in C or C++ (C is a subset of C++)
~ entry must compile (of course)
~ must be a deterministic 1-tape TM as defined below
~ should accept the input string as a command-line argument (see Links for how to do this)
~ upon input, the program should output state:tape followed by a new line
~ the program should terminate once the state becomes H,Y, or N.
~ the delta function should be changeable (no hard coding the procedure!)
~ submissions should have a 'default' delta function that reverses the input string
--- DEFINITION OF TURING MACHINE ---
~ a deterministic 1-tape Turing Machine
~ tape alphabet is 0,1 and the blank symbol '-' (dash)
~ set of states should be characters a-z (lower case), S, H, Y, N
~ S is the starting state
~ H is the halting state
~ Y is the accepting state
~ N is the rejecting state
--- EXAMPLES ---
$ ./tm 01100
H:00110
$
$ ./tm 00101001100
H:00110010100
$
--- COUNTING ---
~ you can test your entry here: http://mindfuzz.net/count/
~ we are counting *all* characters, this includes spaces and '\n'
--- SUBMISSION ---
~ final TM's should be presented on the first available day in term 2
--- LINKS ---
~ http://stackoverflow.com/questions/3697299/passing-command-line-arguments-in-visual-studio-2010
~ http://mindfuzz.net/count/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment