Ask HN: How are Markov chains so different from tiny LLMs?

> However, LLMs will not be able to represent ideas that it has not encountered before. It won't be able to come up with truly novel concepts, or even ask questions about them. Humans (some at least) have that unbounded creativity that LLMs do not.

There's absolutely no evidence to support this claim. It'd require humans to exceed the Turing computable, and we have no evidence that is possible.

If you tell me that trees are big, and trees are made of hard wood, I as a human am capable of asking whether trees feel pain. I don't think what you said is false and I am not familiar with computational theory to be able to debate it. People occasionally have novel creative insights that do not derive from past experience or knowledge, and that is what I think of when I think of creativity.

Humans created novel concepts like writing literally out of thin air. I like how the book "Guns, Steels, and Germs" describes that novel creative process and contrasts it via a disseminative derivation process.

> People occasionally have novel creative insights that do not derive from past experience or knowledge, and that is what I think of when I think of creativity.

If they are not derived from past experience or knowledge, then unless humans exceed the Turing computable, they would need to be the result of randomness in one form or other. There's absolutely no reason why an LLM can not do that. The only reason a far "dumber" pure random number generator based string generator "can't" do that is because it would take too long to chance on something coherent, but it most certainly would keep spitting out novel things. The only difference is how coherent the novel things are.

Wouldn't this insight derive from many past experiences of feeling pain yourself and the knowledge that others feel it too?

> If they are not derived from past experience or knowledge

Every animal is born with intuition, you missed that part.

Turing computability is tangential to his claim, as LLMs are obviously not carrying out the breadth of all computable concepts. His claim can be trivially proven by considering the history of humanity. We went from a starting point of having literally no language whatsoever, and technology that would not have expanded much beyond an understanding of 'poke him with the pointy side'. And from there we would go on to discover the secrets of the atom, put a man on the Moon, and more. To say nothing of inventing language itself.

An LLM trained on this starting state of humanity is never going to do anything except remix basically nothing. It's never going to discover the secrets of the atom, or how to put a man on the Moon. Now whether any artificial device could achieve what humans did is where the question of computability comes into play, and that's a much more interesting one. But if we limit ourselves to LLMs, then this is very straight forward to answer.

So knowledge encoded in the physical structure of the brain.

You're missing the part where unless there is unknown physics going on in the brain that breaks maths as me know it, there is no mechanism for a brain to exceed the Turing computable, in which case any Turing complete system is comptationally equivalent to it.

> Turing computability is tangential to his claim, as LLMs are obviously not carrying out the breadth of all computable concepts

They don't need to. To be Turing complete a system including an LLM need to be able to simulate a 2-state 3-symbol Turing machine (or the inverse). Any LLM with a loop can satisfy that.

If you think Turing computability is tangential to this claim, you don't understand the implications of Turing computability.

> His claim can be trivially proven by considering the history of humanity.

Then show me a single example where humans demonstrably exceeding the Turing computable.

We don't even know any way for that to be possible.

This is akin to claiming that a tic-tac-toe game is turing complete since after all we could simply just modify it to make it not a tic tac toe game. It's not exactly a clever argument.

And again there are endless things that seem to reasonably defy turing computability except when you assume your own conclusion. Going from nothing, not even language, to richly communicating, inventing things with no logical basis for such, and so is difficult to even conceive as a computable process unless again you simply assume that it must be computable. For a more common example that rapidly enters into the domain of philosophy - there is the nature of consciousness.

It's impossible to prove that such is Turing computable because you can't even prove consciousness exists. The only way I know it exists is because I'm most certainly conscious, and I assume you are too, but you can never prove that to me, anymore than I could ever prove I'm conscious to you. And so now we enter into the domain of trying to computationally imagine something which you can't even prove exists, it's all just a complete nonstarter.

-----

