> It only becomes so if you can show that something computes them.
By definition nothing will ever compute an uncomputable function. That’s completely irrelevant to what I wrote.
By definition nothing will ever compute an uncomputable function. That’s completely irrelevant to what I wrote.
One can imagine that someone will find a model of computation that allows to compute more functions than a Turing machine. It's extremely unlikely, but nobody has proven that it is not possible. It may be that our universe is one such model.
The fact that the halting problem (or the nonperiodic tiling problem mentioned by someone else) is undecidable by Turing machines (and all of the other equivalent models of computation) provides an interesting philosophical tri-lemma:
1. There is a "fair" model of computation that is stronger than TMs. No such are known, and the evidence against them is that a bunch of other models turn out to be equivalent than TMs. There's a considerable amount of mathematical fame if you can find one, though.
2. TMs, etc., are the most powerful "fair" model of computation and there is no physically realizable "unfair" model[1,2]. This has some interesting implications for the "superintelligent AI" stuff. This is also the general consensus as far as I know.
3. Something out there is capable of performing "unfair" computations. (The Oracle of Delphi? Something woo-woo?) I think there are information theoretic/thermodynamic reasons for discarding this option, but what do I know?
[1] Note that a finite state machine is actually the most powerful known physically realizable form of computation. Your laptop is actually a FSM---it has a finite amount of memory and if you converted all of the mass in the universe into RAM it would still only have a finite amount of memory. All of the stronger models are mathematical abstractions.
There are computation models that are not obviously similar to computers; using DNA segments in a broth to solve instances of the Traveling Salesman problem, or soap bubbles (https://www.americanscientist.org/article/the-soap-film-an-a...). These are also equivalent to FSMs---there is only a finite amount of DNA or soap involved.
[2] The fact that functions exist (like the Halting Problem) that cannot be computed by TMs is not in itself terribly important beyond the implications of that tri-lemma above. Nor does the fact that essentially all functions are uncomputable by TMs (proof sketch: continuous numbers are transcendental with probability 1.0). I mean, the halting problem is a thing, so what? It only becomes important if something in the universe actually computes one of those functions that cannot be computed by TMs---that would rule out #2 and leave everyone scrambling for #1 or #3.
I’m under the impression that our computing machines are LBAs, not FSMs. Linear bounded automata are practically as powerful as Turing machines. Sipser gives a nice introductory treatment of the subject.
> It only becomes important if something in the universe actually computes one of those functions that cannot be computed by TMs
Or the universe isn’t a computer and doesn’t compute anything. In that case computation is just a human concept that reduces to moving pebbles (calculi) between various jars.
I'm a little uncomfortable with LBAs there because, while there is a limit to the storage based on the input size, there is no limit on the input size. It's a fine distinction, but that's the fun of theory.