undefined | Better HN

0 pointsYeGoblynQueenne3y ago0 comments

>> No worries, you were right on your assumption, I am a programmer, like you seem to be as well.

Of course :)

>> I don’t know if it’s been formally verified, but it’s pretty safe to bet that ChatGPT is Turing Complete. If so, than your statement is false. ChatGPT can emulate every computable problem.

I think that's unlikely. For Universal Turing Machine expressivity, a system needs to have something to function as an infinite Turing tape, and where's that in an LLM? ChatGPT famously has a limited input buffer and it doesn't even have a memory, as such (it forgets everything you tell it, hence why a user's input and its own answers have to be fed back to it continuously during a conversation or it loses the thread).

Besides, OpenAI themselves, while they have made some curious claims in the past (about GPT-3 calculating arithmetic) seem to have backtracked recently and nowadays if you ask ChatGPT to calculate the result of a computation it replies with a sort-of-canned reply that says it's not a computer and can't compute. Sorry I don't have a good example, I've seen a few examples of this with Python programs and bash scripts.

Anyway you could easily test whether ChatGPT (or any LLM) is computing: ask it to perform an expensive computation. For example, ask it to compute the Ackermann function for inputs 10,20, which should take it a few hundred years if it's actually performing a computation. Or ask it to generate the first 1 million digits of pi. It will probably come up with a nonsense answer or with one of it's "canned" answers, so it should be obvious it's not computing the result of the computation you asked it to.

Btw, I think one could argue that a Transformer architecture is Turing-complete, in the sense that it could be, in principle, trained to simulate a UTM; I seem to remember there are similar results for Recurrent Neural Networks (which are, however, a different architecture). But a Transformer trained to generate text is trained to generate text, not to simulate a UTM.

0 comments

tambourine_man3y ago

> infinite Turing tape

That's the ideal machine Turing describes, but it's a very narrow definition we don't really use. If that were the case, nothing would ever be Turing-complete, not even the computer we are writing this on. If we can consider a cellular automaton and even the single x86's MOV instruction Turing-complete, I'm pretty sure ChatGPT will qualify.

>it doesn't even have a memory, as such (it forgets everything you tell it…

It really doesn't. Have you tried it? You can bring back context from several prompts before. One of the remarkable things about it, in fact.

>Btw, I think one could argue that a Transformer architecture is Turing-complete

Bingo. And you can probably tweak your prompt to steer it. The things people at Reddit have been able to persuade ChatGTP to do against its directives is tantalizing.

YeGoblynQueenneOP3y ago

For a UTM, you need something to function as an infinite Turing tape. For example a mechanism that can loop arbitrarily. On a machine with finite resources, running an infinite program will exhaust the machine's resources. But ChatGPT has nothing like that.

As to ChatGPT's memory that's not about UTM expressivity, but another reason why it can't be any kind of computing device.

ChatGPT and other language models of its kind don't have memories. It can retrieve context from earlier prompts because each of your prompts, and the language model's responses to your prompts, are prepended to your latest prompt and then the whole thing passed to the model. It doesn't remember what you said earlier, it just reads it again each time.

Finally, a neural net architecture and a trained model are two different things. For example, you could train one Convolutional neural net to recognise cats, and another to recognise dogs. Suppose you could train a Transformer to simulate a UTM. ChatGPT is not trained to simulate a UTM, it's trained to predict text. So it can't simulate a UTM.

But, after all this discussion I have to ask: why do you say that "it’s pretty safe to bet that ChatGPT is Turing Complete"? What does ChatGPT have in common with cellular automata, for instance?

j / k navigate · click thread line to collapse