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 of undecidability 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?