6 ms·

LLMs can't simulate a Turing machine reliably

smackeyacky 3y ago
[flagged]
vidarh 3y ago
Neither will the vast majority of humans for any reasonable length of time unless you apply significant amount of force and incentives for staying on task. If you want something that will "mindlessly" execute repetitive steps, anything trained to try to act in any way like how humans do would seem an exceedingly bad choice.
- imtringued 3y ago
  Yeah sure, but most CS students will have to do a simple paper trace of a TM or design a TM diagram to graduate. It was on the exam and they only gave you 90 minutes, so it is clearly possible to train a human to do it. Regarding the second half. You aren't very creative. Sometimes you have something very basic, like two tables with numbers in the columns and you ask the LLM to select table rows using it's language capabilities and then tell it to give you the sum and it doesn't work. Great. Except in two years someone will figure out how to train a model to do this and nobody will care. The bitter lesson doesn't mean architectural changes are worthless, it just tells you that an approach that lets the machine leverage its computational capabilities will outpace a researcher's effort to patch a fundamentally broken model with a thousand small workarounds.
  - vidarh 3y ago
    So incentives, in other words. It is possible to teach a human there are consequences not to, and rewards for doing so, because we are consistently fine tuning and retaining state over time, and we have feedback mechanisms in the form of drives. Nothing I said is to suggest it can't be done with LLMs - I'm on record in HN saying LLMs can be made to work as turing machines just fine, and I stand by that. What you can't expect is to give it a prompt, no ongoing constraints or reinforcement, or other feedback, and stay on task for prolonged periods of time. Humans don't do that with any consistency. We self regulate through a whole array of feedback systems, including internal ongoing thoughts, that by the time of exams have been conditioned over years to get better at sticking to a task and consider exam outcomes to matter. And still a lot of us struggle to keep focus for even that kind of time period. Or engage in activities we know are bad for us. Provide similar mechanisms to regular LLMs and they can stay on task too - we can trivially get LLMs to execute individual steps of turing machines, so getting them to keep doing it is a question of how to regulate their ongoing behaviour, not an inherent limitation.
- zer00eyz 3y ago
  We got to the moon, we built the atomic bomb on the literal backs of calculators. These were mostly women who sat at desks all day long and did math. https://www.smithsonianmag.com/science-nature/history-human-computers-180972202/ https://www.smithsonianmag.com/science-nature/history-human-... It was a pretty good job, there wasn't a lot of force, and money is a decent incentive to stay on task.
  - HPsquared 3y ago
    There would have been a system of checking the results somehow. Perhaps the same could be done with LLMs.
    - zer00eyz 3y ago
      More agents is all you need: https://news.ycombinator.com/item?id=39955725 https://news.ycombinator.com/item?id=39955725 This works because each trip through the LLM with the same question uses a different random seed (temperature). You're averaging randomness through a statistical model. You're going to end up with a repeatable result. You're not going to end up with an accurate result.
      - vidarh 3y ago
        You don't typically get accurate results with most humans either without processes for cross checking/tests.
  - cjk2 3y ago
    Just a nit pick, we got to the moon also on the back of slide rules and 3 significant figures of pencil scribblings by thousands of shirted engineers. The computer and calculator side bit is somewhat over-explained because it was sexier. Also, my mother was a calculator once. In the UK. For petrochemical company. It was really boring so she went to smoke weed and fix radios instead as it was the 60s by then and that was cooler.
  - roenxi 3y ago
    Sure; but an LLM can do all those things too. We're talking about a very restricted problem domain with clear deterministic inputs and outputs, neural nets outperform humans under those conditions. Any computer-based method can. So if we take as a starting point that LLMs can't simulate Turing machines and that is important, the tasks you are referring to won't involve simulating Turing machines either. I personally suspect LLMs can simulate Turing machines. Turing machines are pretty basic. Particularly after noting that humans use external tools like pen & paper, so it'd be fair to train the LLM to use some external memory-aiding tool. Then it becomes an academically trivial problem for even a basic neural net.
- criddell 3y ago
  I was thinking the same thing. I get that it’s interesting to study what an LLM in isolation can do. That doesn’t accurately reflect what the commercially available AIs are, does it? Aren’t ChatGPT and Gemini AI tool suites? It kind of annoys me that when you ask Copilot for help with something, it will spit out non-working code. Why isn’t Copilot running and debugging the code before presenting it as an answer?
