Unraveling the Algorithm of Truth: From Hilbert to Turing 🧠

Self referential logic, from Hilbert's decision problem to Turing's halting problem. Tiny programming examples are given in JavaScript.

See also:
A slow and beautiful guided tour of Lambda calculus, in Python:
http://matt.might.net/articles/python-church-y-combinator/


A much faster tour of Lambda calculus and the Y combinator, in JavaScript:
https://raganwald.com/2018/09/10/why-y.html


Details on Turing Machines at computerphile:
https://www.youtube.com/watch?v=dNRDvLACg5Q


My slightly improved version of Morphett's Turing Machine simulator.
https://lawlorcode.com/2024/turing_pp.html

A very pretty graphical Turing Machine emulator:
http://turingmachine.io/


A tiny JavaScript emulator for a Turing Machine:
https://gist.github.com/azproduction/1400509

7-second clip taken from Rammstein's "Du Hast", available on Spotify here:
https://open.spotify.com/album/2w6Vy8qZLU4niyQAHyu0Ag

Hat tip to Tom Scott for the title's phrase "algorithm for truth":
https://www.youtube.com/watch?v=leX541Dr2rU


It's still hazy, but I feel like there are huge opportunties to exploit the beyond-binary logic of self-referential programs. For example, a "self aware" program sounds like clickbait or philosophy. But the halting problem suggests a precise defintion of "self awareness": "able to recognize you own source code when passed as an argument".

This is incredibly hard! You can be translated into a huge number of different programming languages, virtual machines, or obfuscators.