7 ms·

I'm the original author of this blogpost. I've had discussions that range from "we need to fix this" to "maybe human thought isn't Turing complete..." and I'm

I'm the original author of this blogpost. I've had discussions that range from "we need to fix this" to "maybe human thought isn't Turing complete..." and I'm interested in hearing what yall think about the topic. P.S. I'm graduating soon and looking for research scientist roles.

abetusk 3y ago
My apologies, I've only skimmed, but maybe this encapsulates the main idea of your post? """ How MLPs could be trained was an open problem at the time, I think, but the field could easily have chugged along and we’d have been where we are now, just 30 years earlier. """ The main idea here is that we got an AI winter because expectations were too high and the reality didn't meet them? I think this is fundamentally missing why we're making rapid progress now. In my opinion, the AI winter wasn't primarily because of a backlash against overhyped promises, it was because computation just wasn't there. We're just now starting to get access to the compute and storage needed, at a price point that's reasonable, to make progress in these areas. In other words, the AI winter came about because the ground wasn't fertile. Now that we have economic massive computational resources, we're in an AI spring. As a back of the envelope calculation, the human brain is estimated at around 2.5 Pb of storage [0]. At today's prices, that works out to about $50k. The cost of 2.5Pb of storage in 1969 was around $675B [1]. [0] https://www.scientificamerican.com/article/what-is-the-memory-capacity/ https://www.scientificamerican.com/article/what-is-the-memor... [1] https://ourworldindata.org/grapher/historical-cost-of-computer-memory-and-storage?country=~OWID_WRL https://ourworldindata.org/grapher/historical-cost-of-comput...
- BlueTemplar 3y ago
  I had the same thought : what would it have cost to make one of those early deep neural networks that restarted the field, but without hardware virtualization : with the same kind of physical neurons than the Perceptron, but with better tech, say mid-AI winter?
- emmelaich 3y ago
  Agree so much that I had assumed this was the standard common view.
DougBTX 3y ago
At least for short sequences it works, but I guess the trick is to make it work for long sequences! Prompt and output from GPT-4: Write a Python function to compute PARITY incrementally on a list of 0 and 1. For example, the output for [0, 1, 1] should be 0, 1, 0. Print out all the intermediate values. Here is a Python function to compute the parity incrementally on a list of 0s and 1s. The function will print out all intermediate values as well. def incremental_parity(lst): parity = 0 result = [] for num in lst: if num not in (0, 1): raise ValueError("The list should contain only 0s and 1s.") parity ^= num # XOR operation result.append(parity) print(f'Current list: {lst[:len(result)]}, Intermediate result: {result}') return result # Example usage: lst = [0, 1, 1] result = incremental_parity(lst) print(f'Final result: {result}') This function computes the parity incrementally by XORing each element of the list. The intermediate and final results are printed as requested. What is the output for this function on the list [0, 1, 1, 0, 0, 1, 0, 1, 1] To find the output of the function on the given list, you can use the provided incremental_parity function. Here's what the output would look like: lst = [0, 1, 1, 0, 0, 1, 0, 1, 1] result = incremental_parity(lst) Output: Current list: [0], Intermediate result: [0] Current list: [0, 1], Intermediate result: [0, 1] Current list: [0, 1, 1], Intermediate result: [0, 1, 0] Current list: [0, 1, 1, 0], Intermediate result: [0, 1, 0, 0] Current list: [0, 1, 1, 0, 0], Intermediate result: [0, 1, 0, 0, 0] Current list: [0, 1, 1, 0, 0, 1], Intermediate result: [0, 1, 0, 0, 0, 1] Current list: [0, 1, 1, 0, 0, 1, 0], Intermediate result: [0, 1, 0, 0, 0, 1, 1] Current list: [0, 1, 1, 0, 0, 1, 0, 1], Intermediate result: [0, 1, 0, 0, 0, 1, 1, 0] Current list: [0, 1, 1, 0, 0, 1, 0, 1, 1], Intermediate result: [0, 1, 0, 0, 0, 1, 1, 0, 1] Final result: [0, 1, 0, 0, 0, 1, 1, 0, 1] The final result for the list [0, 1, 1, 0, 0, 1, 0, 1, 1] is [0, 1, 0, 0, 0, 1, 1, 0, 1].
- shawntan 3y ago
  Yeah the issue tends to be as the length increases the performance drops off. Your approach reminds me of Hattie's work: https://arxiv.org/pdf/2211.09066.pdf https://arxiv.org/pdf/2211.09066.pdf I do wonder if the observable drop-off in performance on these formal languages / arithmetic tasks is something more fundamental, and related to the attention mechanism; namely that it can't attend further back as the input gets longer (possibly due to the way attention scores are computed).
