Funktionale Programmierung ist in aller Munde und überall werden Konzepte aus der funktionalen Programmierung in imperative Sprachen übernommen. Auch ich bin momentan dabei, mir besagte Konzepte genauer anzusehen und möchte meine gewonnenen Erkenntnisse hier in Form einer Artikelserie veröffentlichen. Den Auftakt soll aber erst mal ein kleiner geschichtlicher Rückblick machen.

Ich muss zugeben, dass ich die Geschichte immer faszinierender finde, je mehr ich darüber recherchiert habe.

Es fing im Jahr 1936 an, als Alonzo Church im April mit seiner Veröffentlichung “An unsolvable Problem of Elementary Number Theory” nahelegte, dass das Entscheidungsproblem unlösbar sei.

…the Entscheidungsproblem is unsolvable in the case of any system of symbolic logic which is ω-consistent (ω-widerspruchsfrei) in the sense of Gödel (loc. cit., p. 187) and is strong enough to allow certain comparatively simple methods of definition and proof.

– Alonzo Church, An unsolvable Problem of Elementary Number Theory

Um zu diesem Schluss zu kommen, hat er das Lambda-Kalkül definiert, welches den Grundstein für die funktionale Programmierung legte.

Etwa zur gleichen Zeit hat sich Alan Turing ebenfalls mit dem Entscheidungsproblem befasst und veröffentlichte im August 1936 “On computable numbers, with an application to the Entscheidungsproblem”. Darin musste er auf Churchs Arbeit verweisen, was ihm wohl etwas missfiel (siehe Alan Turing — a short biography).

In a recent paper Alonzo Church has introduced an idea of “effective calculability”, which is equivalent to my “computability”, but is very differently defined. Church also reaches similar conclusions about the Entscheidungsproblem.

– Alan Turing, On computable numbers, with an application to the Entscheidungsproblem

Teil des Papers von Alan Turing war dabei die Definition der Automatic machines bzw. a-machines, welche heutzutage als Turingmaschinen besser bekannt sind und den Grundstein für die imperative Programmierung legten. Im Anhang besagten Papers legt Turing auch noch dar, dass die Klassen “effective calculability” (Lambda-Kalkül) und “computability” (Turingmaschine) gleich mächtig sind.

Turing kam im September 1936 an die Princeton Universität und begann unter Church seine Promotion. Bemerkenswert finde ich ebenfalls, dass noch andere, in der Informatik bekannte Persönlichkeiten unter Church promovierten wie beispielsweise Kleene, Scott, Kemeny

Wie man an diesen Auszügen aus der Geschichte sehen kann, entstanden die jeweiligen Grundkonzepte beider Programmierparadigmen (funktional und imperativ) interessanterweise im Jahr 1936, aber unabhängig voneinander als Beweis, dass das Entscheidungsproblem unlösbar ist.