2
$\begingroup$

From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and various other sources I've read).

But then doesn't this mean that all partial functions are not Turing-computable? (and by extension not computable at all regardless of computational model due to the Church–Turing thesis?)

But this seems rather silly given that most real-world functions are partial, and many clearly computable...

This confuses me greatly, any help would be appreciated.

A) Is termination part of the definition of Turing-computability? (and computability in general)

B) How does non-termination fit into the concept of computability?

$\endgroup$
3
$\begingroup$

So, some of the functions you talk about might be technically uncomputable, but the problem can become decidable with trivial modifications.

For example, consider the function taking a natural number to its predecessor. If you define it partially, nothing comes before $0$, and there's no algorithm to solve this, because there isn't a correct answer. The algorithm can't find it because it doesn't exist.

But, if you make a choice, and say that the predecessor of $0$ is $0$, or some special character, now you have a total function, from which you can extract your partial one.

I suspect most of the "real world" partial functions you talk about fall into this category. You just define a special "fail" output for any inputs where there's no defined output.

What the definition of computability is talking about really is whether a Turing Machine halts for all inputs. If it halts on all inputs, the result is whatever is on the tape, so it's considered total. If it doesn't, then it's partial.

For your specific questions:

Yes, termination is absolutely part of the definition of computability. Otherwise, everything is decidable: I make a Turing machine that runs forever, and since it doesn't ever give a wrong answer, I've "solved" the problem. Given this, solving a problem without termination is pretty meaningless.

A function is computable if there exists a Turing Machine computing it which halts on all inputs.

How does non-termination fit in? Basically, we don't allow non-termination, because of the problem I mentioned above. There is a special class of problems, called "recursively-enumerable" or "semi-decidable" decision (yes/no) problems, where the Turing Machine halts on all "YES"-valued inputs, but might not halt on all NO-valued inputs.

Another thing to watch here is your quantifiers. A problem is decidable if there exists a Turing Machine that solves it and always halts. I can make a Turing Machine solving addition that sometimes loops forever, but that doesn't mean that addition is undecidable, because there exists another machine that solves it and always halts.

$\endgroup$

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.