Kurt Gödel: The True Inventor of Programming Languages and Data Structures

Douglas Hofstadter Cognitive Science, Indiana University, Bloomington
When Oct 23, 2015
from 03:30 PM to 04:30 PM
Where Duthie Center for Engineering, Room 117
Add event to calendarvCal
iCal

Abstract:

Kurt Gödel is celebrated for his classic 1931 paper in which he showed that any formal deductive system that includes the axioms of number theory is incomplete, meaning that no matter how the formal system is constructed, there will always be an infinite family of unpluggable “holes” in it — true statements about integers none of which it can demonstrate. He proved this mind-boggling result by inventing and beautifully exploiting a systematic mapping, today called “Gödel numbering”, of symbols, formulas, and sequences of formulas onto positive integers (mostly extremely large integers). It also mapped deductive relationships between formulas onto parallel relationships between very large integers.

It turns out that a major chunk of Gödel’s paper can be recast, from a modern perspective, as the crafting of a sophisticated high-level program in which recursive functions operating on lists (disguised as huge integers) call other recursive functions operating on lists, which call yet other functions, etc., many levels down — elaborate computational machinery with nary a machine in sight. In other words, Gödel’s paper was built around the world’s first computer program — indeed, a Lisp program in disguise — even though electronic digital computers had not yet been dreamt of when he wrote it, let alone data structures and high-level programming languages.

Standard versions of the history of computing state that list processing was invented in 1956, and that the Lisp programming language, with its characteristic recursive function definitions, was invented in 1958. However, these landmark developments in computer science were anticipated in remarkable detail by a young mathematical logician working alone in Vienna nearly three decades earlier. Perhaps the main reason that Gödel has never been given credit for this achievement is that he didn’t have the foresight to describe what he was doing using the terms “data structure” and “programming language”, so people never make the connection. He didn’t realize he was writing a computer program, and for many decades, computer scientists seem not to have noticed it either. It is the purpose of this talk to correct this historical oversight.

Biography:

Hofstadter is College of Arts and Sciences Distinguished Professor of Cognitive Science and Computer Science, and Director of the Center for Research on Concepts and Cognition, at Indiana University. Although he is the author of eight major books, Hofstadter is best known for his magisterial first work, Gödel, Escher, Bach: an Eternal Golden Braid (a.k.a. GEB:EGB [a.k.a. GEB]), published in 1979 and awarded the Pulitzer Prize in 1980.

Research Areas:

  • Computational models of human thought (especially analogy-making)
  • Creativity in art and music
  • Discovery in mathematics and physics
  • Literary translation
  • Philosophy of mind and of consciousness