Post by computer science

Gödel set the stage for the digital revolution, not only by redefining the powers of formal systems—and lining things up for their physical embodiment by Alan Turing—but by steering von Neumann’s interests from pure logic to applied. It was while attempting to extend Gödel’s results to a more general solution of Hilbert’s Entscheidungsproblem—the “decision problem” of whether provable statements can be distinguished from disprovable statements by strictly mechanical procedures in a finite amount of time—that Turing inven­ted his Universal Machine. All the powers—and limits to those powers—that Gödel’s theorems assigned to formal systems also applied to Turing’s Universal Machine, in­cluding the version that von Neumann, from his office directly below Gödel’s, was now attempting to build.

Gödel assigned all expressions within the language of the given formal system unique identity numbers—or numerical addresses—forcing them into correspondence with a numerical bureaucracy from which it was impossible to escape. The Gödel numbering is based on an alphabet of primes, with an explicit coding mechanism governing translation between compound expressions and their Gödel numbers—similar to, but without the ambiguity that characterizes the translations from nucleotides to amino acids upon which protein synthesis is based. This representation of all possible concepts by numerical codes seemed to be a purely theoretical construct in 1931.