Bekenstein bound, showing the impossibility of infinite-tape Turing machines of finite size and bounded energy

Chaitin's constant or Omega (computer science) for information relating to the halting problem

Conway's Game of Life, a Turing-complete cellular automaton

Enumerator (in theoretical computer science)

Gödel, Escher, Bach: An Eternal Golden Braid, a famous book that discusses, among other topics, the Church–Turing thesis

Halting problem, for more references

Langton's ant and Turmites, simple two-dimensional analogues of the Turing machine

List of things named after Alan Turing

Claude Shannon, another leading thinker in information theory

Turing tarpit, any computing system or language that, despite being Turing complete, is generally considered useless for practical computing

Unorganised machine, for Turing's very early ideas on neural networks