mckirk 3y ago
The thought I had while reading, which you also touched on towards the end, was: You might indeed not need a model powerful enough to compute PARITY in 'one shot', if what you are aiming for is 'only' modeling human thought. Humans would be terrible at a task like computing PARITY for a long binary sequence if you asked them to do it _instantly_, without taking notes and without going through the sequence iteratively. But that's essentially what we are asking the LLMs to do at the moment. Interestingly, the LLM trained on human language doesn't _know_ that it has this limitation, whereas the humans it is trying to imitate did not, so it is trying its best to one-shot everything (just like the examples it has seen seem to do), though 'talking to itself' about the problem might make it a lot easier. So, perhaps similar to the 'show your work' approach and to your UT approach, if we could offer some 'internal scratch space' to the LLMs and train them to use it in order to reach an answer, they might get a lot better at all the kinds of tasks that a human might prefer to reason through first as well -- though training and inference would become a lot more expensive, I suppose.
- shawntan 3y ago
  To be clear, LSTMs and RNNs have no issue with the parity problem. As for humans, I think you could run into boredom / fatigue if you just told someone to sit there and 'maintain state' for PARITY, but I'm sure most of us could do it: you just need to maintain ODD or EVEN at any point in time as the bits are being fed to you. The fact that Transformers as they exist now require these additional mechanisms feel to me like there is a lot of room for improvement.
  - mckirk 3y ago
    True, I should probably have been more specific, with 'LLMs' I was just referring to the current Transformer based models. And yes, we could of course get the right answer to PARITY problems, but only if we were allowed some kind of scratch space (mental or external) -- even if only for the single bit of current state in the sequence. But that's precisely what Transformers aren't afforded, right? They have to look at the whole problem once and need to derive their solution from that; there's no 'going through the sequence one bit at a time' for them. So they are really good (amazing actually, when you think about it) at performing the 'single thought' action, but still severely limited because they don't have the equivalent of a writable working memory.
mkl 3y ago
Is that parity state machine right? It looks like it can get stuck in the rightmost state when the string ends, e.g. for "1", "10", "111". I also spotted a typo: "cumptation".
- shawntan 3y ago
  Damn I've been meaning to fix that.
mannykannot 3y ago
Thank you for this excellent article, which I almost passed by until I remembered what the original XOR problem was (so, for me at least, the title is inverted click-bait!) With regard to the question of whether human thought is Turing complete: on the one hand, we clearly can solve Turing-hard problems up to the limits of our memory (a constraint which is considerably expanded through written language), while on the other hand, we can and do make mistakes while attempting such problems. Personally, I feel the former is sufficient to answer the question in the affirmative, despite of the fact of the latter. The issue of Turing completeness is central to the Penrose-Lucas argument against AGI, as discussed at length in Roger Penrose's book "The Emperor's New Mind". Here, however, the claim is that human thought goes beyond Turing completeness: Gödel-unprovable results are provable by humans. While I feel that the complete argument against AGI fails on account of it equivocating over what it means to prove something, the above claim about the scope of human thought seems to be an empirical fact. I have no idea how this observation could help in AI development, but we know that one can prompt a current-generation LLM to produce sentences that humans would recognize as expressing the sort of thoughts that would be useful in solving the given problem (though whether the LLM will go on to produce the solution that is obvious to the humans, and consistent with its earlier productions, is hit-or-miss.) This suggests to me that some sort of self-prompting capability might be necessary (but not sufficient) for a general problem-solving ability.
- shawntan 3y ago
  On the memory limitation: Yeah, lack of an infinite tape is a real bummer. On some level I think we're some kind of bounded-tape automaton, which still makes the current limitations of Transformers pretty severe. (Yes, yes, prompting, CoT, and all that)
