1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Halting problem

  1. Aug 9, 2006 #1
    can somnbody pls give me a simple example to show halting problem

    pls

    thanx
     
  2. jcsd
  3. Aug 9, 2006 #2

    0rthodontist

    User Avatar
    Science Advisor

    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?
     
  4. Aug 9, 2006 #3
    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
     
  5. Aug 9, 2006 #4

    0rthodontist

    User Avatar
    Science Advisor

    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."
     
    Last edited: Aug 9, 2006
  6. Aug 9, 2006 #5
    the link above is not found,
    pls re - posted

    thanx
     
  7. Aug 9, 2006 #6

    0rthodontist

    User Avatar
    Science Advisor

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Halting problem
  1. Problem with circuit (Replies: 2)

  2. Statics Problem (Replies: 2)

  3. Truss problem (Replies: 1)

  4. Statics Problem (Replies: 1)

  5. Units problem (Replies: 2)

Loading...