1
$\begingroup$

The halting problem concerns programs which take input. By framing the halting problem on the diagonal argument it is clear why this is so.

What about programs with no input, constant functions.

Can it always be determined if they terminate?

$\endgroup$

1 Answer 1

5
$\begingroup$

No, given any program-input pair $(T,x)$ (formally a Turing machine and a word in $\Sigma^*$ for some alphabet $\Sigma$) you can construct a Turing machine with no input that first writes down $x$ and then simulates $T$.

It follows that the problem is undecidable.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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