Qu'est-ce que cela signifie pour une fonction d'être calculable ?
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.
Bien qu'officieusement une fonction soit calculable si ses valeurs peuvent être calculées, Alan Turing, Alonzo Church et Kurt Godel avaient chacun des définitions formelles de la calculabilité, à savoir les machines de Turing, le calcul lambda et les fonctions récursives générales.  Lorsqu'il a été démontré dans la thèse de Church-Turing que ces trois formulations sont équivalentes, il est devenu plus clair qu'elles pouvaient être utilisées comme définition formelle de la calculabilité.
general_qa
fr