Turing Machines and Machine Schemas
-
09-10-2019 - |
سؤال
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?
المحلول
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.