- YeGoblynQueenne 3y ago
  (...) Gödel-unprovable results are provable by humans. Are they? Certainly humans can recognise the undedicability of a "barber's paradox", like "this sentence is false", but that doesn't mean we can actually decide its truth value. We can spot undecidability, but not resolve it. Right? So what do you mean?
aidenn0 3y ago
I know nothing about ML, but as far as "maybe human thought isn't Turing complete:" If you teach a human how a Turing machine works, they are quite capable of simulating it with paper and pencil with a high probability of each step being correct. If you give several humans the same problem and have them work through it, keeping track of their work, then you can find points of divergence and go with the majority solution, then recalculate starting from the divergence. Prior to electronic computers, groups of humans using pencil, paper, reference-tables (that themselves had been hand-calculated by humans), and slide-rules worked this way to get accurate answers to arbitrarily difficult computations. That is to say that while individual humans might arguably not be Turing complete, groups of humans, with the right manipulatives, are limited only by storage, so are as Turing complete as any general-purpose electronic computer. Given that these recent language models are both non-deterministic, and significantly more human-like in the mistakes they make, I see no reason why similar techniques could not be used, given proper training. It does seem rather inefficient, since for problems in which a well-defined algorithm exists we can already program a computer to do it far better than I suspect any LLM would do.
- deanCommie 3y ago
  > Prior to electronic computers, groups of humans using pencil, paper, reference-tables (that themselves had been hand-calculated by humans), and slide-rules worked this way to get accurate answers to arbitrarily difficult computations. There's a scene of this in Apollo 13. Line of humans with slide rulers manually confirming calculations made on the craft whose computer is out.
- WorldMaker 3y ago
  Related to this topic, we still don't have a good, strong idea of how human thought works. Neural Networks/Perceptrons were built out of analogies of how human-like neurons seem to work (primarily in isolation studies in a petri dish or similar experiments), but it is very easy to forget that the model/analogy is not the reality when you work with those models a lot. The current "map" certainly doesn't seem to be the territory here. Neurons are just one part of the human brain, there's also complex chemical receptors and hormonal pathways that we mostly still only grasp in the abstract of how they interplay with neurons and other signal pathways. Additionally, there's indirect evidence that brains may take some advantage of quantum effects among/between neurons such as entangled particle states, but we don't know a lot more than we know about the quantum states of human brain activity. (How do we even probe that in a living human with our current knowledge of quantum physics?) Neural Networks/Perceptrons have been very useful models in computation, but that doesn't mean they are actually good or representative models for human cognition.
phaedrus 3y ago
To summarize my other top-level comment: I read a paper which pointed out we have no reason to believe the Chomsky hierarchy is the only formal hierarchy of languages that could exist, and the author asked why aren't we looking for other language complexity classification systems that might better match our intuitions about natural languages? Physical computers aren't Turing Complete either, because they have finite memory. That hasn't stopped us from making practical use of them.
aaroninsf 3y ago
To paraphrase The Graduate, "Recurrence, my child—recurrence!" I'd take the bet that in the medium term (whatever that means today), the Transformer architecture as implemented today will be replaced by designs which revive recurrent, non-directed architectures, with a few specific properties: • cycles will be allowed • equilibrium (over time) will serve as state ("output") • computationally this is a couple orders more expensive than current approaches, both in training and in use • investigating emergent internal encoding and computation will similarly be orders more expensive to investigate, and require nearly as expensive tools as subjects This is The Way. NB non-coincidentally this looks much more like an animal brain.

