(no subject)
Feb. 12th, 2009 07:38 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
alogicЛямбда-исчисление - это построение машин по переработке символьных последовательностей. Отсюда понятно, почему оно эквивалентно тому, что умеет делать машина Тьюринга. Возьмём, например, лямбда-функцию
λxyz.zzyxyx
Слева (от λ до точки) - что ожидается на входе, справа - что будет на выходе. Вместо одиночных букв на вход можно подавать последовательности, это называется β-редукцией. То есть, если функции λxyz.zzyxyx подать на вход (aa)(bb)(cc), то получим на выходе ccccbbaabbaa. Скобки нужны, чтобы отделять, что идёт вместо x, что вместо y, что вместо z. Поэтому λ-функции называются "комбинаторами" - они комбинируют из букв входа последовательность букв на выходе. Функции можно подать на вход её саму.
λxyz.zzyxyx
Слева (от λ до точки) - что ожидается на входе, справа - что будет на выходе. Вместо одиночных букв на вход можно подавать последовательности, это называется β-редукцией. То есть, если функции λxyz.zzyxyx подать на вход (aa)(bb)(cc), то получим на выходе ccccbbaabbaa. Скобки нужны, чтобы отделять, что идёт вместо x, что вместо y, что вместо z. Поэтому λ-функции называются "комбинаторами" - они комбинируют из букв входа последовательность букв на выходе. Функции можно подать на вход её саму.