go-v.orgcodex
Menu
Page tools

codex · Philosophy

Description number

Description numbers are numbers that arise in the theory of Turing machines. They are very similar to Gödel numbers, and are also occasionally called "Gödel numbers" in the literature. Given some universal Turing machine (UTM), every Turing machine can, given its encoding on that machine, be assigned a number. This is the machine's description number. These numbers play a key role in Alan Turing's proof of the undecidability of the halting problem, and are very useful in reasoning about Turing machines as well.

Wikipedia contributors, "Description number", Wikipedia, revision 1383156479, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex