Week Fifteen Lecture Notes

More functions than formulas

Last lecture, we showed that

There are uncountably many functions from \(\mathbb{N}\) to {0,1}
There are only countably many finite-length strings of text.

Since computer programs and mathematical formulas are finite-length strings of text, there are only countably many of these. So there are more functions than there are formulas or computer programs. Therefore there are functions for which we can't write a formula or compute the function using a computer program.

The Halting Problem

Here is a specific example of a problem for which we cannot build a program:

The Halting Problem: Given the text for a program P, decide whether P eventually halts.

It's impossible to write an algorithm to solve this task. The proof is beyond the scope of this course. But it's done with a modification of the diagonalization idea that we used to prove that certain sets are uncountable.

Notice that we're talking about whether we can write a fully general algorithm that will work on any input program P, even nasty bits of spaghetti code. Obviously we can write an algorithm that will find the answer in many cases.

Three behaviors

Recall that decimal representations of real numbers come in three types

finite e.g. 3.225
repeating decimal e.g. \(7.5\overline{358}\)
continues off to infinity without repeating e.g. \(\pi\)

Similarly, a program can behave in three ways as it runs:

Halts.
Loops: repeats the same memory state
Continues forever without Looping: never halts and never repeats the same memory state

The Halting Problem cannot be solved because of the third possibility. If we only had to worry about the first two cases, our algorithm could simply watch the state of the program P. After some finite amount of time, P would have to halt or repeat a memory state.

If a program has a limit on how much memory it can use, it must eventually halt or loop. So, technically, a real-world program can't continue forever without looping. However, in practice, a typical computer has enough memory that a program can spend a vast amount of time running without repeating the same memory state.

We'll see two concrete (also pretty) examples of systems that can go on forever without repeating.

Conway's Game of Life
Aperiodic tilings

Both of these systems seem like toys but can simulate a Turing machine, i.e. a very simple stripped-down computer.

Conway's Game of Life

John Conway's "Game of Life" is a type of state machine from 1970 that was loosely motivated by the behavior of populations. Unlike the state machines we've seen earlier, its potential state space is infinite (like an idealized computer).

The playing space is an infinite checkerboard. You start by marking soem cells as "live". When moving from step to step, you consider the eight neighbors of each cell (i.e. diagonal neighbors count).

A cell with 0-1 live neighbors stays/becomes dead.
A cell with 2 live neighbors keeps its current status.
A cell with 3 live neighbors stays/becomes live.
A cell with 4-8 live neighbors stays/becomes dead.

Most of its properties were worked out on graph paper (!!) back in the day, but it's more fun to play with this simulator by Edwin Martin (edwin@bitstorm.org).

XXX X X	Dies completely
XX X X XX	Doesn't change
X XXX X	Oscillates (after a few moves)
X X XX X	Glider (moves across board)

See the Wikipedia page for more patterns.

Glider Gun

The "glider gun", created by Bill Gosper, generates an increasing sequence of gliders.

As it runs, the glider gun moves through an infinite sequence of states, never looping back to the same state.

Life pattern behaviors

So, depending on the input configuration, the Game of Life does one of three things:

"Halts": It stops changing after a while.
"Repeats": It gets into a repeating loop after a while.
"Aperiodic": The configuration keeps changing but it's not returning to the same configuration.

It is possible to simulate a simple computer using the Game of Life.

Periodic tilings

Consider covering the plane with a finite set of tiles. A "periodic tiling" covers the plane with a regular repeating pattern, using either a single shape or a finite set of shapes.

regular tiling 1 — Two periodic tilings (from Wikipedia).

regullar tiling 2 — Two periodic tilings (from Wikipedia).

floor tiling — A ceramic tile floor in Seville, Spain (from Wikipedia).

If you cut out a rectangle of appropriate size, you can make the whole pattern by making copies of whatever is on the rectangle. This is how modern builders often use cheap materials to simulate the look of fancy ceramic tiles.

rectangular unit — A painted unit simulating part of a tile pattern.

Patterns that stop

A regular pentagon can't tile the whole plane. If you try to do so, you get stuck with a gap that you can't fill.

pentagon won't tile — A regular pentagon can't tile the plane.

We've now seen two of our three program behaviors: repeating and self-stopping patterns. Are there tiling patterns that continue forever without repeating?

Aperiodic tilings

A set of tiles is called "aperiodic" if it can cover the whole plane but not in a regularly repeating way. The first such construction used "Wang tiles", i.e. square tiles with labels or colors on their edges. Wang tiles must be placed so that adjacent edges have the same label/color.

A legal placement of four Wang tiles. Adjacent edges match.

aperiodic set of Wang tiles — Aperiodic set of 11 Wang tiles (from Wikipedia).

Timeline for Wang tiles

1961: Hao Wang defines the problem.
1966: Robert Berger finds a set of 20,426 tiles that is aperiodic
2015: Emmanuel Jeandel and Michael Rao and a computer reduce this to 11 tiles.

In 1971 Raphael Robinson showed that it was possible to simulate a Turing Machine using Wang tiles.

Pretty aperiodic tilings

Around 1973-74, Roger Penrose figured out how to make pretty aperiodic tilings using small sets of geometric shapes.

At SIGGRAPH in 2003, a group of graphics researchers (Michael F. Cohen, Jonathan Shade, Stefan Hiller, Oliver Deussen) showed how to use Wang tiles to cheaply produce natural-looking textures using Wang tiles.

leaf texture — Texture of leaves simulated using Wang tiles.

In 2023, a team (David Smith, Joseph Myers, Craig Kaplan, and Chaim Goodman-Strauss) constructed a single tile (the "Spectre") that tiles the plane but only aperiodically.

spectre tiling — Spectre tiling from Simon Tatham

Quasicrystals

Penrose tilings can make patterns with many types of rotational symmetry.

Classical chemical crystal structures produce only four types of rotational symmetr: 2-fold, 3-fold, 4-fold, and 6-fold. In 1982, a chemist named Dan Shechtman observed a crystal structure with a 5-fold rotational symmetry, in an alloy of manganese and aluminum. These were eventually named "quasicrystals".

diffraction pattetn — Diffraction pattern of a quasicrystal with 10-fold symmetry (from Wikipedia).

At first, this discovery was not well received.

"Danny, you are a disgrace to my group. I cannot be with you in the same group."
Head of Shechtman's lab at NIST

"Danny Shechtman is talking nonsense, there are no quasi-crystals, just quasi-scientists."
Linus Pauling

Quotes from an interview with The Guardian newspaper.

However, other folks replicated his observations.

In 2008-2011 Luca Bindi and Paul Steinhardt tracked down natural examples of quasicrystals.
In 2011, Shechtman was given the Nobel prize in Chemistry.

More information on tilings

Some good Wikipedia articles:

From others: