х годах, еще до того,
1.8. Вычислимость
В 1930- х годах, еще до того, как были изобретены компьютеры, логики исследовали абстрактные концепции вычисления. Алан Тьюринг и .Алонзо Черч независимо предложили чрезвычайно простые модели вычисления (названные соответственно машинами Тьюринга и Лямбда-исчислением) и затем выдвинули следующее утверждение (известное как Тезис Черча —Тьюринга):
Любое исполнимое вычисление может быть выполнено на любой из этих моделей.
Машины Тьюринга чрезвычайно просты; если воспользоваться синтаксисом языка С, то объявления данных будут выглядеть так:
char tape[...];
int current = 0;
где лента (tape) предполагается бесконечной. Программа состоит из любого числа операторов вида:
L17: if (tape[currentj == 'g') {
tape[current++] = 'j'i
goto L43;
}
Оператор машины Тьюринга выполняется за четыре следующих шага.
• Считать и проверить символ в текущей ячейке ленты.
• Заменить символ на другой символ (необязательно).
• Увеличить или уменьшить указатель текущей ячейки.
• Перейти к другому оператору.
Согласно Тезису Черча — Тьюринга, любое вычисление, которое действительно можно описать, может быть запрограммировано на этой примитивной машине. Интуитивная очевидность Тезиса опирается на два утверждения:
• Исследователи предложили множество моделей вычислений, и было доказано, что все они эквивалентны машинам Тьюринга.
• Никому пока не удалось описать вычисление, которое не может быть реализовано машиной Тьюринга.
Так как машину Тьюринга можно легко смоделировать на любом языке программирования, можно сказать, что все языки программирования «делают» одно и то же, т. е. в некотором смысле эквивалентны.
1.9. Упражнения
1. Опишите, как реализовать компилятор для языка на том же самом языке («самораскрутка»).
