Turing Machines and Machine Schemas

Question

Arthur Dent, using space age technology not yet available on earth developed an algorithm which determines if a TM M1 halts or not when started on a blank tape. But then later, he discovered that the meaning to life, the universe, and everything is 42.

(a) [5] Given a TM M2, prove that Arthur can determine if M2 halts or not on the input 42 using the program he already developed which determines if a TM M1 halts or not when started on a blank tape. If you create a new TM in your proof, give its machine schema.

(b) [5] Suppose there is a program which is faster than Arthur's but it answers the question of whether a TM M2 halts on input 42. Explain how Arthur can use this algorithm to determine if some TM M1 halts when started on a blank tape. If you create a new TM in your proof, give its machine schema.

(c) [5] We proved in class that that the problem of determining if a TM M halts when started on a blank tape is not decidable. Is it part (a) or part (b) which can be used to prove that it is also undecidable to determine if a TM M halts on input 42?

Can anyone help me decipher what my prof is talking about here?

Answer 1

Welcome to some really complicated computer science theory. Try starting here: http://en.wikipedia.org/wiki/Halting_problem

Google Turing Machine as well if you're not familiar with that.