I'd also add here that I think the current consensus among those in AI is implicit agreement with this issue. If we genuinely wanted AGI it would make vastly more sense to start from as little as possible because it'd ostensibly reduce computational and other requirements by many orders of magnitude, and we could likely also help create a more controllable and less biased model by starting from a bare minimum of first principles. And there's potentially trillions of dollars for anybody that could achieve this. Instead, we get everything dumped into token prediction algorithms which are inherently limited in potential.

> This is akin to claiming that a tic-tac-toe game is turing complete since after all we could simply just modify it to make it not a tic tac toe game. It's not exactly a clever argument.

No, it is nowhere remotely like that. It is claiming that a machine capable of running a Turing machine is in fact capable of running any other Turing machine. In other words, it is pointing out the principle of Turing equivalence.

> And again there are endless things that seem to reasonably defy turing computability

Show us one. We have no evidence of any single one.

> It's impossible to prove that such is Turing computable because you can't even prove consciousness exists.

Unless you can show that humans exceeds the Turing computable, "consciousness" however you define it is either possible purely with a Turing complete system or can not affect the outputs of such a system. In either case this argument is irrelevant unless you can show evidence we exceed the Turing computable.

> I'd also add here that I think the current consensus among those in AI is implicit agreement with this issue. If we genuinely wanted AGI it would make vastly more sense to start from as little as possible because it'd ostensibly reduce computational and other requirements by many orders of magnitude, and we could likely also help create a more controllable and less biased model by starting from a bare minimum of first principles. And there's potentially trillions of dollars for anybody that could achieve this. Instead, we get everything dumped into token prediction algorithms which are inherently limited in potential.

This is fundamentally failing to engage with the argument. There is nothing in the argument that tells us anything about the complexity of a solution to AGI.

You are making a big assumption here, which is that LLMs are the main "algorithm" that the human brain uses. The human brain can easily be a Turing machine, that's "running" something that's not an LLM. If that's the case, we can say that the fact that humans can come up with novel concept does not imply that LLMs can do the same.

No, I am not assuming anything about the structure of the human brain.

The point of talking about Turing completeness is that any universal Turing machine can emulate any other (Turing equivalence). This is fundamental to the theory of computation.

And since we can easily show that both can be rigged up in ways that makes the system Turing complete, for humans to be "special", we would need to be able to be more than Turing complete.

There is no evidence to suggest we are, and no evidence to suggest that is even possible.

An LLM is not a universal Turing machine, though. It's a specific family of algorithms.

You can't build an LLM that will factorize arbitrarily large numbers, even in infinite time. But a Turing machine can.

To make a universal Turing machine out of an LLM only requires a loop and the ability to make a model that will look up a 2x3 matrix of operations based on context and output operations to the context on the basis of them (the smallest Turing machine has 2 states and 3 symbols or the inverse).

So, yes, you can.

Once you have a (2,3) Turing machine, you can from that build a model that models any larger Turing machine - it's just a question of allowing it enough computation and enough layers.

It is not guaranteed that any specific architecture can do it efficiently, but that is entirely besides the point.

Turing machines are deterministic, brain might not be because of quantum mechanics happening. Of course there is no proof that this is related to creativity.

LLMs are not capable of simulating turing machines - their output is inherently and inescapably probabilistic. You would need to fundamentally rewrite one to make this possible, at which point it is no longer an LLM.

And as I stated, you are assuming your own conclusion to debate the issue. You believe that nothing is incomputable, and are tying that assumption into your argument as an assumption. It's not on me to prove your assumption is wrong, it's on you to prove that it's correct - proving a negative is impossible. E.g. - I'm going to assume that there is an invisible green massless goblin on your shoulder named Kyzirgurankl. Prove me wrong. Can you give me even the slightest bit of evidence against it? Of course you cannot, yet absence of evidence is not evidence of absence, so the burden of my claim rests on me.

And so now feel free to prove that consciousness is computable, or even replicating humanity's successes from a comparable baseline. Without that proof you must understand that you're not making some falsifiable claim of fact, but simply appealing to your own personal ideology or philosophy, which is of course completely fine (and even a good thing), but also a completely subjective opinion on matters.

