Теория вычислений

Теория вычислений (англ. theory of computation) — направление компьютерных наук, занимающееся вопросами возможности и осуществлнения решения задач с применением модели вычисления, использующей алгоритм. Это направление подразделяется на две основные ветви: теория вычислимости и сложность вычислений, однако обе они опираются на модели вычислений (англ. model of computation).

[править] Формальные определения вычисления

Кроме машины Тьюринга используются и другие (см.: Тезис Черча-Тьюринга) эквивалентные модели вычислений.

лямбда-исчисление

рассматривается пара — λ-выражение и его аргумент, — а вычислением считается применение, или апплицирование первого члена пары ко второму. Это позволяет отделить функцию и то, к чему она применяется. В более общем случае вычислением считаются цепочки, начинающиеся с исходного λ-выражения, за которым следут конечная последовательность λ-выражений, каждое из которых получается из предыдущего применением β-редукции, то есть правила подстановки.

комбинаторная логика

трактовка вычисления сходна с λ-исчислением, но имеются и важные отличия (например, комбинатор неподвижной точки Y имеет нормальную форму в комбинаторной логике, а в λ-исчислении — не имеет). Комбинаторная логика была первоначально разработана для изучения природы парадоксов и для построения концептуально ясных оснований математики, причем представление о переменной исключалось вовсе, что помогало прояснить роль и место переменных в математике.