P.S. I'm graduating soon and looking for research scientist roles.
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.
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.
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.
I'm pretty sure that you were making a tangent rather than a rebuttal, but I did want to clarify that I'm not saying that these large models replicate the structural thinking of humans. Instead I'm saying that, given a ML model that is "sufficiently human like" in the mistakes it makes, using techniques that prevent humans from making those mistakes (e.g. showing work, having multiple agents calculate in parallel) could demonstrate an ability to solve problems that the ML model itself appears incapable of solving.
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.
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?
What seems like an even better formal solution is something like logical induction[0] that works over something like probabilities instead of truth/falsehood. It has an existence proof but not a constructive formalization, afaik, but maybe some recent progress has been made.
>> I think that Penrose basically thinks it's useful that humans can heuristically step up from a logic system S to S+"statement X is true" in an almost-grounded way, but in reality we are all actually constrained by Godel, Tarski, etc. We just trick ourselves into assuming we can inductively keep stepping up from S+"X is true" indefinitely for any practical problem we encounter, but that is actually an ungrounded assumption.
What you describe sounds to me more like logical abduction, rather than induction. Unfortunately, it's difficult to find simple explanations of what abduction is. One very rough and operational categorisation of modes of inference, as deductive, inductive or abductive, is as follows. Deduction is reasoning (as in automated theorem proving or rule-based systems), induction is learning (as in machine learning) and abduction is reasoning under uncertainty (as in probabilistic inference).
There's a lot of confusion between what is abduction and what is induction, and the definitions of those in terms of "facts" and "rules" (coming from Peirce, who originally named "abduction" at least) is, for me, not very helpful. Another colloquial explanation is that abduction is a form of drawing conclusions from observations that isn't sound, so that conclusions are not necessarily true. I think that's where the association with probabilistic reasoning comes from, and that's why I think it describes better the kind of induction the linked paper is talking about.
Anyway I'll have to read that, thanks.
This depends on S being consistent. Lucas and Penrose apparently suppose that any proposal for explaining thinking as a computational process would, ipso facto, cast a mind as a concrete instantiation of a consistent formal system. [2]
Putting aside any thoughts of whether this is persuasive, I think this seems to be a case of Lucas and Penrose doing what they claim is uniquely human: thinking outside of the box of formal proof. More generally, almost none of human knowledge is couched as a formal proof of something or other, and almost none of it has been acquired that way.
[1] More precisely, one in which a “moderate amount of number theory” can be proven.
[2] J.R.Lucas, "Minds, Machines and Gödel", 1961.
Well, except for all of mathematics :P
Then again, it's useful to wonder what, exactly, is a formal proof, when derived by a human. My understanding of proofs (after having had to come up with several for my PhD research) is that the purpose of a proof is to convince a human that what the associated theorem states, is true. The human is first of all the person stating the theorem, so for example these days at least when I write down a theorem, the next thing I do is ask myself out loud "why do I think this is true?". Then I try to write it down in simple English, and then I try to put it in the standard format of an inductive proof, or a proof by refutation- and I do that only because those are proof structures that are well understood and they will cause the least confusion about what I mean. Even so I've got proofs wrong and I had reviewers pick out my mistakes and help me correct them, which is a bit of a "phew, dodged a bullet" (worst case is you get your erroneous proof published and look like an idiot for eternity).
Btw, I picked up that idea that the purpose of proofs is to convince others (other mathematicians) from some article or paper I read about proofs in mathematics, but I have no idea which one it was now. Anyway it's not my own idea, I just found it somewhere and it made a lot of sense, and still does.
Then there's the proofs you can construct with an automated theorem prover. I wonder if that's more the kind of proof that Penrose is talking about? In a sense, I don't think any human can really really construct an entire proof. All the proofs I've seen (and all the ones I've written) are more correctly proof sketches. That's why I think their point is only to convince others that what you say is true, and not to uncover some fundamental truth about the nature of the universe. Humans don't do that. I don't think we can do that. Formal systems like arithmetic or logic try to capture what is our ideal reasoning procedure, but not what we do in practice. I think so anyway.
>> This depends on S being consistent. Lucas and Penrose apparently suppose that any proposal for explaining thinking as a computational process would, ipso facto, cast a mind as a concrete instantiation of a consistent formal system.
I haven't read Lucas' and Penrose's work but I would find it very hard to be convinced about the truth of that.
I don't understand how humans reason. I can see what I do, and what others do, but after a certain point all models seem to break down and minds seem capable of just jumping to conclusions because they like them. It's such a huge question how our minds work, exactly. I will probably never know.
Don't put too much trust in what I wrote about how Penrose deals with the consistency issue; it's been a long time since I read his first book, I never did read the second (his response to criticism of the first), and I put that paragraph together from a couple of hours 'refresher' on the internet. I am reasonably sure, however, in my recollection that Penrose, following Lucas, constructed his argument from the formality of Turing machines and the Turing-equivalence of programming languages. Theorem provers demonstrate that it is possible for computers to produce formal arguments, but that is not sufficient for his purpose, which is to show that computers cannot do something that human minds can do.
On the other hand, I am guessing that it would be relatively straightforward to take a theorem-prover and modify it so that its logic is inconsistent? If I am not mistaken, this is a question you are well-positioned to answer, so your comments would be appreciated. If inconsistent theorem "provers" are possible, this would seem to defeat Penrose's argument, unless one adds the premise that humans are consistent reasoners, which seems to me to be obviously false.
Personally, I believe that human minds have evolved via natural selection from precursors that are, broadly speaking, understandable, and have probably done so without the intercession of currently-unknown fundamental physics or extra-physical causes, so I take an interest in arguments claiming that this cannot possibly be so, or that they could not possibly be simulated by a digital computer. Nevertheless, I agree entirely with your last paragraph.
>> On the other hand, I am guessing that it would be relatively straightforward to take a theorem-prover and modify it so that its logic is inconsistent? If I am not mistaken, this is a question you are well-positioned to answer, so your comments would be appreciated. If inconsistent theorem "provers" are possible, this would seem to defeat Penrose's argument, unless one adds the premise that humans are consistent reasoners, which seems to me to be obviously false.
Yes, you could modify an automated theorem prover to be inconsistent, or unsound, in fact you could do that in many different ways. My specialty is Resolution-based theorem proving. While Resolution is sound and complete in principle, in practice it doesn't make sense to consider it so except under the Closed World Assumption (CWA). The CWA, very simply stated is that only what is currently known, either as axiomatic truths or theorems derived from those, is true, and everything else is false. That might sound dumb, but it's actually one of the simplest ways to deal with uncertainty: anything that can't be known with certainty is set aside. The good thing of course is that the CWA does not have to be seen as a static assumption. In particular, it is a very well known fact that if new information is received, under a CWA (more precisely, with Negation-As-Failure, under a CWA) the set of logical consequences of a theory can both increase, and decrease - non-monotonically. What that means, in practice, is that, under the CWA, beliefs can be updated as new information comes in, so that a reasoner doesn't have to be stuck forever in a "bad world" entailed by a faulty set of initial assumptions.
In a sense, given a sound and complete inference rule like Resolution, the CWA means a reasoning system can be "locally consistent" without having to be "globally consistent". It can be right for what it knows for sure, without having to worry too much about what it doesn't know, because once unknowns become known, local consistency kicks in and the reasoner's model of the world is updated to better approximate reality. Unfortunately most of that remains mainly theoretical. To my knowledge nobody has really gone and built a system that learns continuously by exploiting the non-monotonicity of Resolution under a CWA. Although people have build systems, they tend to be academic prototypes, that are only described in a couple of papers at most and then forgotten about.
There's another way in which Resolution can be inconsistent ("inconsistent" is a very loose term, I hope I'm using it right :). That is by performing induction, or abduction. Normally, Resolution is deductive: one has a theory (in practice that's a logic program, a set of definite clauses) and proves new consequences of the theory. In the Inductive use of Resolution ("Meta-Interpretive Learning"... doesn't quite roll off the tongue, I know) one has some background theory and some observations not covered by the theory, and Resolution is used to add clauses to the theory so that it "covers" the new observations. In abduction, the premises of the theory, its very axioms, are updated.
In both cases, reasoning is unsound. In induction, because we can never observe every logical consequence of a new theory that we derive from some small number of observations, so we can never verify the theory (but we can falsify it). In abduction, because axioms are by their nature unsound, arbitrary assumptions that are not provable and we only hold true by choice.
I guess all this is very abstract and will sound vague, so sorry about that. Note also that it's all a drastic departure from classical logic, that assumes that everything to be known is known, and knowable (although maybe undecidable). There's a certain opinion that non-monotonic reasoning is closer to human reasoning, because of its ability to be locally consistent and globally who-cares. I don't know about human-like, but it certainly seems like a good way to approach the real world, with all its uncertainties, where we nevertheless want to have good answers that we can rely on.
Let me know if you would like to read further on all this and I can give some pointers.
""" 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-memor...
[1] https://ourworldindata.org/grapher/historical-cost-of-comput...
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.
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}')
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)
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]
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).
Show the full output of this Python script in a single code block, with no other commentary:
```
lst = [1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0]
x = 0
for i, bit in enumerate(lst):
x ^= bit
print(x)
```
Show the full output of this Python script in a single code block, with no other commentary:
```
lst = [1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0]
for i, bit in enumerate(lst):
print(f"{i}:{bit}")
x = 0
for i, bit in enumerate(lst):
x ^= bit
print(f"{i}:{bit}:{x}")
```Prompt:
Can you write out this sequence 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 to the output, but write it one character longer each line?
Sure, here is the sequence written out one character longer each line:
0
0 0
0 0 0
0 0 0 1
0 0 0 1 1
0 0 0 1 1 1
0 0 0 1 1 1 0
0 0 0 1 1 1 0 1
0 0 0 1 1 1 0 1 0
0 0 0 1 1 1 0 1 0 1
0 0 0 1 1 1 0 1 0 1 1
0 0 0 1 1 1 0 1 0 1 1 1
0 0 0 1 1 1 0 1 0 1 1 1 0
0 0 0 1 1 1 0 1 0 1 1 1 0 1
0 0 0 1 1 1 0 1 0 1 1 1 0 1 1
0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0
0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1
0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1
0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0
0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1
I used this prompt to get it to compute semi-reliably for 16+ digit sequences.
Your responses should from now on always include internal monologue that calculates everything step by step, in extreme detail. Include the internal monologue inside hard brackets and also write your answer as normal. For example:
Input: How many 1's are there in the sequence 1 1 0 1 1 0?
Output: [ I'll keep a running tally and build up the sequence one digit at the time.
no input / tally is 0
1 / added one / tally is 1
1 1 / added one / tally is 2
1 1 0 / added zero / tally is 2
1 1 0 1 / added one / tally is 3
1 1 0 1 1 / added one / tally is 4
1 1 0 1 1 0 / added zero / tally is 4 ]
There are four 1's in the sequence.
How many 1's are there in the sequence 1 1 0 0 0 1 1 1 1 0 0 0?That’s what I saw too, errors coming in around item 16 to 30, depending on small changes in the requested output. It looked like it was reading the wrong items from the list, possibly the attention was at slightly the wrong position. It would be interesting to know how that error changes, eg, is it tending to read earlier or later items?
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.
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.
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.
Instruction tuned LLMs as chat bots receive multiple inputs in a sequence, interspersed with computation to produce output tokens. Those output tokens appear to be able to act like short term memory.
For example, this ChatGPT 3.5 prompt appears to work well:
You will act as a parity calculator. Ask me for each bit in turn. The parity value starts at 0, an is updated with xor using each new bit. Print out the updated value after each new bit is processed.
Got it, so we'll apply the XOR operation between the current parity value (1) and the new bit (1), which gives us 0.
The updated parity value is 0.
What is the next bit?
I also spotted a typo: "cumptation".
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.