Was bedeutet es, dass eine Funktion berechenbar ist?
What does it mean for a function to be computable?
Although informally a function is computable if its values can be calculated, Alan Turing, Alonzo Church, and Kurt Godel each had formal definitions of computablility, namely Turing Machines, Lambda Calculus, and general recursive functions.  When it was shown in the Church-Turing thesis that these three formulations are equivalent, it became more clear that they could be used as a formal definition of computability.
Obwohl eine Funktion informell berechenbar ist, wenn ihre Werte berechnet werden können, hatten Alan Turing, Alonzo Church und Kurt Godel jeweils eine formale Definition der Berechenbarkeit, nämlich Turing-Maschinen, Lambda-Kalkül und allgemeine rekursive Funktionen.  Als in der Church-Turing-These gezeigt wurde, dass diese drei Formulierungen gleichwertig sind, wurde klar, dass sie als formale Definition der Berechenbarkeit verwendet werden können.
general_qa
de