abetusk 3y ago

My apologies, I've only skimmed, but maybe this encapsulates the main idea of your post? """ How MLPs could be trained was an open problem at the time, I think, but the field could easily have chugged along and we’d have been where we are now, just 30 years earlier. """ The main idea here is that we got an AI winter because expectations were too high and the reality didn't meet them? I think this is fundamentally missing why we're making rapid progress now. In my opinion, the AI winter wasn't primarily because of a backlash against overhyped promises, it was because computation just wasn't there. We're just now starting to get access to the compute and storage needed, at a price point that's reasonable, to make progress in these areas. In other words, the AI winter came about because the ground wasn't fertile. Now that we have economic massive computational resources, we're in an AI spring. As a back of the envelope calculation, the human brain is estimated at around 2.5 Pb of storage [0]. At today's prices, that works out to about $50k. The cost of 2.5Pb of storage in 1969 was around $675B [1]. [0] https://www.scientificamerican.com/article/what-is-the-memory-capacity/ https://www.scientificamerican.com/article/what-is-the-memor... [1] https://ourworldindata.org/grapher/historical-cost-of-computer-memory-and-storage?country=~OWID_WRL https://ourworldindata.org/grapher/historical-cost-of-comput...

BlueTemplar 3y ago
I had the same thought : what would it have cost to make one of those early deep neural networks that restarted the field, but without hardware virtualization : with the same kind of physical neurons than the Perceptron, but with better tech, say mid-AI winter?
emmelaich 3y ago
Agree so much that I had assumed this was the standard common view.

DougBTX 3y ago

At least for short sequences it works, but I guess the trick is to make it work for long sequences! Prompt and output from GPT-4: Write a Python function to compute PARITY incrementally on a list of 0 and 1. For example, the output for [0, 1, 1] should be 0, 1, 0. Print out all the intermediate values. Here is a Python function to compute the parity incrementally on a list of 0s and 1s. The function will print out all intermediate values as well. def incremental_parity(lst): parity = 0 result = [] for num in lst: if num not in (0, 1): raise ValueError("The list should contain only 0s and 1s.") parity ^= num # XOR operation result.append(parity) print(f'Current list: {lst[:len(result)]}, Intermediate result: {result}') return result # Example usage: lst = [0, 1, 1] result = incremental_parity(lst) print(f'Final result: {result}') This function computes the parity incrementally by XORing each element of the list. The intermediate and final results are printed as requested. What is the output for this function on the list [0, 1, 1, 0, 0, 1, 0, 1, 1] To find the output of the function on the given list, you can use the provided incremental_parity function. Here's what the output would look like: lst = [0, 1, 1, 0, 0, 1, 0, 1, 1] result = incremental_parity(lst) Output: Current list: [0], Intermediate result: [0] Current list: [0, 1], Intermediate result: [0, 1] Current list: [0, 1, 1], Intermediate result: [0, 1, 0] Current list: [0, 1, 1, 0], Intermediate result: [0, 1, 0, 0] Current list: [0, 1, 1, 0, 0], Intermediate result: [0, 1, 0, 0, 0] Current list: [0, 1, 1, 0, 0, 1], Intermediate result: [0, 1, 0, 0, 0, 1] Current list: [0, 1, 1, 0, 0, 1, 0], Intermediate result: [0, 1, 0, 0, 0, 1, 1] Current list: [0, 1, 1, 0, 0, 1, 0, 1], Intermediate result: [0, 1, 0, 0, 0, 1, 1, 0] Current list: [0, 1, 1, 0, 0, 1, 0, 1, 1], Intermediate result: [0, 1, 0, 0, 0, 1, 1, 0, 1] Final result: [0, 1, 0, 0, 0, 1, 1, 0, 1] The final result for the list [0, 1, 1, 0, 0, 1, 0, 1, 1] is [0, 1, 0, 0, 0, 1, 1, 0, 1].

