By Sahand Saba / sahandsaba.com

Assume $\mathcal{L}$ is some (not necessarily finite, or even countable) set. We are interested in the following two problems:

- Deciding if a given $x$ is in $\mathcal{L}$
- Describing the elements in $\mathcal{L}$

To make this accurate we need to make precise two things:

- A mathematical model of computation
- An encoding for $x$ and $\mathcal{L}$

Let's look at the first item for a bit. We will skip the details of encoding for the most part.

- $\mathcal{L} = \{x : x \text{ is a binary string and } \mathtt{11} \text{ does not occur in } x\}$
- For example:
- $\mathtt{00101} \in \mathcal{L}$
- $\mathtt{011} \not\in \mathcal{L}$

A machine with a finite set of *states* and transition rules.

For $\mathcal{L}$ defined on the previous slide:

Challange: find the eigen-values of the adjacency matrix for this graph. Do they look familiar? Find how this graph and the associated language $\mathcal{L}$ is related to the Fibonacci numbers.

- Very limited.
- Example: $\mathcal{L}$ the set of binary strings with equal number of ones and zeros.
- Challenge: See if you can prove $\mathcal{L}$ given above can not be decided using an FSM.

In simple terms: an FSM that can also read and write to a tape.

- Input: Description of a Turing machine $T$ and an input $x$
- Output: What $T$ would output if given $x$
- In other words: a Turing machine that "emulates" any given Turing machine

- Turing machines turn out to be quite powerful.
- It seems that any meaningful algorithm can be turned into a Turing machine
- This led to the Church-Turing thesis:

Any effectively decidable set $\mathcal{L}$ can be decided using a Turing machine

- Informally: Turing machines are as good a computing model as we are going to get!

- Let $\mathcal{L}$ be the set of Turing machines that eventually halt.
- Is $\mathcal{L}$ decidable using a Turing machine?
- This is known as the
*Halting Problem* - Equivalent to the following programming assignment:

Write a Python program that reads the source code of another Python program and outputs "yes" if the read program will stop when run, and otherwise "no".

(If you ever teach a first-year programming course and feel devilish, try giving this as an actual assignment to students.)

For simplicity, let's go with the Python version.

- Assume such a Python program exists
- Let's say
`halts_eventually`

from module`magic`

- What's the output of the following program?

- Did that idea seem familiar?
- Liar's paradox
- Cantor's proof of $|A| < |2^A|$
- Gödel's incompleteness theorems
- Tarski's undefinability of truth
- Incomputability of the Kolmogorov complexity
- etc.

- Set of statements true in number theory (Gödel's incompleteness theorems)
- The group isomorphism problem
- Problems to do with finite simplicial complexes in topology
- Solving Diophantine equations
- Problem of computing the Kolmogorov complexity
- Problems to do with context-free grammars
- Etc...

Informally, if a system is capable of simulating any Turing machine then the system is said to be *Turing
complete*. Some examples:

- Turing machines (Challenge: might seem obvious, but why?)
- Lambda calculus
- Post tag machines
- Logical gates (AND, OR, NOT)
- Conway's game of life
- Even 1-dimensional cellular automata (rule 110)
- Idealized billiard balls

Simple 2-dimensional cullular automata.

Have a look at this demo.

Yes. You can simulate logical gates using them:

Taken from Fredkin and Toffoli's paper "Conservative logic" (link)

Many problems to do with Turing complete systems can be inherently so difficult so as to be impossible to solve.

In some sense, this is a "hard" limit on what we can hope to solve computationally.

Given a piece of information (say a string or image), what is the smallest Turing machine (one with the least number of states and transition rules) that can reproduce the information?

This number is defined as the
*Kolmogorov complexity* of the string.

We can replace Turing machine with any Turing complete system. For our examples, let's use Python.

What's the Kolmogorov complexity of this image?

What's the Kolmogorov complexity of this image?

What's the Kolmogorov complexity of this image?

What about this one?

What's the smallest number that can not be described using less than 100 English words?

This paradox is the basic idea behind the proof that Kolmogorov complexity is not computable.

Somewhat related to the "full-employment theorem"... look it up!

Some resources for further exploration

- Turing's "On computable numbers, with an application to the Entscheidungsproblem"
- Godel's "On Formally Undecidable Propositions in Principia Mathematica and Related Systems"
- Hofstadter's "Gödel, Escher, Bach"