Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

this is very wrong. LLMs are very much not Turing complete, but they are algorithms on a computer so they definitely can't compute anything uncomputable


"Essentially"

This is the #1 pedantic thing HN frequenters flail over.

Turing built a limited machine, bound to a finite tape.

Bravo.


Turing machines are typically described as having an infinite tape. It may not be able to access that tape in finite time, but the tape is not bound to a finite tape

But it doesn't matter, it is an abstract model of computation.

But it doesn't matter Church–Turing thesis states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.

It doesn't matter if you put the algorithm on paper, on 1 or k tapes etc...

Rice's theorem I mentioned above is like Scott–Curry theorem in Lambda calculus. Lambda calculus is Turing complete, that is, it is a universal model of computation that can be used to simulate any Turing machine.

The similar problems with 'trivial properties' in TMs end up being recursively inseparable sets in Lambda calculus.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: