Remix.run Logo
vidarh 3 days ago

We don't have hard evidence that no other functions exist that are computable, but we have no examples of any such functions, and no theory for how to even begin to formulate any.

As it stands, Church, Turing, and Kleene have proven that the set of generally recursive functions, the lambda calculus, and the Turing computable set are equivalent, and no attempt to categorize computable functions outside those sets has succeeded since.

If you want your name in the history books, all you need to do is find a single function that humans can compute that a is outside the Turing computable set.

As for LLMs, you can trivially test that they can act like a Turing machine if you give them a loop and use the context to provide access to IO: Turn the temperature down, and formulate a prompt to ask one to follow the rules of the simplest known Turing machine. A reminder that the simplest known Turing machine is a 2-state, 3-symbol Turing machine. It's quite hard to find a system that can carry out any kind of complex function that can't act like a Turing machine if you allow it to loop and give it access to IO.