dathinab 3y ago
somewhat unrelated to what the article is about but: LLMs can't do anything reliable AFIK they are too much probabilistic to be fully "reliable" at least if we take the definition of reliable from well written programs or even proof based programs if we take the definition of reliable from idk. how reliable a underpayed and not well treated employee is then ... it might be a different thing
- cjk2 3y ago
  LLMs are "close enough" solutions. Which should never be used where "close enough" is not good enough. Like Turing machines. Or most things really.
  - mrbombastic 3y ago
    I am already starting to hear from product managers that they want to replace simple deterministic code with llm solutions. There are certainly domains where it makes sense to use these tools but I am afraid they are good enough to essentially make a shiny sales demo for anything that we are gonna be inundated soon with unreliable services.
    - cjk2 3y ago
      As it always goes: Monkey get shiny hammer. Monkey hit toes.
    - jvanderbot 3y ago
      What about summaries? Maybe LLMs are really good human approximates if you need to mashup two or more deterministically computed results into a coherent message. A RAG that pulls meta data about the system and takes as input some plain old computer output could ELI5 just about any result. This is more "project this result onto a context -specific human like space of answers" than "compute it all in LLM"
      - cjk2 3y ago
        This is actually one of my principal objections. A summary of a deterministic computation requires careful thought around how it is explained so that it is interpreted as intended. That requires understanding of the domain, understanding of the semantics of the data being presented and understanding the audience. A failure in this particular space in an observability product we use leads people wildly astray. While the data is correct, the summary is definitely not because it does not have enough understanding of the context.
littlestymaar 3y ago
All I get from that big stack of words is that we've reach the point where LLM can make more sensible arguments than AGI enthusiasts…
HarHarVeryFunny 3y ago
How about this as a nice reductive example of the things that current LLMs struggle/fail at: https://x.com/VictorTaelin/status/1776677635491344744 https://x.com/VictorTaelin/status/1776677635491344744 This guy is offering a $10K prize if anyone can prompt an LLM to reliably (by itself - no tool use) repeatedly apply some simple letter-pair substitution rules to strings of up to 12 characters. The rules to be applied (to strings composed of the letters A, B, X & Y) are: 1) AX -> delete 2) AY -> YA 3) BX -> BY 4) BY -> delete In his Tweet he uses A# #A B# #B rather than A X B Y, but has clarified it makes no difference. Try it - it's remarkably hard. You should be able to get the LLM to do a few short ones, but try getting it to be reliable or do longer ones. So, Turing? Not going to happen!
- viraptor 3y ago
  As long as you can convince LLM to do it step by step, reproducing the whole thing again, it gets much simpler. It changes the idea of an unlimited number of steps into one replacement at a time. Then make sure to split the list so that the letters don't get merged into larger tokens. (Same issue as numbers and math)
  - sfn42 3y ago
    Then go win the prize?
  - phire 3y ago
    Which is part of the problem. LLMs don't like doing things step by step. You can force an LLM to go step by step with an external tool that continually re-prompts with each step, but the challenge requires a single prompt. When you try to do prompt engineering to make it go step by step before telling you the answer, things go off the rails after a handful of steps.
    - vidarh 3y ago
      Humans don't like doing things step by step without incentives and prodding either. To me, this is an odd thing to try to get LLMs to do because we know it's immensely hard to ensure reliable repetitive rule application to the point we spend many years conditioning humans on tasks where we care about the ability to stick with it, and then still built entire social structures on encouraging ongoing compliance, and still regularly fail to achieve it. Why would we expect LLMs that are still fairly primitive to do this well without mechanisms regulating it?
brap 3y ago
>To get a true AGI, we would need some kind of architecture that is able to not just learn functions by example, but also grant these functions all the computing power they need to run and thrive. Computers can’t simulate Turing machines reliably either, and for the same reason. This is probably true for humans also.
- jvanderbot 3y ago
  Can you explain why computers cannot simulate Turing machines and how that relates to the quote? My reading is that the quote says "to reach agi, it's not enough to learn a sequence of steps in text, we will want the agi to be able to crystalize (compile) that sequence of steps into a program run without abstractions on its native system." Presumably because it's too slow to run it on top of an LLM. Stretching further. I think humans do crystalize learning into things that look hardcoded, like muscle memory or reflexes, rather than talking themselves through everything.
- rsynnott 3y ago
  Both humans and computers can absolutely simulate Turing machines. What are you talking about?