shawntan 3y ago
Yeah the issue tends to be as the length increases the performance drops off. Your approach reminds me of Hattie's work: https://arxiv.org/pdf/2211.09066.pdf https://arxiv.org/pdf/2211.09066.pdf I do wonder if the observable drop-off in performance on these formal languages / arithmetic tasks is something more fundamental, and related to the attention mechanism; namely that it can't attend further back as the input gets longer (possibly due to the way attention scores are computed).

mckirk 3y ago

The thought I had while reading, which you also touched on towards the end, was: You might indeed not need a model powerful enough to compute PARITY in 'one shot', if what you are aiming for is 'only' modeling human thought. Humans would be terrible at a task like computing PARITY for a long binary sequence if you asked them to do it _instantly_, without taking notes and without going through the sequence iteratively. But that's essentially what we are asking the LLMs to do at the moment. Interestingly, the LLM trained on human language doesn't _know_ that it has this limitation, whereas the humans it is trying to imitate did not, so it is trying its best to one-shot everything (just like the examples it has seen seem to do), though 'talking to itself' about the problem might make it a lot easier. So, perhaps similar to the 'show your work' approach and to your UT approach, if we could offer some 'internal scratch space' to the LLMs and train them to use it in order to reach an answer, they might get a lot better at all the kinds of tasks that a human might prefer to reason through first as well -- though training and inference would become a lot more expensive, I suppose.

shawntan 3y ago
To be clear, LSTMs and RNNs have no issue with the parity problem. As for humans, I think you could run into boredom / fatigue if you just told someone to sit there and 'maintain state' for PARITY, but I'm sure most of us could do it: you just need to maintain ODD or EVEN at any point in time as the bits are being fed to you. The fact that Transformers as they exist now require these additional mechanisms feel to me like there is a lot of room for improvement.
- mckirk 3y ago
  True, I should probably have been more specific, with 'LLMs' I was just referring to the current Transformer based models. And yes, we could of course get the right answer to PARITY problems, but only if we were allowed some kind of scratch space (mental or external) -- even if only for the single bit of current state in the sequence. But that's precisely what Transformers aren't afforded, right? They have to look at the whole problem once and need to derive their solution from that; there's no 'going through the sequence one bit at a time' for them. So they are really good (amazing actually, when you think about it) at performing the 'single thought' action, but still severely limited because they don't have the equivalent of a writable working memory.

mkl 3y ago

Is that parity state machine right? It looks like it can get stuck in the rightmost state when the string ends, e.g. for "1", "10", "111". I also spotted a typo: "cumptation".

shawntan 3y ago
Damn I've been meaning to fix that.

mannykannot 3y ago

Thank you for this excellent article, which I almost passed by until I remembered what the original XOR problem was (so, for me at least, the title is inverted click-bait!) With regard to the question of whether human thought is Turing complete: on the one hand, we clearly can solve Turing-hard problems up to the limits of our memory (a constraint which is considerably expanded through written language), while on the other hand, we can and do make mistakes while attempting such problems. Personally, I feel the former is sufficient to answer the question in the affirmative, despite of the fact of the latter. The issue of Turing completeness is central to the Penrose-Lucas argument against AGI, as discussed at length in Roger Penrose's book "The Emperor's New Mind". Here, however, the claim is that human thought goes beyond Turing completeness: Gödel-unprovable results are provable by humans. While I feel that the complete argument against AGI fails on account of it equivocating over what it means to prove something, the above claim about the scope of human thought seems to be an empirical fact. I have no idea how this observation could help in AI development, but we know that one can prompt a current-generation LLM to produce sentences that humans would recognize as expressing the sort of thoughts that would be useful in solving the given problem (though whether the LLM will go on to produce the solution that is obvious to the humans, and consistent with its earlier productions, is hit-or-miss.) This suggests to me that some sort of self-prompting capability might be necessary (but not sufficient) for a general problem-solving ability.

