3 ms·
The halting problem for any given program is either true or false, so a program that prints true or a program that prints false is a valid function that produce
by empath75 2y ago
The halting problem for any given program is either true or false, so a program that prints true or a program that prints false is a valid function that produces an answer for that function. You don't know _which_ one is the correct function, but it exists. The thing that's not computable is a function that produces an answer given any arbitrary program as input.
It's the difference between:
does_program_x_halt():
return true
and
does_program_halt(x):
if x halts:
return true
else:
return false
The important distinction is that the first function is a constant that takes no input, and the second function is not a constant and takes a program as input. The first is computable(although we may not know right now if "return false" or "return true" is the correct function, one of the two is), the second is not.
I think an important clarification to make is whether or not we currently know how to write a function isn't relevant to whether it's computable or not.