Description number
id:
description-number-321-18057868
title:
Description number
text:
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, 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 machine
brand slug:
wiki
category slug:
encyclopedia
description:
Numbers that arise in the theory of Turing machines
original url:
https://en.wikipedia.org/wiki/Description_number
date created:
date modified:
2023-07-03T20:00:57Z
main entity:
{"identifier":"Q5263786","url":"https://www.wikidata.org/entity/Q5263786"}
image:
fields total:
13
integrity:
14