Automata and Computability Question

1. In the notation used in this question, the symbols bi stand for bit values. The symbol stands for blank. Thus on the Turing machine tape indicated below, the non-blank portion of the tape is a sequence of bit values. Design a Turing machine M which, when started in a configuration of the form q0 b1 b2 . . . bn

in state q0 over the cell containing b1, eventually halts in state qhalt over the symbol bn on the tape configuration qhalt bn bn1 . . . b1

Thus, your Turing machine reverses the sequence of bit values within which it begins. Note that your Turng machine in various states will have to handle three possible tape symbols: 0, 1, and . You may add auxiliary symbols to the tape alphabet.

2. Implement and test your Turing machine at https://alistat.eu/online/turingmachinesimulator

You may have to modify your syntax to suit the conventions of the online simulator

Note : By modifying the state transition function of a Turing machine from a function of type : Q Q {L, R} to a function of type : Q 2 {Q{L, R}} we obtain nondeterministic Turing machines.