# What makes a function computable?

It seems to me, at the moment, that I don't understand where the line is drawn between "computability" and being incomputable. The main question is, is it the ability to be "solved" only by trying out every possible combination?

I know there are probably "even worse" things where it is not even possible to define "every possible combination", but those are obviously over the line.

I have a few fringe examples I would like to discuss.

1 - If there was a program called HaltsInUnder100Operations, one could make that decides whether any program x, given an input i, halts in under n operations (say 100 operations as it might need to be a certain goldilocks range). It seems like it could be possible to analyse the program and find the answer from there. But if you put it through the same test as the general halting problem that Turing proved was impossible, it could run into the same logical difficulty.

The problem would not directly be that it is incomputable, but instead that there are probably some programs you cannot tell will halt in under n operations, without running them. Is it that itself that makes it incomputable?

If you tried to test that program, it would possibly take more than n operations to give the result.

If you design a set of programs where it is possible to tell how many steps they will take, then the program HaltsInUnder100Operations(x,i) will not itself be in that set of programs either, so that can't work.

2 - In Numberphile where they are solving a^3 + b^3 + c^3 = 33, they say equations like these officially "could be undecideable" (incomputable?), and yet they are finding solutions left and right by trying every possible combination. Maybe they mean that there might be no "formula" for finding the solutions.

3 - Similarly, the travelling salesman problem is a famous example, but can be solved for small enough sets by trying every possible combination.

And the busy beaver problem (a prime example of "incomputable") has been solved for up to 4 states in binary, again by trying every possible program and finding which ones halt or loop - but I heard there is a point (1919 states?) where it can't be solved in this way. Maybe there are infinitely changing results for that which technically do not halt but there is no way of telling that they won't at some extremely large finite number? So, given a never-ending amount of time to get the answer, the answer would never be found.

4 - The prime numbers may seem "computable" at first glance, but then there is no known formula that can "efficiently compute" them (i.e. you plug in n and you get out the nth prime number). So what side of the line is that on?

5 - Pi (or the digits thereof) is considered to be "computable", even though it would take infinity to find all the digits.

6 - If you were to write down some numbers "at random" (without using a formula) or generate them based on random inputs, would these be "incomputable"? It could be argued that being possibly affected by stochastic processes makes them incomputable, though finite (because you are going to stop at some point). And yet if you had a computer generate all decimals of length n (where n is the length of your randomly generated decimal) then one of those would be the same decimal. So it is again a blurred line.

With these possible incomputable finite problems (if they are indeed incomputable), that makes me wonder if the basic foundation of computability is itself "incomputable" by some definition? For example, the formulae themselves which had to require some exhaustive testing, even if doing so was very easy. Computability would then be something that is based on established formulae, and then the ability to get further answers using those, without needing an exhaustive search. Maybe it just means anything that can be reached with "shortcuts" of some type?

• While every problem that can be solved by inspecting a finite number of options is computable, the notion of computability is different from this property. In particular, we cannot claim that simply because a problem would be solvable by inspecting an infinite number of instances, it can only be solved that way. In contrast, the definition of computability does allow to prove that some problems cannot be computed. – Discrete lizard Mar 24 at 16:52
• Note that the travelling salesman problem is decidable, even if you mention it as a famous undecidable problem! We do not know of any efficient (polynomial time) way to decide it, but there are exptime algorithms, so it is definitely decidable. – chi Mar 24 at 17:10
• It feels like you are writing a suspense story where conflicting clues and ideas abound. It seems you want to be philosophically exploratory and mathematically precise at the same time. There is one simple answer to your question, picking up a textbook such as introduction to theory of computation by Michael Sipser. Or follow the Wikipedia entry on computability – Apass.Jack Mar 24 at 18:24
• I fail to understand how it is in any way "story-like". – user101783 Mar 25 at 19:35

## 1 Answer

[is] the basic foundation of computability is itself "incomputable" by some definition?

Nope. There is a precise mathematical definition for the concept of "computable". We say that a function $$f:\{0,1\}^* \to \{0,1\}$$ is computable if there exists a Turing machine that computes it. It only makes sense to apply this concept to functions. It doesn't make sense to ask whether an apple is computable, or whether the color green is computable, or whether the foundation of computability is computable -- none of those are functions, and the notion "computable" is only defined for functions.

I suggest finding a good textbook on computability and the theory of computing, and studying the material there to learn about computability theory. It sounds like you might be trying to guess what it might mean based on examples, informal descriptions, analogies, first principles, and maybe a little bit of speculation. I suspect that none of those are going to be a very effective way to learn a mathematical subject.

• There must be something wrong with my logic - you just said it is exempt from the notion of computable, which "by some definition" means incomputable, by my logic. Even if the official / actual / real definition has to relate to something that can also "be a function". – user101783 Mar 25 at 19:33
• @lmnyx, Suppose Alice asks you "see this apple right here -- is it happy?" and you say "no, it doesn't make sense to apply the concept 'happy' to apples, as apples don't have an emotional state" and Alice responds by saying "ok, so if this apple is not happy, then I shall conclude that this apple is unhappy.".... what would you say to that? – D.W. Mar 25 at 20:02
• I thought about that or something very similar, and yes, the apple is conclusively "not happy" according to the law of excluded middle. Of course one could use that to infer that the law of excluded middle is wrong, and that there is another category (in this case "exempt"). That's a perfectly good conclusion, probably. – user101783 Mar 26 at 20:53
• @lmnyx, This might now be getting beyond the scope of this site, but in my example, it's incorrect to say "the apple is happy", and incorrect to say "the apple is unhappy". In your situation, it's incorrect to say "the foundation is computable" and incorrect to say "the foundation is incomputable". – D.W. Mar 27 at 1:38
• (Saying "the apple is not happy" is ambiguous -- it's not clear whether that would mean "not(the apple is happy)" or "the apple is not(happy)". The former is potentially invalid in formal logic but people will probably understand what you mean, the latter is incorrect. It's ambiguous and confusing enough that you risk confusing yourself, let alone others. So try to avoid that in this context. Same for "the foundation is not computable" -- try to avoid that, too.) – D.W. Mar 27 at 1:39