3 ms·

Turing designed his machines to capture "computation" as it is intuitionally understood: as something a mathematician, equipped with an unlimited supply of scra

Turing designed his machines to capture "computation" as it is intuitionally understood: as something a mathematician, equipped with an unlimited supply of scratch paper and pencils, could do. (The other equivalent apparatuses are provably equivalent, but it is harder to argue that they capture the correct intuition.) 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.

User23 5y ago
> 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.
- mcguire 5y ago
  On the contrary, uncomputable functions are uncomputable relative to a given model of computation. Many functions cannot be computed by finite state machines but can be by stack machines, and many that cannot be computed by FSMs or stack machines can be computed by Turing machines. (The interesting fact here is that Turing machines are equivalent to a large number of other models of computation, and no "fair" model of computation is known which is more powerful than Turing machines or those other equivalent models. ("Fair" means that the model of computation does not do something that a mathematician with pencil and paper could not also do---"unfair" models do exist but they do things like assuming you can do an unbounded amount of work in a finite number of steps.)) 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-analogue-computer 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.
  - User23 5y ago
    > Note that a finite state machine is actually the most powerful known physically realizable form of computation. Your laptop is actually a FSM 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.
    - mcguire 5y ago
      Note: not a computational theory guy. 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.
    - Stupulous 5y ago
      I assume you know more about this than me, so can you help me understand this or direct me somewhere? The universe is constantly taking its current state (or infinity of relativistic frames and/or multiverses) and outputting its next state/states. Is that not definitionally a specialized computer? Are my assumptions wrong?
- Isinlor 5y ago
  Not if the definition of computing and uncomputable are from two different models of computation. For example, there are functions uncomputable by finite state machine, but that can be computed by a Turing machine. 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.

User23 5y ago

> 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.

mcguire 5y ago
On the contrary, uncomputable functions are uncomputable relative to a given model of computation. Many functions cannot be computed by finite state machines but can be by stack machines, and many that cannot be computed by FSMs or stack machines can be computed by Turing machines. (The interesting fact here is that Turing machines are equivalent to a large number of other models of computation, and no "fair" model of computation is known which is more powerful than Turing machines or those other equivalent models. ("Fair" means that the model of computation does not do something that a mathematician with pencil and paper could not also do---"unfair" models do exist but they do things like assuming you can do an unbounded amount of work in a finite number of steps.)) 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-analogue-computer 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.
- User23 5y ago
  > Note that a finite state machine is actually the most powerful known physically realizable form of computation. Your laptop is actually a FSM 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.
  - mcguire 5y ago
    Note: not a computational theory guy. 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.
  - Stupulous 5y ago
    I assume you know more about this than me, so can you help me understand this or direct me somewhere? The universe is constantly taking its current state (or infinity of relativistic frames and/or multiverses) and outputting its next state/states. Is that not definitionally a specialized computer? Are my assumptions wrong?
Isinlor 5y ago
Not if the definition of computing and uncomputable are from two different models of computation. For example, there are functions uncomputable by finite state machine, but that can be computed by a Turing machine. 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.