Assignment: Theoretical Models as Practical Computers

1. Programming a Turing Machine.

Use the online Turing machine simulator to program a Turing machine (i.e., create the transition function for one) so as to accept any input of this form:
10*1

In the notation above, the symbol "*" means "0 or more of the preceding character." Any of the following should be an accepted input:
11
101
1001
(etc.)

The following are examples of inputs that should be rejected: 111 10101 1101

Please submit your Turing machine program (transition function) in text following the syntax required for the online simulator.

2. Programming with the Lambda Calculus.

Use the online lambda calculus interpreter to express the addition functions and test it on the values (3, 2) and (2,3), using Church numbers. Verify that 3 + 2 = 2 + 3 according to the lambda calculus.

Your submission should be a text file with two lines: the first line holds the expression for 3 + 2, the second for 2 + 3. I should be able to copy each of your lines into the online interpreter, reduce it, and see the right answer as the last line.

Please submit your initial lambda expression in text using the syntax required for the online interpreter.