1.8. Вычислимость

В 1930-х годах, еще до того, как были изобретены компьютеры, логики иссле­довали абстрактные концепции вычисления. Алан Тьюринг и .Алонзо Черч независимо предложили чрезвычайно простые модели вычисления (назван­ные соответственно машинами Тьюринга и Лямбда-исчислением) и затем вы­двинули следующее утверждение (известное как Тезис Черча —Тьюринга):

Любое исполнимое вычисление может быть выполнено на любой из этих моделей.

Машины Тьюринга чрезвычайно просты; если воспользоваться синтак­сисом языка С, то объявления данных будут выглядеть так:

char tape[...];

int current = 0;

где лента (tape) предполагается бесконечной. Программа состоит из любого числа операторов вида:

L17: if (tape[currentj == 'g') {

tape[current++] = 'j'i

goto L43;

}

Оператор машины Тьюринга выполняется за четыре следующих шага.

• Считать и проверить символ в текущей ячейке ленты.

• Заменить символ на другой символ (необязательно).

• Увеличить или уменьшить указатель текущей ячейки.

• Перейти к другому оператору.

Согласно Тезису Черча — Тьюринга, любое вычисление, которое действи­тельно можно описать, может быть запрограммировано на этой примитивной машине. Интуитивная очевидность Тезиса опирается на два утверждения:

• Исследователи предложили множество моделей вычислений, и было до­казано, что все они эквивалентны машинам Тьюринга.

• Никому пока не удалось описать вычисление, которое не может быть ре­ализовано машиной Тьюринга.

Так как машину Тьюринга можно легко смоделировать на любом языке программирования, можно сказать, что все языки программирования «дела­ют» одно и то же, т. е. в некотором смысле эквивалентны.