All problems solved by standard today's general purpose computer can be solved by standard Turing machine.As general purpose computer can't do more than Turing machine so The Turing machine halting problem must also be unsolved by today's general purpose computer.How can I realize the fact that halting problem can't be solved by todays general purpose computers.

  • $\begingroup$ What do you mean "realize the fact"? Are you asking how to prove it? The quickest two options are A) prove that a computer (i.e. a RAM machine) can be simulated by a TM, or B) Prove that a RAM machine can simulate another RAM machine, and follow the diagonalization argument used in Turing's original proof. $\endgroup$ – Shaull Mar 9 '14 at 6:36
  • $\begingroup$ no I am not asking for the proof.I just want to know how Turing machine halting problem can occur in our general use of computers for implementing algorithms,which can't be solved. $\endgroup$ – tanmoy Mar 9 '14 at 6:40
  • $\begingroup$ I don't really understand what you're asking. Can you perhaps rephrase? What is "general use"? What algorithms are you referring to, for example? $\endgroup$ – Shaull Mar 9 '14 at 7:21
  • $\begingroup$ I just want to know how Turing machine halting problem can occur in RAM machine. $\endgroup$ – tanmoy Mar 9 '14 at 9:35
  • $\begingroup$ The problem is not in the machine, it is about what the machine can do. $\endgroup$ – vonbrand Mar 9 '14 at 13:26

The halting problem is the question of whether a program $B$ halts on and some given input $x$. It is impossible to create a program that decides the halting problem, so the effect is that, whatever program $A$ you create, there will exist some program $B$ and input $x$ such that $A$ will not tell correctly whether $B$ halts on input $x$.

| cite | improve this answer | |
  • $\begingroup$ is program B a particular type of program or any kind of program? $\endgroup$ – tanmoy Mar 10 '14 at 4:48
  • $\begingroup$ What exactly do you mean by that? The only thing you know a priori is that such a program $B$ exists, you know nothing else about $B$. The classical proof that the halting problem is undecidable explicitly constructs such a program $B$ (look it up, it's not technical at all, just takes some time to get your head around), but others may exist. $\endgroup$ – fkraiem Mar 10 '14 at 5:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.