Are you saying that LLMs are Turing complete or did I misunderstand it?

This Turing completeness equivalence is misleading. While all Turing-complete systems can theoretically compute the same class of functions, this says nothing about computational complexity, physical constraints, practical achievability in finite time, or the actual algorithms required. A Turing machine that can theoretically simulate a brain does not mean we know how to do it or that it is even feasible. This is like arguing that because weather systems and computers both follow physical laws, you should be able to perfectly simulate weather on your laptop.

Additionally, "No mechanism to exceed Turing computable" is a non-sequitur. Even granting that brains do not perform hypercomputation, this does not support your conclusion that artificial systems are "computationally equivalent" to brains in any practical sense. We would need: (1) complete understanding of brain algorithms, (2) the actual data/weights encoded in neural structures, (3) sufficient computational resources, and (4) correct implementation. None of these follow from Turing completeness alone, I believe.

More importantly, you completely dodged the actual point about intuition. Jensson's point is about evolutionary encoding vs. learned knowledge. Intuition represents millions of years of evolved optimization encoded in brain structure and chemistry. You acknowledge this ("knowledge encoded in physical structure") but then pivot to an irrelevant theoretical CS argument rather than addressing whether we can actually replicate such evolutionary knowledge in artificial systems.

Your original claim was "If they are not derived from past experience or knowledge" which creates a false dichotomy. Animals are born with innate knowledge encoded through evolutionary optimization. This is not learned from individual experience, yet it is still knowledge, specifically, it is millions of years of selection pressure encoded in neural architecture, reflexes, instincts, and cognitive biases.

So, for example: a newborn animal has never experienced a predator but knows to freeze or flee from certain stimuli. It has built-in heuristics for threat assessment, social behavior, spatial reasoning, and countless other domains that cost generations to develop through survival pressure.

Current AI systems lack this evolutionary substrate. They are trained on human data over weeks or months, not evolved over millions of years. We do not even know how to encode this type of knowledge artificially or even fully understand what knowledge is encoded in biological systems. Turing completeness does not bridge this gap any more than it bridges the gap between a Turing machine and actual weather.

Correct me if I'm misinterpreting your argument.

Turing machines are deterministic if all their inputs are deterministic, which they do not need to be, and if we allow them to be. Indeed, by default, LLMs are by default not deterministic because we intentionally inject randomness.

It doesn't mean we can accurately simulate the brain by swapping its source of nondeterminism with any other PRNG or TRNG. It might just so happen that to simulate ingenuity you have to simulate the universe first.

LLMs cannot loop (unless you have a counterexample?), and I'm not even sure they can do a lookup in a table with 100% reliability. They also have finite context, while a Turing machine can have infinite state.

After having read your comment, I feel I should have left my comment under this thread. I will just refer to it instead: https://news.ycombinator.com/item?id=46003870. This was my reply to your parent. I agree with you.

I...I am very interested in this subject. There's a lot to unpack in your comment, but I think it's really pretty simple.

> this does not support your conclusion that artificial systems are "computationally equivalent" to brains in any practical sense.

You're making a point about engineering or practicality, and in that sense, you are absolutely correct.

That's not the most interesting part of the question, however.

> This is like arguing that because weather systems and computers both follow physical laws, you should be able to perfectly simulate weather on your laptop.

Yes, that's exactly what I'd argue, and...hm.. yes, I think that's clearly true. Whether it takes 10 minutes or 10^100 minutes, 1~ or 10^100 human lifetimes to do so, it's irrelevant. Units (including human lifetimes) are arbitrary, and I think fundamental truths probably won't depend on such arbitrary things as how long a particular collection of atoms in a particular corner of the universe (i.e. humans) happens to be stable for. Ratios are closer to being fundamental, but I digress.

To put it a different way - we think we know what the speed of light is. Traveling at v = 0.1c or at v = (1 - 10^(-100))c are equivalent in a fundamental sense, it's an engineering problem. Now, traveling at v = c...that's very different. That's interesting.

