- #1

NoahsArk

Gold Member

- 220

- 21

- TL;DR Summary
- Help understanding the halting problem.

Hello. I've been trying to understand the halting problem, which is confusing for me on many levels.

1) I'm not even sure what the halting problem is asking? Is it asking whether or not there are certain problems that computers can't solve, or is it asking whether or not there are certain truth's that computer's will never be able to prove. If it's the later, then it's getting philosophical because how can we know something is true to begin with if it can't be proven?

2) What is the solution saying? My understanding is that it proves that there are some kinds of questions that computers will never be able to solve, even computers that one day are thousands of times faster than today's.

3) The way I see the Halting problem being defined is "Can we write a program that will determine whether any other program will halt or run forever". Thinking of modern programming languages, I don't see why this isn't possible. In python, for example, code which loops has the "while" key word. If we want to see whether or not a program loops forever, we can just scan the language and see if it has any looping keywords. There must be something more fundamental about this problem that I'm missing.

4) I also don't understand Turing's solution to the halting problem which concludes such a program can't be written. He first assumed that such a program could be written (call the first program Hal). He then imagines a second program (Barry) that does the opposite of everything Hal does. Now he imagines that Hal runs with Barry as it's input. If Hal states that Barry halts, Barry runs forever and vice versa. Turing says this proves we can never write a program which will determine whether or not another program halts or goes on forever.

My understanding is that we'd want a program like Hal, which can determine whether another other program will halt or run forever, to exist to be able to solve problems like Goldbach's conjecture. I don't see how this trick of creating a contradictory program means that programs like Hal couldn't solve such problems. The real problem seems that if a program were to solve Golbach's conjecture, it would have to keep testing even numbers and seeing if any of them fail to have two prime numbers that add up to that number. It might one day find a number like that, but how could we prove in advance whether or not one day it will?

So I am confused not only about the solution, but about the nature of the problem itself. Adding to the confusion is the fact that when Turing was writing about the halting problem, there were no computers or computer programs like there are today, and by "computer" and "program" he meant something more abstract which I can't define.

Thanks

1) I'm not even sure what the halting problem is asking? Is it asking whether or not there are certain problems that computers can't solve, or is it asking whether or not there are certain truth's that computer's will never be able to prove. If it's the later, then it's getting philosophical because how can we know something is true to begin with if it can't be proven?

2) What is the solution saying? My understanding is that it proves that there are some kinds of questions that computers will never be able to solve, even computers that one day are thousands of times faster than today's.

3) The way I see the Halting problem being defined is "Can we write a program that will determine whether any other program will halt or run forever". Thinking of modern programming languages, I don't see why this isn't possible. In python, for example, code which loops has the "while" key word. If we want to see whether or not a program loops forever, we can just scan the language and see if it has any looping keywords. There must be something more fundamental about this problem that I'm missing.

4) I also don't understand Turing's solution to the halting problem which concludes such a program can't be written. He first assumed that such a program could be written (call the first program Hal). He then imagines a second program (Barry) that does the opposite of everything Hal does. Now he imagines that Hal runs with Barry as it's input. If Hal states that Barry halts, Barry runs forever and vice versa. Turing says this proves we can never write a program which will determine whether or not another program halts or goes on forever.

My understanding is that we'd want a program like Hal, which can determine whether another other program will halt or run forever, to exist to be able to solve problems like Goldbach's conjecture. I don't see how this trick of creating a contradictory program means that programs like Hal couldn't solve such problems. The real problem seems that if a program were to solve Golbach's conjecture, it would have to keep testing even numbers and seeing if any of them fail to have two prime numbers that add up to that number. It might one day find a number like that, but how could we prove in advance whether or not one day it will?

So I am confused not only about the solution, but about the nature of the problem itself. Adding to the confusion is the fact that when Turing was writing about the halting problem, there were no computers or computer programs like there are today, and by "computer" and "program" he meant something more abstract which I can't define.

Thanks