LightMachine 3y ago
Oh my point was NOT that LLMs can't simulate a Turing machine reliably. I was just replying to the tweet above. The main point of this (speculative) text is that GPTs can "evolve a general learner" inside them, but are unable to give enough computing power to it, since it will dispute dispute compute and space with billions of task-specific circuits. Also, even if it could, the "computer" on which learned procedures run (inside transformers) is too limited in many senses, but not being Turing complete isn't the main issue, just one of them. Basically I'm saying that (on my view) GPTs is kinda growing an AGI procedure inside it, but that AGI is restricted by rigid computational constraints imposed by the GPT architecture. I think something slightly more flexible might be capable of filtering out the noise more efficiently and replicate what GPTs do with an absurdly small fraction of the cost. So, to be very clear, the point has nothing to do with Turing completeness and more to do with the ultra-limited computation and expressivity granted to internally learned functions. It is a small distinction, but a non-Turing complete model can still be extremely expressive.
- idkdotcom 3y ago
  [dead]
Scene_Cast2 3y ago
The neat thing is that LLMs can run on non-Turing-complete hardware.
deleted 3y ago
[deleted]
cma 3y ago
Deepmind did a study of which language classes different neural network architectures can learn with generalization: https://arxiv.org/abs/2207.02098 https://arxiv.org/abs/2207.02098 ("Neural Networks and the Chomsky Hierarchy") LSTMs could learn slightly deeper into the Chomsky hierarchy than transformers, neural turing machines could learn them all including recursively enumerable (context free grammar or turing machine to produce). Transformers did outperform LSTMs in something in an alternate hierarchy if I remember. It's not conclusive since it is not training indefinitely, there are formal proofs that many architectures can do things that they can't actually effectively be trained for, but they threw a lot of compute at it.
idkdotcom 3y ago
[dead]
QuadrupleA 3y ago
LLMs sample each next token from a probability distribution. So there's an inherent random process at work. As long as your LLM's "next Turing machine step" output token has anything less than 100.000% odds of being the correct one, you'll get mistakes and unreliability. You could change your sampling to top-token-only. But (and maybe this is hand-wavey) I still suspect the incorrect token will be sometimes predicted on top.
skeledrew 3y ago
After making several attempts at figuring it out, I'm giving up. Takes too much thought. Guess I'm not an "average" person, and even my MS in CS is useless :shrugs:
- geor9e 3y ago
  Are you referring to the puzzle at the top of the tweet thread, where he spells out the 4 simple steps to get to the solution? Or are you referring to the $10,000 prize competition where dozens of the worlds best minds are failing to solve it yet?
  - skeledrew 3y ago
    The puzzle. Eyeballing it wasn't working out and I couldn't be bothered to actually write it down to figure it out. But then again I was also listening to music in a language that I'm learning, so some thought power was tied up. BTW re the prompt problem... several persons actually solved it and the prize was claimed.

[flagged]

Neither will the vast majority of humans for any reasonable length of time unless you apply significant amount of force and incentives for staying on task. If you want something that will "mindlessly" execute repetitive steps, anything trained to try to act in any way like how humans do would seem an exceedingly bad choice.

imtringued 3y ago
Yeah sure, but most CS students will have to do a simple paper trace of a TM or design a TM diagram to graduate. It was on the exam and they only gave you 90 minutes, so it is clearly possible to train a human to do it. Regarding the second half. You aren't very creative. Sometimes you have something very basic, like two tables with numbers in the columns and you ask the LLM to select table rows using it's language capabilities and then tell it to give you the sum and it doesn't work. Great. Except in two years someone will figure out how to train a model to do this and nobody will care. The bitter lesson doesn't mean architectural changes are worthless, it just tells you that an approach that lets the machine leverage its computational capabilities will outpace a researcher's effort to patch a fundamentally broken model with a thousand small workarounds.
- vidarh 3y ago
  So incentives, in other words. It is possible to teach a human there are consequences not to, and rewards for doing so, because we are consistently fine tuning and retaining state over time, and we have feedback mechanisms in the form of drives. Nothing I said is to suggest it can't be done with LLMs - I'm on record in HN saying LLMs can be made to work as turing machines just fine, and I stand by that. What you can't expect is to give it a prompt, no ongoing constraints or reinforcement, or other feedback, and stay on task for prolonged periods of time. Humans don't do that with any consistency. We self regulate through a whole array of feedback systems, including internal ongoing thoughts, that by the time of exams have been conditioned over years to get better at sticking to a task and consider exam outcomes to matter. And still a lot of us struggle to keep focus for even that kind of time period. Or engage in activities we know are bad for us. Provide similar mechanisms to regular LLMs and they can stay on task too - we can trivially get LLMs to execute individual steps of turing machines, so getting them to keep doing it is a question of how to regulate their ongoing behaviour, not an inherent limitation.