If the brain does not exceed the Turing computable, then it does mean it is possible to accurately simulate the brain. Not only that, but in that case the brain itself is existence proof that doing so efficiently is possible.

If the brain exceeds the Turing computable, then all bets are off, but we have no evidence to suggest it does, nor that doing so is possible. This was in fact my original argument.

The only viable counter to my argument is demonstrating that there are computable functions outside the Turing computable, and that humans can compute them.

> While all Turing-complete systems can theoretically compute the same class of functions, this says nothing about computational complexity, physical constraints, practical achievability in finite time, or the actual algorithms required.

True. But if the brain is limited to the Turing computable, then the brain itself is existence proof it is possible to do so efficiently. It might require a different architecture, but that is a detail.

Personally I think that we have gotten this far this quickly with brute force suggests that the problem is fairly tractable, but it may in fact turn out to be much harder than we think.

The point is that when people dismiss it as impossible, that is a belief not backed up by any evidence.

> Additionally, "No mechanism to exceed Turing computable" is a non-sequitur. Even granting that brains do not perform hypercomputation, this does not support your conclusion that artificial systems are "computationally equivalent" to brains in any practical sense. We would need: (1) complete understanding of brain algorithms, (2) the actual data/weights encoded in neural structures, (3) sufficient computational resources, and (4) correct implementation. None of these follow from Turing completeness alone, I believe.

Computationally equivalent here refers to any two Turing complete systems being able to compute all functions that the other can, and so on that basis all four of your points are irrelevant to the question I addressed.

> yet it is still knowledge

You claim my statement creates a false dichotomy, but here you concede it is not.

> Current AI systems lack this evolutionary substrate.

That is irrelevant to the question of whether it is possible. That's an engineering problem, not a fundamental limitation.

> Correct me if I'm misinterpreting your argument.

It seems you're arguing difficult and complexity, while I argued over possibility. Your argument is mostly not relevant to mine for that reason. Most of it is not unreasonable, it just does not say anything about the possibility.

> LLMs are not capable of simulating turing machines - their output is inherently and inescapably probabilistic.

This is fundamentally not true. Inference code written to be numerically stable and temperature set to 0 is all you need for an LLM to be entirely deterministic.

> And as I stated, you are assuming your own conclusion to debate the issue. You believe that nothing is incomputable, and are tying that assumption into your argument as an assumption.

This is categorically also false. Please do not make a position for me that I have at no point in my life claimed. I believe plenty of things are incomputable. That is provable the case. What I have repeatedly said is that we have no evidence to show 1) that there are computable functions that exceed the Turing computable, 2) that the brain are capable of computing such functions that exceeds the Turing computable.

If you have evidence of either of those two, please do feel free to provide it - it would be earth-shattering news. It'd revolutionise physics, as it'd involve unknown interactions, it'd revolutionise maths and computer science by forcing us to throw out areas of theory of computation.

> It's not on me to prove your assumption is wrong, it's on you to prove that it's correct - proving a negative is impossible.

That the Turing computable set of functions is the totality of computable functions is not a claim I've come up with.

If you want to make the extraordinary claim that there are computable functions outside that, despite no extant evidence, then since you've invoked a weird version of Russels teapot, that requires extraordinary proof.

And it is not impossible: A single example of a computable function outside the Turing computable would falsify the underlying claim. A single example of humans being able to compute such a function would falsify the claim that Turing equivalence has relevance here.

I've been very careful throughout to make clear that my arguments hinges on humans being unable to exceed the Turing computable.

I don't believe we should talk in absolutes when we can't prove it, hence my challenge to the people here who are so absolutely certain about the limitations of LLMs to show just a single example of humans exceeding the Turing computable.

Because you are so certain, the surely there lies something behind that certainty other than blind faith?

> And so now feel free to prove that consciousness is computable

At no point have I made claims about "consciousness". Before I'd do that, you'd need to define in an objective way what you mean. It is an entirely separate question from the ones I've addressed.

> Without that proof you must understand that you're not making some falsifiable claim of fact

