Основні поняття рекурсивних функцій
Заміна предикатів, запропонована Тюринг, на перший погляд виглядала відмінною від тієї, що запропонував його колега. Але в результаті вони виявилися еквівалентними, в тому сенсі, що кожен з них вибирає один і той же набір математичних функцій. Теза Черча-Тюрінга є твердженням, що це безліч містить кожну функцію, значення якої можуть бути отримані методом, що задовольняє умовам ефективності. Було ще одна відмінність цих двох відкриттів. Воно полягало в тому, що Черч розглядав тільки приклади додатних цілих чисел, тоді як Тьюринг описував свою роботу охоплює вычислимые функції з інтегральної або реальної змінної.
Загальні рекурсивні функції
У первісній формулюванні Черча говориться, що розрахунок може бути виконаний з використанням λ-числення. Це еквівалентно використанню загальних рекурсивних функцій. Теза Черча-Тюрінга охоплює більше видів обчислень, ніж ті, які спочатку передбачалися. Наприклад, пов’язані з клітинними автоматами, комбинаторами, реєстраційними машинами і системами заміщення. У 1933 році математики Курт Гедель і Жаком Хербранд створили формальне визначення класу, званого загальними рекурсивними функціями. Воно використовує функції, в яких можливий більш ніж один аргумент.
