2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Аппликация лямбда-термов ассоциативна или нет?
Сообщение25.12.2016, 09:40 
Заслуженный участник


08/04/08
8484
Аппликация лямбда-термов ассоциативна или нет?
В Пирсе написано, что $a \ b \ c$ понимается левоассоциативно: $(a \ b) \ c$. И мне кажется, что у меня есть примеры лямбда-термов, которые неассоциативны. Просто если они неассоциативны, то какие это функции?
А если ассоциативны, то давайте я примеры приведу, а Вы у меня ошибки найдете.

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение25.12.2016, 15:40 
Заслуженный участник
Аватара пользователя


06/10/08
6211
Аппликация неассоциативна, разумеется. Например, $KKIxy = Kxy = x$, $K(KI)xy = KIy = I$.

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение25.12.2016, 18:21 
Заслуженный участник
Аватара пользователя


27/04/09
26224
(Собственно, ведь когда операция $*$ неассоциативна, и возникает нужда сказать, лево- или правоассоциативно стоит понимать записи $a_1*a_2*\ldots*a_n$, если они спасают от скобок. Правда, тут сразу контрпример: если рассказывать об ассоциативной операции языку программирования, придётся всё равно сказать, как её ассоциировать при разборе, если это не какой-то супер-язык, который решает, что есть смысл расставлять скобки в выражении с заведомо ему известно ассоциативной операцией по-разному в зависимости от чего-то.)

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение25.12.2016, 20:47 
Заслуженный участник


08/04/08
8484
О, у меня мозги заработали. Проверка:
$g(f(x)) = (g \circ f)(x) = g \ (f \ x)\Rightarrow$
$g \circ f = \lambda x (g \ (f \ x))$
$h \circ (g \circ f) = (h \circ g) \circ f \Leftrightarrow$
$h \circ (\lambda x (g \ (f \ x))) = (\lambda x (h \ (g \ x))) \circ f \Leftrightarrow$
$\lambda x (h \ ((\lambda x (g \ (f \ x))) \ x)) = \lambda x (\lambda x (h \ (g \ x)) (f \ x)) \Leftrightarrow$
делаем аппликацию внутри с обеих сторон:
$\lambda x (h \ (g \ (f \ x)))= \lambda x (h \ (g \ (f \ x)))  \Leftrightarrow$
получается просто тождество
(а я чего-то сначала подумал, что будет $(h \ (g \ f)) = ((h \ g) \ f)$. Значит композиция функций и аппликация - разные вещи)
Спасибо!

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение27.05.2018, 11:00 


20/10/17
95
Xaositect в сообщении #1179845 писал(а):
Аппликация неассоциативна, разумеется. Например, $KKIxy = Kxy = x$, $K(KI)xy = KIy = I$.

Здравствуйте, объясните пожалуйста подробнее данные равенства. Нашел, что $Ix = x,Kxy = x$, но не понимаю, как получается первая их часть, точнее $KKIxy = Kxy$ и $K(KI)xy = KIy$ - что к чему применяется и в какой последовательности. Я так понял, что первое равенство - это левоассоциативность, а второе - правоассоциативность. И не могли бы привести другие примеры, показывающие не ассоциативность?

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение27.05.2018, 16:15 
Заслуженный участник
Аватара пользователя


27/04/09
26224
$abcdef$ — это сокращение для $((((ab)c)d)e)f$. Соответственно, $KKIxy \equiv (KKI)xy = Kxy$, потому что $KKI = K$, и $K(KI)xy \equiv (K(KI)x)y = KIy$, потому что $K(KI)x = KI$.

artey в сообщении #1315247 писал(а):
И не могли бы привести другие примеры, показывающие не ассоциативность?
Практически любой взятый с потолка пример её покажет, попробуйте. И вообще она более-менее естественна из смысла аппликации.

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение27.05.2018, 18:00 


20/10/17
95
arseniiv в сообщении #1315324 писал(а):
Практически любой взятый с потолка пример её покажет, попробуйте. И вообще она более-менее естественна из смысла аппликации.