As noted, my claims are falsifiable: Show a single example of a function that exceeds the Turing computable, that humans can compute.

If your argument is that a system incorporating a model is not an LLM if there is a loop around it, then reasoning models are not LLMs.

They can do lookup in a table with 100% reliability, yes, because you can make then 100% deterministic if you wish by using numerically stable inferencing code and setting temperature to 0.

Finite context is irrelevant, because the context can be used as an IO channel.

A Turing machine does not have infinite state within the mechanism itself - it requires access to a potentially infinite tape. A Turing machine can be constructed with down to 1 bit of state (a (2,3) or (3,2) Turing machine are the smalles possible, where one number represents the number of states, and the other represents number of discrete symbols it can handle).

An IO channel is computationally equivalent to an infite tape, and unlike an infinite tape, an IO channel is physically possible.

An LLM in itself is inert - it's just the model, so when talking about an LLM doing anything it is doing so as part of an inference engine. An inference system with a loop is trivially Turing complete if you use the context as an IO channel, use numerically stable inferencing code, and set temperature to 0 - in that case, all you need is for the model to encode a 6 entry lookup table to operate the "tape" via context.

You write (as a response to someone else in this thread): "If the brain is limited to the Turing computable, then the brain itself is existence proof it is possible to do so efficiently."

No. The brain is existence proof that that particular physical substrate can achieve intelligence efficiently. A bird is existence proof that flight is possible efficiently, but not that elephants can fly. You are claiming "computational equivalence" means any Turing-complete system can efficiently replicate any other, but this does not follow from Turing's thesis at all.

You say: "Computationally equivalent here refers to any two Turing complete systems being able to compute all functions that the other can."

But then you make claims about replicating brain capabilities. These are different things. A Python interpreter and raw transistors are Turing-equivalent, but we do not conclude Python can efficiently do what transistors do. The abstraction layers, the architecture, the implementation: these all matter for the actual question at hand.

You dismiss the evolutionary substrate: "That is irrelevant to the question of whether it is possible. That's an engineering problem, not a fundamental limitation.".

This concedes the key point. You are now admitting current AI systems lack something the brain has (millions of years of encoded optimization), then handwaving it away as "just engineering". But the original discussion was whether LLMs as currently implemented can represent truly novel ideas. You have retreated to arguing about theoretical possibility with complete knowledge and arbitrary resources.

Finally: "It seems you're arguing difficult and complexity, while I argued over possibility."

Exactly. Your argument has contracted from making claims about actual LLM capabilities to an unfalsifiable position about theoretical possibility. In the sense you are now defending, it is "possible" that monks with abacuses could run Crysis given infinite time and perfect execution. This tells us nothing interesting about whether current LLMs have unbounded creativity.

Perhaps I am misunderstanding your original argument. Could you clarify what your argument is exactly? I want to make sure we are not talking past each other.

> No. The brain is existence proof that that particular physical substrate can achieve intelligence efficiently.

So in other words, it is existence proof that it can be done efficiently. You arbitrarily applied your false beliefs about what that statement implied.

If you want to claim that we don't have any evidence that it can be done in an arbitrary substrate, then you'd be right, but that is entirely separate argument I have no interest in.

> You are claiming "computational equivalence" means any Turing-complete system can efficiently replicate any other, but this does not follow from Turing's thesis at all.

I have never in my life made that claim.

I have at times argued I believe that efficiency is "just" an engineering problem, but I have certainly not ever argued that computational equivalence proves that.

Again you are falsely attributing opinions to me I do not hold, and it's frankly offensive that you keep attrbuting to me things I not only have not said, but do not agree with.

> The abstraction layers, the architecture, the implementation: these all matter for the actual question at hand.

They do not at all matter for the question of whether one architecture is theoretically capable of computing the same as the other, which is what I have argued it is.

> This concedes the key point.

It concedes nothing. It pointed out that my argument was about whether LLMs can be made to "represent ideas that is has not encountered before" and "come up with truly novel concepts".

