Understanding the Halting Problem: A Simple Example

[teng125]

can somnbody pls give me a simple example to show halting problem

pls

thanx

 

[0rthodontist]

What exactly do you want an example of? A program which we don't know whether it halts? Or are you just looking for the standard proof of the halting problem's noncomputability?

 

[teng125]

a simple example program which explains a program which we don't know whether it halts and also a simple example for the standard proof of the halting problem's noncomputability

thanx

 

[0rthodontist]

Well, I don't know what an "example" would be for the standard proof of the halting problem's noncomputability. If you want the proof itself you can find it on wikipedia.

For an example of a program which may or may not halt, consider the 3n + 1 problem. (find an explanation at http://acm.uva.es/p/v1/100.html) . Now write a program which does the following:

i <- 0
start:
i <- i + 1
run the 3n + 1 algorithm starting from i until one of the following two things happen:
if the sequence entered a finite loop of numbers that repeat over and over and do not include 1, return 0
otherwise if the sequence generated by that algorithm terminated in 1, goto start

You can turn any unsolved problem in mathematics into this kind of "example" of the halting problem. For example you could do: "Iterate through all legal proofs in ZFC. If one of them is a proof for Goldbach's conjecture, return 0. Otherwise keep iterating."

 

[teng125]

the link above is not found,
pls re - posted

thanx

 

[0rthodontist]

http://acm.uva.es/p/v1/100.html
for some reason the parenthesis was considered part of the link