Suppose you are given a function Halt that can be used to determine whether a program that requires no input halts. To make this concrete, assume that you are writing a C or Pascal program that reads in another program as a string. Your program is allowed to call Halt with a string input. Assume that the call Halt returns true if the argument is a program that halts and does not read any input and returns false if the argument is a program that runs forever and does not read any input. You should not make any assumptions about the behavior of Halt on an argument that is not a syntactically correct program.

Can you solve the halting problem by using Halt ? more specifically, can you write a program that reads a program text P as input, reads an integer n as input, and decides whether P halts when it reads n as input? You may assume that any program P you are given begins with a read statement that reads a single integer from standard input. This problem does not ask you to write the program to solve the halting problem. It just asks whether it is possible to do so.

If you believe that the halting problem can be solved if you are given Halt, then explain your answer by describing how a program solving the halting problem would work. If you believe that the halting problem cannot be solved by using Halt, then explain breifly why you think not.