Those were the claims I stated has no evidence in favour of them. Nothing of what you have written in any of your responses have any relevance to that.

As you concede:

> Exactly.

Then you go on to make another false assertion about what I have said:

> Your argument has contracted from making claims about actual LLM capabilities to an unfalsifiable position about theoretical possibility.

It has done nothing of the sort. You have repeatedly tried to argue against a position I did not take, by repeatedly misrepresenting what I have claimed, as this quoted statement also does.

There is also nothing unfalsificable about my claim:

Show that humans can compute even a single function outside the Turing computable, and my argument is is proven false.

> In the sense you are now defending, it is "possible" that monks with abacuses could run Crysis given infinite time and perfect execution. This tells us nothing interesting about whether current LLMs have unbounded creativity.

This is the only thing I have been defending. It may not be interesting to you, but to be it matters because without it being possible, there is no point in even arguing over whether it is practical.

If said Crysis-executing monks were fundamentally limited in a way that made it impossible for them to execute the steps, then it would be irrelevant whether or not there were ways for them to speed it up (say, by building computers...).

Since I was arguing against someone who denied the possibility that is the only argument I had any reason to make.

> Perhaps I am misunderstanding your original argument. Could you clarify what your argument is exactly? I want to make sure we are not talking past each other.

I told you how you misunderstood my original argument: I've argued over possibility. I've not made any argument about difficulty or complexity.

You've gone out to falsely and rudely claim that my argument has shifted, but it has not.

Here is my first comment in this sub-thread, where I state there is no evidence to support a claim that LLMs "will not be able to represent ideas that it has not encountered before" and won't be able to "come up with truly novel concepts". My original claim didn't even extent to claim full computational equivalence, because it was not necessary.

https://news.ycombinator.com/item?id=45996749

Exactly this. I would argue that I believe doing it efficiently is "just engineering", but I would not claim we know that to any reasonable amount of certainty.

I hold beliefs about what LLMs may be capable of that are far stronger than what I argued, but stated only what can be supported by facts for a reason:

That absent evidence we can exceed the Turing computable, we have no reason to believe LLMs can't be trained to "represent ideas that it has not encountered before" or "come up with truly novel concepts".

I will get back to this later, but I literally quoted you and I replied to what I quoted you said, so you cannot say that I made it up myself when I quoted you verbatim and then responded to that.

In one instance you did say "If the brain is limited to the Turing computable, then the brain itself is existence proof it is possible to do so efficiently.", for example, and I explained why it is not the proof you thought it was.

In any case, no hard feelings. I will get back to you in a minute.

Setting the temperature to 0 doesn't make an LLM non-probabilistic. Once again, LLMs are inherently probabilistic. All setting the temperature to 0 does is make it always choose the highest probability token instead of using a weighted randomization. You'll still get endless hallucinations and the same inherent limitations, including the inability to reliably simulate a turing machine.

As for the rest of your post, you are again, consciously or not, trying to say 'give me a calculable function that isn't a calculable function.' I obviously agree that the idea of trying to 'calculate' consciousness is essentially a non-starter. That's precisely the point.

"To be Turing complete a system including an LLM need to be able to simulate a 2-state 3-symbol Turing machine (or the inverse)."

And infinite memory. You forgot the infinite memory. And LLMs are extremely inefficient with memory. I'm not talking about the memory needed in the GPU to store the weights, but rather the ability of an LLM to remember whatever it's working on at the moment.

What could be stored as a couple of bits in a temporary variable is usually output as "Step 3: In the previous step we frobbed the junxer and got junx, and if you do junx + flibbity you get floopity"

And remember that this takes up a bunch of tokens. Without doing this (whether the LLM provider decides to let you see it or not, but still bill you for it), an LLM can't possibly execute an algorithm that requires iteration in the general case. For a more rigorous example, check apple's paper where an LLM failed to solve a tower of hanoi problem even when it had the exact algorithm to do so in context (apart from small instances of the problem for which the solution is available countless times).