Спасибо за пояснение. Вот взял такой пример, проверьте пожалуйста на правильность: $W \equiv \lambda xy.xyy $ $WIWxy \equiv (WIW)xy = (IW)W)xy = (WWx)y = (Wxx)y = xxxy$ и $WI(Wx)y \equiv (W(IW)x)y = (I(Wx)x)y = (W(xx)y) = xxyy$

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение27.05.2018, 18:09 
Заслуженный участник
Аватара пользователя


27/04/09
26224
Во втором ошибка, $WI(Wx) \equiv (WI)(Wx)$ редуцируется в $I(Wx)(Wx)$ и под конец останавливается на $x(Wx)(Wx)$.

-- Вс май 27, 2018 20:10:38 --

Т. е. вы наверно сразу хотели написать $W(IW)xy$, но поставили скобки немного не там?

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение27.05.2018, 18:20 


20/10/17
95
Вот так $W(IW)xy \equiv (W(IW)x)y = (I(Wx)x)y = (W(xx)y) = xxyy$ ?

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение27.05.2018, 19:35 
Заслуженный участник
Аватара пользователя


27/04/09
26224
$(W(IW)x)y = (IW)xxy = Wxxy = xxxy.$

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение27.05.2018, 20:02 


20/10/17
95
arseniiv в сообщении #1315378 писал(а):
$(W(IW)x)y = (IW)xxy = Wxxy = xxxy.$

Тогда получается, что ассоциативны.

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение27.05.2018, 21:07 
Заслуженный участник
Аватара пользователя


27/04/09
26224
Ассоциативность операции $*$ — это когда для всех троек элементов выполняется $(a*b)*c = a*(b*c)$. Если хотя бы для одной не выполняется, а для остальных да, ассоциативности всё равно уже нет. Тем более что в данном случае бесконечно много троек термов $a,b,c$, для которых $(ab)c \ne a(bc)$ (и не только при $a = K$).

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение27.05.2018, 21:28 


20/10/17
95
arseniiv в сообщении #1315378 писал(а):
$(IW)xxy = Wxxy = xxxy.$

Почему вы так скобки расставили, а не так: $(I(Wx)x)y$ мы же смотрим правоассоциативность.

Почему ассоциативности не будет, если получается что
artey в сообщении #1315360 писал(а):
$WIWxy \equiv (WIW)xy = (IW)W)xy = (WWx)y = (Wxx)y = xxxy$
и
arseniiv в сообщении #1315378 писал(а):
$(W(IW)x)y = (IW)xxy = Wxxy = xxxy.$
.
Что то я совсем запутался. Можете пожалуйста вот для этого $WIWxy$ примера правильно расписать оба равенства.

 Профиль  
                  
 
 Re: Аппликация лямбда-термов ассоциативна или нет?
Сообщение29.05.2018, 18:36 
Заслуженный участник
Аватара пользователя


27/04/09
26224
Давайте с начала. Здесь рассматриваются три каких-то терма $a, b, c$ таких, чтобы, предположительно, $(ab)c \ne a(bc)$. Чтобы проще было убедиться в неравенстве, к рассматриваемым комбинаторам $(ab)c, a(bc)$ ещё применяется достаточное число переменных — $x, y$ в нашем случае. Скобки не нужно пытаться ставить каким-то особым образом в обход обычных правил больше нигде кроме этих уже готовых выражений (где они тоже поставлены вполне сознательно и не в обход правил вычисления). Ниже, так уж и быть, я укажу все скобки, не пользуясь соглашением об их левоассоциативной расстановке.

Итак, мы берём $(a, b, c) = (W, I, W)$ и получаем $$(((ab)c)x)y = (((WI)W)x)y = (((IW)W)x)y = ((WW)x)y = ((Wx)x)y = ((xx)x)y$$и $$((a(bc))x)y = ((W(IW))x)y = (((IW)x)x)y = ((Wx)x)y = ((xx)x)y.$$Недоразумение устранено? Если нет, опишите точнее, в чём оно состоит, а то непонятно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group