Как можно превратить бесконечные

14

Я думал об этих вопросах:

Существует ли типизированное лямбда-исчисление, которое является последовательным и полным по Тьюрингу?

/cs/65003/if-%CE%BB-xxx-has-a-type-then-is-the-type-system-inconsistent

и уже нет трудно ответить на связанные вопросы в нетипизированной обстановке! В частности, мне любопытно узнать, можем ли мы восстановить полноту по Тьюрингу из не прекращения следующим образом:

Вопрос: Учитывая (чистый) λ -term t с не слабой головной нормальной формой, не существует всегда существует фиксированная точка комбинатора Yt такие , что

Yt (λx.x)=t

Все равенства взяты по модулю βη .

Я на самом деле подозреваю, что эта версия вопроса неверна , поэтому можно смягчить вопрос для циклических комбинаторов , где циклический комбинатор Y определен так, что для каждого f

Y f=f (Y f)
где Y снова требуется быть циклическим комбинатором. Конечно, этого достаточно для определения рекурсивных функций как обычно.

В целом, я заинтересован в поиске «естественных» способов перехода от бесконечного t к циклическому комбинатору, даже если вышеприведенное уравнение не выполняется.

Я также заинтересован в более слабых версиях вышеупомянутого вопроса, например, t может рассматриваться как приложение tt1 t2tn с каждым ti в нормальной форме (хотя я не уверен, что это действительно помогает).


Пока что: естественный подход состоит в том, чтобы использовать t и «перец» приложения f повсюду, например,

Ω:=(λx.x x)(λx.x x)

становится обычным

YΩ:=λf.(λx.f (x x)) (λx.f (x x))

Идея состоит в том, чтобы свести голову t к лямбда-приложению λx.t и заменить его на λx.f t , но следующий шаг неясен (и я скептически отношусь к тому, что это может привести ко всему).

Я не уверен, что достаточно разбираюсь в деревьях Бёма, чтобы понять, есть ли у них что сказать, но я сильно сомневаюсь в этом, поскольку дерево Бёма просто , которое совсем не похоже на дерево Y Ω : бесконечное дерево абстракции.ΩYΩ


Редактировать : мой друг заметил, что этот наивный подход не работает с термином: Наивный подход даст ( λ x . F ( x x x ) ) ( λ x . f ( x x x ) ) Но это не комбинатор с фиксированной точкой! Это можно исправить, заменив второе приложение f на

(λx.x x x)(λx.x x x)
(λx.f (x x x))(λx.f (x x x))
f , но тогда f I не дает первоначального термина. Пока не ясно, является ли этот термин контрпримером к первоначальному вопросу (и, конечно, он не является контрпримером к более общему).λyz.f yfI
Коди
источник
Я считаю, что требование об отсутствии нормальной формы головы следует усилить, чтобы исключить также слабые нормальные формы головы. Если t может произвести лямбду, то, поскольку в положении головы у вас всегда есть комбинатор с фиксированной точкой (начиная с f = id), он должен производить лямбду, что невозможно.
Андреа Асперти
@AndreaAsperti вы правы, конечно. Я исправлю вопрос.
Коди

Ответы:

7

В этом очень хорошем вопросе есть несколько аспектов, поэтому я соответствующим образом структурирую этот ответ.

1. Ответ на поставленный вопрос - нет . Термин предложенный вашим другом, действительно является контрпримером.Ω3=(λx.xxx)(λx.xxx)

Ранее в комментариях было замечено, что имеются контрпримеры, подобные «огру» , пока вопрос не будет ограничен членами без нормальной нормальной формы слабой головы. Такие термины известны как нулевые термины . Это термины, которые никогда не сводятся к лямбде при любой замене.K=YK

Для любого комбинатора с фиксированной запятой (fpc) , Y I - это так называемый термин mute (AKA «root-active»): каждый его редукция сводится далее к редексу.YYI

не является немым; также не является Ω 3 - что проявляется в проверке его набора редукций, который равен { Ω 3 ( λ x . x x x ) ( λ x . x x x ) kk N }KΩ3

{Ω3(λx.xxx)(λx.xxx)kkN}

Вместо того, чтобы приводить точный аргумент, почему является немым для всех fpcs Y (действительно, для любого циклического комбинатора) - что может быть трудоемким, но, надеюсь, достаточно ясным - я рассмотрю очевидное обобщение вашего вопроса, ограничиваясь также терминами без звука.YIY

Безгласные термины являются подклассом нулевых терминов, которые являются подклассом неразрешимых терминов. Вместе они, пожалуй, являются наиболее популярным выбором для понятия «бессмысленный» или «неопределенный» в лямбда-исчислении, что соответствует тривиальным деревьям Берардуччи, Леви-Лонго и В »соответственно. Решетка понятий бессмысленных терминов был подробно проанализирован Паулой Севери и Фер-Яном де Фрисом. [1] Безгласные термины составляют нижний элемент в этой решетке, т. е. наиболее ограничительное понятие «неопределенный».

2. Пусть будет немым термин, и Y является зацикливание комбинатор со свойством , что Y I = M .MYYI=M

Во- первых мы утверждаем , что для нового переменного , Y г на самом деле выглядит очень похоже на Y M вы описали, полученный «дождевания г вокруг» некоторый редукта М .zYzYMzM

