If your conclusion implies the existence of computation beyond Turing machines, you should probably find an example or check your assumptions.
However, uncomputable functions not only exist, but are the overwhelming majority of functions. This suggests that at least some aspects of reality might only be accurately described by uncomputable functions. How could uncomputable functions exist in an entirely computable reality?
If you can show something a mathematician can do to compute a function, that cannot be emulated by a Turing machine, then you have demonstrated that Turing's definition does not capture the intuition and we get to start over with the theory of computation. So far, no one has been able to do that.
The existence of uncomputable functions is not itself a problem. 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.
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.
BTW - The field trying to deal with defining what exist means is called ontology:
This seems unlikely to me. Functions are a mathematical abstraction. Almost all of those functions are uncomputable, but what does the universe care? In what manner could the universe be organized in such a way as to depend on an uncomputable function?
Perhaps a better question for my above post would have been:
Can we imagine any empirical experiment to distinguish between a universe that depends on uncomputable functions and one that does not?
Edit: And if not, in what sense can the universe actually depend on an uncomputable function if we can't distinguish?
This follows from the fact that set of all Turing machines is countable (you can write an algorithm that lists all Turing machines), but set of real numbers is uncountable. So, by Cantor's diagonal argument you can prove that there are real numbers that can not be computed.
My guess is that universe can not depend on real numbers (i.e. real numbers are not real) because real numbers introduce infinity related breakdowns in physical models. For example, if there exist a physical state can encode arbitrary real number then that would allow to store infinite amount of information. But it is not possible to prove that something does not exist, see arguments related to Russell's teapot.
https://en.wikipedia.org/wiki/Computable_number
Thanks for the interesting discussion!
Such concepts cannot appear in a finite universe.