Ассоциативность в лямбда-исчислении

StackOverflow https://stackoverflow.com/questions/3080775

  •  28-09-2019
  •  | 
  •  

Вопрос

Я работаю над вопросами упражнения книги Лямбда исчисления. Отказ Один из вопросов, которые я застрял, доказывает следующее: показать, что приложение не ассоциативно; На самом деле х (YZ) не равен (XY) Z

Вот что я работал до сих пор:

Let x = λa.λb. ab
Let y = λb.λc. bc
Let z = λa.λc. ac

(xy)z => ((λa.λb. ab) (λb.λc. bc)) (λa.λc. ac)    
=> (λb. (λb.λc. bc) b) (λa.λc. ac)    
=> (λb.λc. bc) (λa.λc. ac)    
=> (λc. (λa.λc. ac) c)

x(yz) => (λa.λb. ab) ((λb.λc. bc) (λa.λc. ac))    
=> (λb. ((λb.λc. bc) (λa.λc. ac)) b)    
=> (λb. (λc. (λa.λc. ac) c) b)

Это верно? Пожалуйста, помогите мне понять.

Это было полезно?

Решение

Производства кажутся в порядке, на первый взгляд.

Концептуально, просто подумайте, что X, Y и Z могут представлять любые вычислимые функции, а четко, некоторые из этих функций не являются ассоциативными. Скажем, x - «вычесть 2», Y - «разделить на 2», а Z - «двойной». Для этого примера x (yz) = 'citt 2' и (xy) z = 'substract 1'.

Другие советы

Я также думаю, что ваш контр-пример правильный.
Вы, вероятно, можете получить более простой контр-пример, как это:

позволять x = λa.n. и у, z. Переменные тогда:

(xy) z => ((λa.n) y) z => nz
x (yz) => (λa.n) (yz) => n

Кажется, в порядке, но для простоты, как насчет доказательства противоречия?

Предположить (xy) z = x (yz) и пусть

x = λa.λb. a     # x = const
y = λa. -a       # y = negate
z = 1            # z = 1

и показать, что ((xy) z) 0 ≠ (x (yz)) 0.

Книга, которую вы упомянуте Barendegt, чрезвычайно формально и точны (отличная книга), поэтому было бы неплохо иметь точное заявление о упражнении.

Я предполагаю, что фактическая цель состояла в том, чтобы найти мнение для x, y и z, такие что x (yz) сводится к логическому stare = xy.x, а (xy) z сводится к логическому Йолу = xy.y.

Затем вы можете взять, например, x = z.true и z = i = zz (y arbitrary).

Но как мы можем доказать, что True не конвертируется с false? У вас нет возможности доказать его внутри исчисления, поскольку у вас нет отрицания: вы можете только доказать равенства, а не неравенство. Тем не менее, давайте посмотрим, что если true = false, то все условия равны.

Действительно, для любого m и n, если true = false, то 

                         true M N = false M N

Но истинно Mn уменьшает м, а ложь Mn сводится к n, так

                              M = N

Следовательно, если true = false, все условия будут равны, а исчисление будет тривиальным. Поскольку мы можем найти не тривиальные модели лямбда-исчисления, такая модель не может приравнивать истинную и ложную (в целом может приравнивать термины с различными нормальными формами, что потребует от нас, чтобы поговорить о методике BOHM-OUT).

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top