Тьюринг. Компьютерное исчисление

— Шаг 4. Подставить полученную величину в одно из двух уравнений, где выделена одна неизвестная.

— Шаг 5. Решить получившееся в предыдущем пункте уравнение.

— Шаг 6. Конец программы.

Эти заключения приводят нас к выводу о том, что компьютер представляет собой машину Тьюринга, работающую с алгоритмами. Когда решение задачи может быть выражено в виде алгоритма, считается, что задача разрешима. Швейцарский инженер Никлаус Вирт (р. 1934), автор языков программирования «Алгол», «Модула-2» и «Паскаль», участвовал в разработке определения программы в 1975 году. Согласно его определению, программа — соединение алгоритма с формой организации данных внутри программы; организация данных также получила название структура данных. Отсюда происходит знаменитое выражение Вирта: алгоритм + структура данных = программа.

АЛОНЗО ЧЁРЧ, ЛЯМБДА-ИСЧИСЛЕНИЕ И «ЛИСП»

Несмотря на то что с Тьюрингом всегда ассоциировалась машина, носящая его имя, после того как с трудами этого исследователя познакомился другой замечательный математик, Алонзо Чёрч (1903-1995), последний опубликовал работу, которая отнимала у машины Тьюринга часть оригинальности.

В 1930-е годы Чёрч вместе со Стивеном Клейни (1909-1994) ввели Х-исчисление — абстрактную математическую систему для формализации и анализа вычислимости функций.

Функция — математическое выражение у = f(x), отражающее связь между двумя переменными, например длиной х и весом у синих китов, в виде выражения у = 3,15х - 192. Это понятие, предложенное в XVII веке Декартом, Ньютоном и Лейбницем, в 1930-е годы было пересмотрено с целью разработки общей теории математических функций.

Новый синтаксис

Одной из заслуг Чёрча считается введение нового синтаксиса для представления данного класса математических выражений. Так, если, например, мы вычислим значение выражения (+(*23)(*56)), при этом звездочка — оператор умножения, то получим 36, поскольку (2 · 3) + (5 · 6) = 6 + + 30 = 36. Математическая функция должна быть абстрактной. Также для λ-исчисления используется более сложное выражение (λx. + x1), означающее: «Функция (представленная символом λ) от переменной (здесь х), которая имеет вид λ(x) (представлена здесь как.), добавляет (оператор +) величину переменной (то есть х) к 1». Мы можем несколько усложнить предыдущее выражение, записав ((λ х. + х1)3), результат которого равен 4, поскольку мы указали, что х = 3. Предсказуемо, что для преобразования всех элементов λ-исчисления мы можем усложнять операции. Другой заслугой такого типа исчисления стало его влияние на теорию, изучающую компьютерное программирование.

Проблема остановки