6 ms·

It might not be able to do it for any turing machine/ a universal turing machine – but it might quickly figure out what a turing machine will do without executi

It might not be able to do it for any turing machine/ a universal turing machine – but it might quickly figure out what a turing machine will do without executing all steps of it.

simiones 5y ago
It might get it right some of the time, but it will be necessarily wrong some of the time. It's also very possible that for many (possibly even most) TMs, the most efficient algorithm for predicting the output is that TM itself.
- vlovich123 5y ago
  I think the problem is you're assuming that general AI = Turing machine, but there's no indication that needs to be the case. "General AI" to me means human intelligence running on an artificial system (silicon, simulated brain, etc), so the optimization I'm thinking of is more akin to having an assembly expert translate your code into assembly than a compiler optimization pass. Given that I have optimized my fair bit of code by removing abstraction layers or simplifying code, by definition a general AI should be similarly capable & can handle even ambiguous tasks like "refactor this codebase in this way". Obviously this gives up accuracy, but humans make mistakes writing code as well & it would be much easier to say "I've observed a fault that has this properties. Figure out the problem". It should do an even better job than I can on problems like that because for complicated problems it should be able to follow complex codebases with greater ease than I. Again, I'm defining a tautological definition of "general AI" as one that's capable of doing all that. If it's not capable of doing that then it's not general AI.
  - adrianN 5y ago
    Humans can't solve the halting problem either, there is no contradiction. The halting problem is a theoretical problem that needn't apply in real life. If you for example restrict your AI to be able to generate optimal assembly for all programs that don't require more than 100PB of source code to write down, the halting problem no longer applies (in fact you can now implement this AI using a regular expression).
  - tsimionescu 5y ago
    I understand your points, but it's important to understand that humans ARE Turing Machines. We don't know of anything that CAN be computed bit can't be computed by a Turing Machine, so General AI would be a Turing Machine. The Turing Machine model is specifically designed to abstract what a human (mathematician) does: you have a notebook (tape) and some kind of working memory inside your head, and at any one time you can either read something from the notebook and change the state in your head, or you can write something new in the notebook. This is what a TM does - it is an extremely abstract description of what it means to think, basically.
    - vlovich123 5y ago
      The problem for me with that line of reasoning is that it's one based on philosophy & not mathematically proven or with any clear evidence. For example, [1], [2], [3] all show there are classes of computation outside of Turing machines. So if we agree there are computations outside of Turing machines, then the question is where does the human brain fall and, relatedly, can non-Turing machines run Turing machines? I suspect the answer to the latter question must be yes given the simplicity of a Turing machine (i.e. a pen & pencil is sufficient). Thus, the fact that a human can execute a Turing machine doesn't conclude anything meaningful to me. If you could show that a Turing machine can execute a human brain, then the human brain would 100% be a Turing machine since a core property of a Turing machine is that it can transfer to any other Turing machine. Even if we build "general AI" on a Turing machine, all we've shown is that there is a class of intelligence that is at its core a complicated Turing machine. It might suggest that a human brain is also a Turing machine (& I'd shift the weight of my prior from let's say 30% we're not Turing machines to 70% we are), but I think the only way to definitively prove that would be to do so by mathematically proving the model of the human brain, and then maybe also using it to actually clone a human brain onto a Turing machine to prove the model correct. I think until that happens the argument remains philosophical & whichever side you take to be uninteresting. The only purpose of the debate is to show the question itself is important. [1] https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation [2] http://faculty.poly.edu/~jbain/physinfocomp/Readings/94Hogarth.pdf http://faculty.poly.edu/~jbain/physinfocomp/Readings/94Hogar... [3] https://www.sciencedirect.com/science/article/pii/S0304397503006352 https://www.sciencedirect.com/science/article/pii/S030439750...
- runT1ME 5y ago
  It might only be wrong for programs that have never existed and will ever exist.
  - tsimionescu 5y ago
    Sure, that's possible, but the opposite is also possible: it might be wrong for most programs we actually write. Well, to be fair, there is some upper bound for any program running on a real CPU.
    - runT1ME 5y ago
      >Sure, that's possible, but the opposite is also possible: it might be wrong for most programs we actually write. We could confirm this though! It's not like we can't find out if a given program halts or is inconsisent. Godel talks about it in his letter to Von Nuemann.
      - tsimionescu 5y ago
        There are programs for which we can check this, but there is no general procedure to check if any program halts. Even ignoring the halting problem itself, say we analyze a program and realize it halts iff P=NP, or pi to the e is transcendental, .or if Pi's decimal expansion at position Graham's number is divisible by 3. Will that program halt? It might be very hard to say. More promisingly, there are ways to construct programs such they will halt, using total languages (though not every problem can be solved with such a limitation).
        runT1ME 5y ago
        We can write a general procedure to see it any given program halts within n-steps however.
- MauranKilom 5y ago
  > It might get it right some of the time, but it will be necessarily wrong some of the time Yes, but the proof of the halting problem relies on diagonalization - i.e. a very exotic and carefully crafted input. I would also like to note that, analogously, modern SAT solvers can solve most instances of NP-hard problems in polynomial time. Even though there exist hard cases they cannot solve in polynomial time (well, assuming P != NP), in practice these polynomial algorithms are exceedingly useful. > It's also very possible that for many (possibly even most) TMs, the most efficient algorithm for predicting the output is that TM itself. That could very well be true, but might still not hold for the subset of inputs (i.e. programs) that we actually care about in practice. Relatedly, Kolmogorov complexity makes for some very interesting further reading (which essentially formalizes the problem we're discussing here): https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity

It might not be able to do it for any turing machine/ a universal turing machine – but it might quickly figure out what a turing machine will do without executing all steps of it.

simiones 5y ago

It might get it right some of the time, but it will be necessarily wrong some of the time. It's also very possible that for many (possibly even most) TMs, the most efficient algorithm for predicting the output is that TM itself.

vlovich123 5y ago
I think the problem is you're assuming that general AI = Turing machine, but there's no indication that needs to be the case. "General AI" to me means human intelligence running on an artificial system (silicon, simulated brain, etc), so the optimization I'm thinking of is more akin to having an assembly expert translate your code into assembly than a compiler optimization pass. Given that I have optimized my fair bit of code by removing abstraction layers or simplifying code, by definition a general AI should be similarly capable & can handle even ambiguous tasks like "refactor this codebase in this way". Obviously this gives up accuracy, but humans make mistakes writing code as well & it would be much easier to say "I've observed a fault that has this properties. Figure out the problem". It should do an even better job than I can on problems like that because for complicated problems it should be able to follow complex codebases with greater ease than I. Again, I'm defining a tautological definition of "general AI" as one that's capable of doing all that. If it's not capable of doing that then it's not general AI.
- adrianN 5y ago
  Humans can't solve the halting problem either, there is no contradiction. The halting problem is a theoretical problem that needn't apply in real life. If you for example restrict your AI to be able to generate optimal assembly for all programs that don't require more than 100PB of source code to write down, the halting problem no longer applies (in fact you can now implement this AI using a regular expression).
- tsimionescu 5y ago
  I understand your points, but it's important to understand that humans ARE Turing Machines. We don't know of anything that CAN be computed bit can't be computed by a Turing Machine, so General AI would be a Turing Machine. The Turing Machine model is specifically designed to abstract what a human (mathematician) does: you have a notebook (tape) and some kind of working memory inside your head, and at any one time you can either read something from the notebook and change the state in your head, or you can write something new in the notebook. This is what a TM does - it is an extremely abstract description of what it means to think, basically.
  - vlovich123 5y ago
    The problem for me with that line of reasoning is that it's one based on philosophy & not mathematically proven or with any clear evidence. For example, [1], [2], [3] all show there are classes of computation outside of Turing machines. So if we agree there are computations outside of Turing machines, then the question is where does the human brain fall and, relatedly, can non-Turing machines run Turing machines? I suspect the answer to the latter question must be yes given the simplicity of a Turing machine (i.e. a pen & pencil is sufficient). Thus, the fact that a human can execute a Turing machine doesn't conclude anything meaningful to me. If you could show that a Turing machine can execute a human brain, then the human brain would 100% be a Turing machine since a core property of a Turing machine is that it can transfer to any other Turing machine. Even if we build "general AI" on a Turing machine, all we've shown is that there is a class of intelligence that is at its core a complicated Turing machine. It might suggest that a human brain is also a Turing machine (& I'd shift the weight of my prior from let's say 30% we're not Turing machines to 70% we are), but I think the only way to definitively prove that would be to do so by mathematically proving the model of the human brain, and then maybe also using it to actually clone a human brain onto a Turing machine to prove the model correct. I think until that happens the argument remains philosophical & whichever side you take to be uninteresting. The only purpose of the debate is to show the question itself is important. [1] https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation [2] http://faculty.poly.edu/~jbain/physinfocomp/Readings/94Hogarth.pdf http://faculty.poly.edu/~jbain/physinfocomp/Readings/94Hogar... [3] https://www.sciencedirect.com/science/article/pii/S0304397503006352 https://www.sciencedirect.com/science/article/pii/S030439750...
runT1ME 5y ago
It might only be wrong for programs that have never existed and will ever exist.
- tsimionescu 5y ago
  Sure, that's possible, but the opposite is also possible: it might be wrong for most programs we actually write. Well, to be fair, there is some upper bound for any program running on a real CPU.
  - runT1ME 5y ago
    >Sure, that's possible, but the opposite is also possible: it might be wrong for most programs we actually write. We could confirm this though! It's not like we can't find out if a given program halts or is inconsisent. Godel talks about it in his letter to Von Nuemann.
    - tsimionescu 5y ago
      There are programs for which we can check this, but there is no general procedure to check if any program halts. Even ignoring the halting problem itself, say we analyze a program and realize it halts iff P=NP, or pi to the e is transcendental, .or if Pi's decimal expansion at position Graham's number is divisible by 3. Will that program halt? It might be very hard to say. More promisingly, there are ways to construct programs such they will halt, using total languages (though not every problem can be solved with such a limitation).
      - runT1ME 5y ago
        We can write a general procedure to see it any given program halts within n-steps however.
MauranKilom 5y ago
> It might get it right some of the time, but it will be necessarily wrong some of the time Yes, but the proof of the halting problem relies on diagonalization - i.e. a very exotic and carefully crafted input. I would also like to note that, analogously, modern SAT solvers can solve most instances of NP-hard problems in polynomial time. Even though there exist hard cases they cannot solve in polynomial time (well, assuming P != NP), in practice these polynomial algorithms are exceedingly useful. > It's also very possible that for many (possibly even most) TMs, the most efficient algorithm for predicting the output is that TM itself. That could very well be true, but might still not hold for the subset of inputs (i.e. programs) that we actually care about in practice. Relatedly, Kolmogorov complexity makes for some very interesting further reading (which essentially formalizes the problem we're discussing here): https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity