Is there a non-halting program for every undecidable program? is undecidable the "same thing" as non-halting?


  • $\begingroup$ What is an "undecidable program" in this context? $\endgroup$ – Aaron Rotenberg Jan 19 at 1:05

The notion of an "undecidable program" doesn't make sense, for the same reasons I gave in response to your last question. It makes sense to talk about whether a language is decidable or undecidable. It doesn't make sense to talk about whether a program is decidable or undecidable. If you check the formal definition of decidable, you'll see that decidability is only defined for languages.

Undecidable is not the same as non-halting. Check the definition.


Your Answer

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

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