Reference no: EM1310545

1) Develop a two-track Turing machine which compares the two binary strings and decides if they are equal. If strings are equal, machine halts in some of the fixed state; if they are not equal, the machine halts in some other fixed state. Solve the same problem utilizing the Turing machine (regular Turing machine).

2)  Prove the following given statement: Any computation which can be carried out utilizing a regular Turing machine can be done using the two-track Turing machine. Based on the parts (a) and (b), build an argument for the following statement: Any computation which can be carried out utilizing a two-track Turing machine can be done utilizing a regular Turing machine.