Regular Languages and Model Theory 12: Gödel's Beta Function

In this video, I complete the proof of Gödel's First Incompleteness Theorem by showing how arbitrary tuples of natural numbers can be encoded in full arithmetic using Gödel's beta function and the Chinese Remainder Theorem.

Play around with Gödel's beta function encodings here: trkern.github.io/godelbetasolver

Matthew Cook Proved that a particular 1d cellular automaton where each cell has only 0 or 1 is Turing Complete: en.wikipedia.org/wiki/Rule_110 . This is very helpful for simplifying some Turing-completeness proofs.

Conway's Game of Life is also Turing Complete:
conwaylife.com/wiki/Universal_computer

The situation with Gödel's First Incompleteness Theorem is even worse than it first seems: a research problem you're working on might not just be unprovable and undisprovable, but you might not be able to prove this!
math.stackexchange.com/questions/932301/can-unprov…

Public Domain Conway's Game of Life Animation:
commons.wikimedia.org/wiki/File:Gosper_glider_gun_…

Public Domain 1d Cellular Automaton Image:
commons.wikimedia.org/wiki/File:Rule30-256-rows.pn…