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

Profile

alogic: (Default)
alogic

December 2016

S M T W T F S
    123
45678910
11121314151617
181920212223 24
25262728293031

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 24th, 2017 06:52 am
Powered by Dreamwidth Studios