Алгоритм – это заранее заданная последовательность четко определенных правил или команд для получения решения задачи за конечное число шагов. Эффективным называют алгоритм, допускающий эффективную вычислительную реализацию. Понятие эффективной вычислимости предложено Тьюрингом 1936 г. Функция эффективно вычислима, если существует алгоритм правильно ее вычисляющий и удовлетворяющий следующим требованиям:

1. он состоит из конечного множества простых команд, для которых однозначно определен порядок исполнения.

2. Вычисления должны закончиться и дать результат за конечное число шагов, если аргумент принадлежит области определения и не должен приводить ни к каким результатам, если аргумент не из области определения.

Тезис Тьюринга-Черча об эквивалентности различных определений вычислимости.

До Тьюринга для определения формального алгоритма использовалось определение Черча. Определение основано на общей рекурсивности Геделя. В 1936 г. Тьюринг и Черч выдвинули тезис о том, что определения вычислимости  могут быть сведены к определению Тьюринга. В частности любой алгоритм можно признать вычислимым, если он допускает реализацию на машине Тьюринга. Машина Тьюринга – гипотетическая. Для неё определены правила выполнения элементарных определённых операций.