Halting problem on no input

Assignment Help Basic Computer Science

Reference no: EM13963444

Halting Problem on No Input

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 to 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 speci?cally, can you write a program that reads a program text P as input, reads an integer n as input, and then 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 brie?y why you think not.

Reference no: EM13963444

Questions Cloud

Description and symptoms of parkinson disease : Provide a short description and the symptoms of Parkinson's disease or early detections, if any

What is the speed of sound in air at each temperature : The coldest and hottest temperatures recorded are: 134 degrees Farhenheit and -80 degrees Farhenheit.

Journalize the entry to record the current depreciation : Journalize the entry to record the current depreciation of the old equipment to the date of trade-in.

What is the minimum photon energy in electron volts : The metallic light-receiving surface within each tube is sensitive to light of wavelengths shorter than 605 x 10^2nm. The corresponding photon energy represents the minimum energy to eject a photoelectron. What is the minimum photon energy in elec..

Halting problem on no input : 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.

Ow does smart grid concept impact cybersecurity discussion : What do you think are the current issues facing our power grids to defend against attacks? And, how does the Smart Grid concept impact the cybersecurity discussion?

Different solutions to work through conflict in positive way : Tension and conflict continue and this problem is unresolved. Your assignment is to apply concepts from the course material correctly toward solving family and relationship problems by using three different solutions to work through conflict in po..

Employers do not pay payroll taxes on payments : Employers do not pay payroll taxes on payments made to independent contractors The FICA tax rates and taxable wage bases are exactly the same for employees and employers

What is the final total mass of the cup and its contents : A 150 gram Aluminum calorimeter cup contains 320 grams of water at 22 degrees Celsius. Steam at 100 degrees Celsius is routed into the calorimeter until the temperature of the cup and its contents reaches 50 degrees Celsius.

User Account

All Pages