По Черч-Россеру, и M имеют общий редуктор, M . Возьмите стандартное сокращение R : Y I s M . Каждому подтерму в M соответствует единственный подтерм в Y I Y z [ z : = I ] при этой редукции. Для любого подтерм C [ N ] = M ' , R факторов , как Y I C [YIMMR:YIsMMYIYz[z:=I]C[N]=MR , где средняя нога представляет собой слабое уменьшение головы (а последняя нога является внутренней). N «охраняется» z, если этот второй этап заключает некоторый переопределение I P , а I - потомок замещения [ z : = I ] .YIC[N0]whC[N1]iC[N]NzIPI[z:=I]

Очевидно, что должен охранять некоторые подтермы M , поскольку в противном случае он также будет отключен. С другой стороны, он должен быть осторожен, чтобы не охранять те подтермы, которые необходимы для не-завершения, поскольку в противном случае он не мог бы развить бесконечное B-омное дерево циклического комбинатора.YM

Таким образом, достаточно найти немой термин, в котором каждый подтерм каждого редуктора необходим для ненормализации, в том смысле, что если поместить переменную перед этим подтермом, получится нормализующий термин.

Рассмотрим , где W = λ w . ж я ж ш . Это похоже на Ω , но на каждой итерации мы проверяем, что вхождение W в позиции аргумента не «блокируется» переменной head путем передачи ему идентификатора. Помещение z перед любым подтерием в конечном итоге приведет к нормальной форме z P 1P k , где каждый P i является либо I , W, либо их « z- окраской». Так ΨΨ=WWW=λw.wIwwΩWzzP1PkPiIWzΨ является контрпримером к обобщенному вопросу.

Теорема. Не существует циклического комбинатора такого, что Y I = Ψ .YYI=Ψ

Доказательство. Множество всех редуктов равно { WΨ . Чтобы быть конвертируемым с Ψ , Y я должен привести к одному из них. Аргумент идентичен во всех случаях; для определенности предположимчто Y I I I W W .{WW,WIWW,IIIIWW,IIIWW,IIWW,IWW}ΨYIYIIIWW

Любое стандартное сокращение может быть пропущено , как Y I ш P N 4 , Р YIsIIWW

YIwPN4,PwQN3,QwN1N2,thus YIwN1N2N3N4N1I,N2I,N3W,N4W

Обратимся к сокращению как R 0 , а сокращения, начиная с N i, как R i .YIwN1N2N3N4R0NiRi

Эти сокращения могут быть сняты за замену чтобы получить R z 0 : Y z z k ( М 1 М 2 М 3 М 4 ) N iM i [ z : = I ], так что R 0 является составом Y I R z 0 [ z : = I ] I[z:=I]

R0z:Yzzk(M1M2M3M4)NiMi[z:=I]
R0 .YIR0z[z:=I]Ik(N1N4)wkN1N4

Ri:NiN{I,W}

Riz:MiNizRi:NiRiz[z:=I]Niz[z:=I]IN

RiINiz[z:=I]NNiz

NizzNzNN{I,W}Niz

zk1(λx.zk2(x))zk1(λw.zk2(zk3(zk5(zk7(w)zk8(λx.zk9(x)))zk6(w))zk4(w)))

So M1M2M3M4N1zN2zN3zN4z, with Niz a z-sprinkling of I for i=1,2 and of W for i=3,4.

At the same time, the term N1zN2zN3zN4z should yet reduce to yield the infinite fpc Bohm tree z(z(z())). So there must exist a "sprinkle" zkj in one of the Niz which comes infinitely often to the head of the term, yet does not block further reductions of it.

And now we are done. By inspecting each Niz, for i4, and each possible value of kj, for j2+7i12, we find that no such sprinkling exists.

For example, if we modify the last W in IIWW as Wz=λw.z(wIww), then we get the normalizing reduction

IIWWzIWWzWWzWzIWzWzz(IIII)WzWzzIWzWz

(Notice that Ω admits such a sprinkling precisely because a certain subterm of it can be "guarded" without affecting non-normalization. The variable comes in head position, but enough redexes remain below.)

3. The "sprinkling transformation" has other uses. For example, by placing z in front of every redex in M, we obtain a term N=λz.Mz which is a normal form, yet satisfies the equation NI=M. This was used by Statman in [2], for example.

4. Alternatively, if you relax the requirement that YI=M, you can find various (weak) fpcs Y which simulate the reduction of M, while outputting a chain of zs along the way. I am not sure this would answer your general question, but there are certainly a number of (computable) transformations MYM which output looping combinators for every mute M, in such a way that the reduction graph of YM is structurally similar to that of M. For example, one can write

YMz={z(YP[x:=Q]z)M(λx.P)QYNzM is not a redex and MwhN

[1] Severi P., de Vries FJ. (2011) Decomposing the Lattice of Meaningless Sets in the Infinitary Lambda Calculus. In: Beklemishev L.D., de Queiroz R. (eds) Logic, Language, Information and Computation. WoLLIC 2011. Lecture Notes in Computer Science, vol 6642.

[2] Richard Statman. There is no hyperrecurrent S,K combinator. Research Report 91–133, Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA, 1991.

Andrew Polonsky
источник
This answer is great, and I will likely accept it. However, I'm not sure what the actual theorems you are describing, other than "there is no looping combinator Y such that Y I=Ω3". I think stating the theorems separately will make the arguments much easier to follow.
cody
Good point. I just updated the answer.
Andrew Polonsky