[Maxatar]

So unless I'm mistaken, the TL;DR is that GPTs inherently can not be Turing complete because they always terminate, ie. there is always a non-zero probability of the end-of-token character to be generated.

Seems like a fair argument to raise, although not too insightful.

As a nitpick, it really is not the case that most programming languages are context-free, but I can sympathize with what the author is trying to get at. Most programming languages have a context-free superset that is useful to use as one of many stages in the parsing pipeline, before type checking and name resolution etc... but apart from perhaps some dynamically typed programming languages, the vast majority of programming languages are context-sensitive, not context-free.

[onraglanroad]

> GPTs inherently can not be Turing complete because they always terminate

I'm not sure that was intended entirely seriously. After all, humans always terminate too...

[bigfishrunning]

To follow on logically, maybe humans aren't Turing complete? we are not equivalent to Turing machines...

[FeepingCreature]

No machine instantiated in the physical universe is Turing complete in this sense.

[thaumasiotes]

You can do everything a Turing machine can do; obviously, you cannot fail to be Turing complete.

[wat10000]

We can simulate a Turing machine, given storage. The infinite storage and infinite time is always a sticking point when comparing any real physical system to a theoretical Turing machine, so we tend to ignore those bits.

[tshaddox]

"Unbounded" is a better term to use than "infinite."

[prolyxis]

Except that as far as I understand, one of the inspirations for the Turing machine is to explain precisely the computations a human computer could perform with (potentially a lot of) pen and paper.

[nkrisc]

Theoretically, not in any sense of reality.

[stormking]

And an unlimited life span.

[arjvik]

As a quick hack, is this flaw fixed by using top-p or top-k or min-p or whatever the current hottest logit sampling algorithm is?

[FeepingCreature]

The "flaw" is also fixed by simply not recognizing the end-of-sampling token. Even the limited size of the context window can be worked around with tool calls.

[fi-le]

Thank you for the nitpick, corrected!