zer00eyz 3y ago
We got to the moon, we built the atomic bomb on the literal backs of calculators. These were mostly women who sat at desks all day long and did math. https://www.smithsonianmag.com/science-nature/history-human-computers-180972202/ https://www.smithsonianmag.com/science-nature/history-human-... It was a pretty good job, there wasn't a lot of force, and money is a decent incentive to stay on task.
- HPsquared 3y ago
  There would have been a system of checking the results somehow. Perhaps the same could be done with LLMs.
  - zer00eyz 3y ago
    More agents is all you need: https://news.ycombinator.com/item?id=39955725 https://news.ycombinator.com/item?id=39955725 This works because each trip through the LLM with the same question uses a different random seed (temperature). You're averaging randomness through a statistical model. You're going to end up with a repeatable result. You're not going to end up with an accurate result.
    - vidarh 3y ago
      You don't typically get accurate results with most humans either without processes for cross checking/tests.
- cjk2 3y ago
  Just a nit pick, we got to the moon also on the back of slide rules and 3 significant figures of pencil scribblings by thousands of shirted engineers. The computer and calculator side bit is somewhat over-explained because it was sexier. Also, my mother was a calculator once. In the UK. For petrochemical company. It was really boring so she went to smoke weed and fix radios instead as it was the 60s by then and that was cooler.
- roenxi 3y ago
  Sure; but an LLM can do all those things too. We're talking about a very restricted problem domain with clear deterministic inputs and outputs, neural nets outperform humans under those conditions. Any computer-based method can. So if we take as a starting point that LLMs can't simulate Turing machines and that is important, the tasks you are referring to won't involve simulating Turing machines either. I personally suspect LLMs can simulate Turing machines. Turing machines are pretty basic. Particularly after noting that humans use external tools like pen & paper, so it'd be fair to train the LLM to use some external memory-aiding tool. Then it becomes an academically trivial problem for even a basic neural net.
criddell 3y ago
I was thinking the same thing. I get that it’s interesting to study what an LLM in isolation can do. That doesn’t accurately reflect what the commercially available AIs are, does it? Aren’t ChatGPT and Gemini AI tool suites? It kind of annoys me that when you ask Copilot for help with something, it will spit out non-working code. Why isn’t Copilot running and debugging the code before presenting it as an answer?

dathinab 3y ago

somewhat unrelated to what the article is about but: LLMs can't do anything reliable AFIK they are too much probabilistic to be fully "reliable" at least if we take the definition of reliable from well written programs or even proof based programs if we take the definition of reliable from idk. how reliable a underpayed and not well treated employee is then ... it might be a different thing

cjk2 3y ago
LLMs are "close enough" solutions. Which should never be used where "close enough" is not good enough. Like Turing machines. Or most things really.
- mrbombastic 3y ago
  I am already starting to hear from product managers that they want to replace simple deterministic code with llm solutions. There are certainly domains where it makes sense to use these tools but I am afraid they are good enough to essentially make a shiny sales demo for anything that we are gonna be inundated soon with unreliable services.
  - cjk2 3y ago
    As it always goes: Monkey get shiny hammer. Monkey hit toes.
  - jvanderbot 3y ago
    What about summaries? Maybe LLMs are really good human approximates if you need to mashup two or more deterministically computed results into a coherent message. A RAG that pulls meta data about the system and takes as input some plain old computer output could ELI5 just about any result. This is more "project this result onto a context -specific human like space of answers" than "compute it all in LLM"
    - cjk2 3y ago
      This is actually one of my principal objections. A summary of a deterministic computation requires careful thought around how it is explained so that it is interpreted as intended. That requires understanding of the domain, understanding of the semantics of the data being presented and understanding the audience. A failure in this particular space in an observability product we use leads people wildly astray. While the data is correct, the summary is definitely not because it does not have enough understanding of the context.

littlestymaar 3y ago

All I get from that big stack of words is that we've reach the point where LLM can make more sensible arguments than AGI enthusiasts…

HarHarVeryFunny 3y ago

How about this as a nice reductive example of the things that current LLMs struggle/fail at: https://x.com/VictorTaelin/status/1776677635491344744 https://x.com/VictorTaelin/status/1776677635491344744 This guy is offering a $10K prize if anyone can prompt an LLM to reliably (by itself - no tool use) repeatedly apply some simple letter-pair substitution rules to strings of up to 12 characters. The rules to be applied (to strings composed of the letters A, B, X & Y) are: 1) AX -> delete 2) AY -> YA 3) BX -> BY 4) BY -> delete In his Tweet he uses A# #A B# #B rather than A X B Y, but has clarified it makes no difference. Try it - it's remarkably hard. You should be able to get the LLM to do a few short ones, but try getting it to be reliable or do longer ones. So, Turing? Not going to happen!

