alogic

Лямбда-исчисление - это построение машин по переработке символьных последовательностей. Отсюда понятно, почему оно эквивалентно тому, что умеет делать машина Тьюринга. Возьмём, например, лямбда-функцию
λxyz.zzyxyx
Слева (от λ до точки) - что ожидается на входе, справа - что будет на выходе. Вместо одиночных букв на вход можно подавать последовательности, это называется β-редукцией. То есть, если функции λxyz.zzyxyx подать на вход (aa)(bb)(cc), то получим на выходе ccccbbaabbaa. Скобки нужны, чтобы отделять, что идёт вместо x, что вместо y, что вместо z. Поэтому λ-функции называются "комбинаторами" - они комбинируют из букв входа последовательность букв на выходе. Функции можно подать на вход её саму.