shawntan 3y ago
On the memory limitation: Yeah, lack of an infinite tape is a real bummer. On some level I think we're some kind of bounded-tape automaton, which still makes the current limitations of Transformers pretty severe. (Yes, yes, prompting, CoT, and all that)
YeGoblynQueenne 3y ago
(...) Gödel-unprovable results are provable by humans. Are they? Certainly humans can recognise the undedicability of a "barber's paradox", like "this sentence is false", but that doesn't mean we can actually decide its truth value. We can spot undecidability, but not resolve it. Right? So what do you mean?

aidenn0 3y ago

I know nothing about ML, but as far as "maybe human thought isn't Turing complete:" If you teach a human how a Turing machine works, they are quite capable of simulating it with paper and pencil with a high probability of each step being correct. If you give several humans the same problem and have them work through it, keeping track of their work, then you can find points of divergence and go with the majority solution, then recalculate starting from the divergence. Prior to electronic computers, groups of humans using pencil, paper, reference-tables (that themselves had been hand-calculated by humans), and slide-rules worked this way to get accurate answers to arbitrarily difficult computations. That is to say that while individual humans might arguably not be Turing complete, groups of humans, with the right manipulatives, are limited only by storage, so are as Turing complete as any general-purpose electronic computer. Given that these recent language models are both non-deterministic, and significantly more human-like in the mistakes they make, I see no reason why similar techniques could not be used, given proper training. It does seem rather inefficient, since for problems in which a well-defined algorithm exists we can already program a computer to do it far better than I suspect any LLM would do.

deanCommie 3y ago
> Prior to electronic computers, groups of humans using pencil, paper, reference-tables (that themselves had been hand-calculated by humans), and slide-rules worked this way to get accurate answers to arbitrarily difficult computations. There's a scene of this in Apollo 13. Line of humans with slide rulers manually confirming calculations made on the craft whose computer is out.
WorldMaker 3y ago
Related to this topic, we still don't have a good, strong idea of how human thought works. Neural Networks/Perceptrons were built out of analogies of how human-like neurons seem to work (primarily in isolation studies in a petri dish or similar experiments), but it is very easy to forget that the model/analogy is not the reality when you work with those models a lot. The current "map" certainly doesn't seem to be the territory here. Neurons are just one part of the human brain, there's also complex chemical receptors and hormonal pathways that we mostly still only grasp in the abstract of how they interplay with neurons and other signal pathways. Additionally, there's indirect evidence that brains may take some advantage of quantum effects among/between neurons such as entangled particle states, but we don't know a lot more than we know about the quantum states of human brain activity. (How do we even probe that in a living human with our current knowledge of quantum physics?) Neural Networks/Perceptrons have been very useful models in computation, but that doesn't mean they are actually good or representative models for human cognition.

phaedrus 3y ago

To summarize my other top-level comment: I read a paper which pointed out we have no reason to believe the Chomsky hierarchy is the only formal hierarchy of languages that could exist, and the author asked why aren't we looking for other language complexity classification systems that might better match our intuitions about natural languages? Physical computers aren't Turing Complete either, because they have finite memory. That hasn't stopped us from making practical use of them.

aaroninsf 3y ago

To paraphrase The Graduate, "Recurrence, my child—recurrence!" I'd take the bet that in the medium term (whatever that means today), the Transformer architecture as implemented today will be replaced by designs which revive recurrent, non-directed architectures, with a few specific properties: • cycles will be allowed • equilibrium (over time) will serve as state ("output") • computationally this is a couple orders more expensive than current approaches, both in training and in use • investigating emergent internal encoding and computation will similarly be orders more expensive to investigate, and require nearly as expensive tools as subjects This is The Way. NB non-coincidentally this looks much more like an animal brain.