viraptor 3y ago
As long as you can convince LLM to do it step by step, reproducing the whole thing again, it gets much simpler. It changes the idea of an unlimited number of steps into one replacement at a time. Then make sure to split the list so that the letters don't get merged into larger tokens. (Same issue as numbers and math)
- sfn42 3y ago
  Then go win the prize?
- phire 3y ago
  Which is part of the problem. LLMs don't like doing things step by step. You can force an LLM to go step by step with an external tool that continually re-prompts with each step, but the challenge requires a single prompt. When you try to do prompt engineering to make it go step by step before telling you the answer, things go off the rails after a handful of steps.
  - vidarh 3y ago
    Humans don't like doing things step by step without incentives and prodding either. To me, this is an odd thing to try to get LLMs to do because we know it's immensely hard to ensure reliable repetitive rule application to the point we spend many years conditioning humans on tasks where we care about the ability to stick with it, and then still built entire social structures on encouraging ongoing compliance, and still regularly fail to achieve it. Why would we expect LLMs that are still fairly primitive to do this well without mechanisms regulating it?

brap 3y ago

>To get a true AGI, we would need some kind of architecture that is able to not just learn functions by example, but also grant these functions all the computing power they need to run and thrive. Computers can’t simulate Turing machines reliably either, and for the same reason. This is probably true for humans also.

jvanderbot 3y ago
Can you explain why computers cannot simulate Turing machines and how that relates to the quote? My reading is that the quote says "to reach agi, it's not enough to learn a sequence of steps in text, we will want the agi to be able to crystalize (compile) that sequence of steps into a program run without abstractions on its native system." Presumably because it's too slow to run it on top of an LLM. Stretching further. I think humans do crystalize learning into things that look hardcoded, like muscle memory or reflexes, rather than talking themselves through everything.
rsynnott 3y ago
Both humans and computers can absolutely simulate Turing machines. What are you talking about?

LightMachine 3y ago

Oh my point was NOT that LLMs can't simulate a Turing machine reliably. I was just replying to the tweet above. The main point of this (speculative) text is that GPTs can "evolve a general learner" inside them, but are unable to give enough computing power to it, since it will dispute dispute compute and space with billions of task-specific circuits. Also, even if it could, the "computer" on which learned procedures run (inside transformers) is too limited in many senses, but not being Turing complete isn't the main issue, just one of them. Basically I'm saying that (on my view) GPTs is kinda growing an AGI procedure inside it, but that AGI is restricted by rigid computational constraints imposed by the GPT architecture. I think something slightly more flexible might be capable of filtering out the noise more efficiently and replicate what GPTs do with an absurdly small fraction of the cost. So, to be very clear, the point has nothing to do with Turing completeness and more to do with the ultra-limited computation and expressivity granted to internally learned functions. It is a small distinction, but a non-Turing complete model can still be extremely expressive.

idkdotcom 3y ago
[dead]

Scene_Cast2 3y ago

The neat thing is that LLMs can run on non-Turing-complete hardware.

deleted 3y ago

[deleted]

cma 3y ago

Deepmind did a study of which language classes different neural network architectures can learn with generalization: https://arxiv.org/abs/2207.02098 https://arxiv.org/abs/2207.02098 ("Neural Networks and the Chomsky Hierarchy") LSTMs could learn slightly deeper into the Chomsky hierarchy than transformers, neural turing machines could learn them all including recursively enumerable (context free grammar or turing machine to produce). Transformers did outperform LSTMs in something in an alternate hierarchy if I remember. It's not conclusive since it is not training indefinitely, there are formal proofs that many architectures can do things that they can't actually effectively be trained for, but they threw a lot of compute at it.

idkdotcom 3y ago

[dead]

QuadrupleA 3y ago

LLMs sample each next token from a probability distribution. So there's an inherent random process at work. As long as your LLM's "next Turing machine step" output token has anything less than 100.000% odds of being the correct one, you'll get mistakes and unreliability. You could change your sampling to top-token-only. But (and maybe this is hand-wavey) I still suspect the incorrect token will be sometimes predicted on top.

skeledrew 3y ago

After making several attempts at figuring it out, I'm giving up. Takes too much thought. Guess I'm not an "average" person, and even my MS in CS is useless :shrugs:

geor9e 3y ago
Are you referring to the puzzle at the top of the tweet thread, where he spells out the 4 simple steps to get to the solution? Or are you referring to the $10,000 prize competition where dozens of the worlds best minds are failing to solve it yet?
- skeledrew 3y ago
  The puzzle. Eyeballing it wasn't working out and I couldn't be bothered to actually write it down to figure it out. But then again I was also listening to music in a language that I'm learning, so some thought power was tied up. BTW re the prompt problem... several persons actually solved it and the prize was claimed.