undefined | Better HN

0 pointsJerrrry1y ago0 comments

  > the open-domain Frame Problem is equivalent to the Halting Problem and is therefore undecidable.

Thank you, Code as Data problems are innate to the von Nuemman architecture, but I could never articulate how LLMs are so huge they are essentially Turing-complete and equivalent computationally.

You _can_ combinate through them, just not in our universe.

0 comments

adgjlsfhk11y ago

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

JerrrryOP1y ago

"Essentially"

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

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

Bravo.

nyrikki1y ago

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.

j / k navigate · click thread line to collapse