I was reading about the halting problem recently, there is a video on youtube where it tries to explain the halting problem easily (since it is complicated to explain).

So, (A,C & H) have different inputs, if we suppose that we can run the three inputs on a machine (x) using one encoding scheme (i.e encoding for chess = arthemtic), would that solve the halting problem ?

Is it a problem of encoding different forms of inputs to the machine itself, or is it a problem of always getting the right answer to the input ?

  • $\begingroup$ Whatever encoding you use, halting problem remains undecidable. $\endgroup$ – sashas Nov 7 '15 at 22:11
  • 1
    $\begingroup$ I would disagree with you on this, if it's an encoding problem, then i can make it always halts. $\endgroup$ – Henry akpo Nov 7 '15 at 22:22
  • 3
    $\begingroup$ Thats what I said. Halting problem is undecidable irrespective of the encoding. You should have a look at how halting problem is proved to be undecidable , the proof nowhere assumes a specific encoding. $\endgroup$ – sashas Nov 7 '15 at 22:28
  • 3
    $\begingroup$ Maybe the video lecture is confusing you. There are dozens of other accounts on the web, some of which you might find more convincing. $\endgroup$ – Yuval Filmus Nov 7 '15 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.