5 ms·

>If this is so, then we can conclude that a Turing machine also cannot possess AGI, because it fails to fulfil a necessary condition thereof. If your conclusio

>If this is so, then we can conclude that a Turing machine also cannot possess AGI, because it fails to fulfil a necessary condition thereof. If your conclusion implies the existence of computation beyond Turing machines, you should probably find an example or check your assumptions.

simonh 5y ago
My conclusion or theirs? I’m not sure what you mean.
- Stupulous 5y ago
  I'm responding to their claim in agreement with you.
User23 5y ago
By definition the computable functions are those that can be computed by a Turing machine or equivalent apparatus, so talking about "computation beyond Turing machines" is incoherent. 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?
- CrazyStat 5y ago
  Do uncomputable functions actually "exist" in reality in any meaningful sense, or are they just mathematical abstractions?
  - doganulus 5y ago
    You need to start with the assumption that an infinite set exists (Axiom of Infinity) for uncomputable functions (and other weird mathematical things). Such concepts cannot appear in a finite universe.
  - Isinlor 5y ago
    You are asking a question that does not have an answer, because "exist" is not well-defined. But if you want to know whether an arbitrary JavaScript in your browser will stop or not, well you can not know that for all scripts people can throw at you. In this sense uncomputable functions do exist. BTW - The field trying to deal with defining what exist means is called ontology: https://en.wikipedia.org/wiki/Ontology https://en.wikipedia.org/wiki/Ontology
    - CrazyStat 5y ago
      The JavaScript argument doesn't really get at the point I was trying to make (poorly, probably). The parent was arguing that since almost all functions are uncomputable, "some aspects of reality might only be accurately described by uncomputable functions." 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?
      - Isinlor 5y ago
        Universe depending on all real numbers would be uncomputable, because most real numbers are uncomputable. 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 https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument https://en.wikipedia.org/wiki/Russell%27s_teapot https://en.wikipedia.org/wiki/Russell%27s_teapot
- mcguire 5y ago
  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.
- Stupulous 5y ago
  Suppose we have some intelligence that cannot be simulated in a Turing machine because it invokes an uncomputable function. That intelligence as it exists in reality is computing something that cannot be computed by a Turing machine. It's not impossible that that can exist (quantum computers may someday demonstrate that, for example), but it would be a huge discovery that would shake the foundations of information theory, especially if it was happening at neuron-scale.
mensetmanusman 5y ago
Turing machines can’t generate their own true randomness, so they are incomplete.
- Stupulous 5y ago
  I believe whether there is a deterministic system underlying quantum behavior is still an open question. My suspicion is that nothing can produce true randomness, in whioh case Turing machines are incomplete only for nonexistent computations. If I'm wrong, Turing machines still feel the effects of true randomness at a greater degree than the brain (compare the size of an axon with silicon), though my assumption that everything in the universe can be modeled in a computer falls through.

simonh 5y ago

My conclusion or theirs? I’m not sure what you mean.

Stupulous 5y ago
I'm responding to their claim in agreement with you.

User23 5y ago

By definition the computable functions are those that can be computed by a Turing machine or equivalent apparatus, so talking about "computation beyond Turing machines" is incoherent. 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?

CrazyStat 5y ago
Do uncomputable functions actually "exist" in reality in any meaningful sense, or are they just mathematical abstractions?
- doganulus 5y ago
  You need to start with the assumption that an infinite set exists (Axiom of Infinity) for uncomputable functions (and other weird mathematical things). Such concepts cannot appear in a finite universe.
- Isinlor 5y ago
  You are asking a question that does not have an answer, because "exist" is not well-defined. But if you want to know whether an arbitrary JavaScript in your browser will stop or not, well you can not know that for all scripts people can throw at you. In this sense uncomputable functions do exist. BTW - The field trying to deal with defining what exist means is called ontology: https://en.wikipedia.org/wiki/Ontology https://en.wikipedia.org/wiki/Ontology
  - CrazyStat 5y ago
    The JavaScript argument doesn't really get at the point I was trying to make (poorly, probably). The parent was arguing that since almost all functions are uncomputable, "some aspects of reality might only be accurately described by uncomputable functions." 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?
    - Isinlor 5y ago
      Universe depending on all real numbers would be uncomputable, because most real numbers are uncomputable. 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 https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument https://en.wikipedia.org/wiki/Russell%27s_teapot https://en.wikipedia.org/wiki/Russell%27s_teapot
mcguire 5y ago
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.
Stupulous 5y ago
Suppose we have some intelligence that cannot be simulated in a Turing machine because it invokes an uncomputable function. That intelligence as it exists in reality is computing something that cannot be computed by a Turing machine. It's not impossible that that can exist (quantum computers may someday demonstrate that, for example), but it would be a huge discovery that would shake the foundations of information theory, especially if it was happening at neuron-scale.

mensetmanusman 5y ago

Turing machines can’t generate their own true randomness, so they are incomplete.

Stupulous 5y ago
I believe whether there is a deterministic system underlying quantum behavior is still an open question. My suspicion is that nothing can produce true randomness, in whioh case Turing machines are incomplete only for nonexistent computations. If I'm wrong, Turing machines still feel the effects of true randomness at a greater degree than the brain (compare the size of an axon with silicon), though my assumption that everything in the universe can be modeled in a computer falls through.