Bagaimana bisa non-terminating

14

Saya telah memikirkan pertanyaan-pertanyaan ini:

Apakah ada kalkulus lambda yang diketik yang konsisten dan Turing lengkap?

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

dan sudah ada beberapa pertanyaan yang sulit dijawab terkait dalam pengaturan yang tidak diketik ! Lebih khusus lagi, saya ingin tahu apakah kami dapat memulihkan Turing-kelengkapan dari non-pemutusan dengan cara berikut:

Pertanyaan: Mengingat (murni) -istilah dengan tidak ada bentuk normal kepala lemah, tidak ada selalu ada sebuah fixed-point combinator sehingga Y_t \ (\ lambda xx) = tλtYt

Yt (λx.x)=t

Kesetaraan semua diambil modulo βη .

Saya benar-benar menduga versi pertanyaan ini salah , sehingga orang dapat melonggarkan pertanyaan ke kombinator pengulangan , di mana kombinator pengulangan Y didefinisikan sebagai istilah sedemikian rupa sehingga untuk setiap f

Y f=f (Y f)
di mana Y lagi diperlukan untuk menjadi kombinator perulangan. Ini cukup untuk mendefinisikan fungsi rekursif seperti biasa, tentu saja.

Lebih umum, saya tertarik dalam menemukan "alami" cara untuk pergi dari non-terminating t ke combinator perulangan, bahkan jika persamaan di atas tidak puas.

Saya juga tertarik pada versi yang lebih lemah dari pertanyaan di atas, misalnya dapat dianggap sebagai aplikasi dengan setiap dalam bentuk normal (meskipun saya tidak yakin itu benar-benar membantu).ttt1 t2tnti


Sejauh: pendekatan alami adalah untuk mengambil dan "lada" aplikasi dari seluruh, misalnyatf

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

menjadi biasa

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

Idenya adalah untuk mengurangi kepala ke aplikasi dan ganti dengan , tetapi langkah selanjutnya tidak jelas (dan saya skeptis bahwa ini dapat menyebabkan apa saja).λ x . t λ x . f t tλx.tλx.f t

Saya tidak yakin saya cukup mengerti tentang pohon Böhm untuk melihat apakah mereka memiliki sesuatu untuk dikatakan, tetapi saya sangat meragukannya, karena pohon Böhm hanyalah , yang tidak seperti pohon : sebuah pohon abstraksi tanpa batas.Y ΩΩYΩ


Sunting : Seorang teman saya mengatakan bahwa pendekatan naif ini tidak berfungsi dengan istilah: Pendekatan naif akan memberikan Tapi ini bukan kombinasi titik tetap! Ini dapat diperbaiki dengan mengganti aplikasi kedua dari oleh , tetapi kemudian tidak memberikan istilah aslinya. Tidak jelas apakah istilah ini merupakan contoh tandingan terhadap pertanyaan awal (dan tentu saja ini bukan contoh tandingan untuk pertanyaan yang lebih umum).( λ x . f ( x x x ) ) ( λ x . f ( x x x ) ) f λ y z . f y f I

(λx.x x x)(λx.x x x)
(λx.f (x x x))(λx.f (x x x))
fλyz.f yfsaya
cody
sumber
Saya percaya persyaratan bahwa t tidak memiliki bentuk normal kepala harus diperkuat untuk mengecualikan bentuk normal kepala lemah. Jika t mampu menghasilkan lambda, maka, karena di posisi kepala Anda selalu memiliki kombinator fixpoint (dimulai dengan f = id), lambda harus diproduksi oleh itu, itu tidak mungkin.
Andrea Asperti
@ AndreaAsperti Anda benar, tentu saja. Saya akan mengubah pertanyaan.
cody

Jawaban:

7

Ada beberapa aspek untuk pertanyaan yang sangat bagus ini, jadi saya akan menyusun jawaban ini sesuai dengan itu.

1. Jawaban untuk pertanyaan dalam kotak adalah tidak . Istilah disarankan oleh teman Anda memang merupakan contoh tandingan.Ω3=(λx.xxx)(λx.xxx)

Sebelumnya diperhatikan dalam komentar bahwa seseorang memiliki contoh tandingan seperti "raksasa" , sampai pertanyaan dibatasi untuk persyaratan tanpa bentuk normal lemah kepala. Istilah tersebut dikenal sebagaiistilah nol. Ini adalah istilah yang tidak pernah direduksi menjadi lambda, di bawah substitusi apa pun.K=YK

Untuk setiap combinator titik tetap (fpc) , Y I adalah istilah yang disebut bisu (AKA "root-active"): setiap reduksi mengurangi lebih jauh ke redex.YYI

tidak bisu; tidak ada yang Ω 3 - seperti manifes dengan memeriksa set reductnya, yaitu { Ω 3 ( λ x . x x x ) ( λ x . x x x ) kk N }KΩ3

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

Daripada memberikan argumen yang tepat mengapa bisu untuk semua fpcs Y (memang, untuk penggabung perulangan) - yang mungkin melelahkan namun mudah-mudahan cukup jelas - saya akan memperlakukan generalisasi yang jelas dari pertanyaan Anda, membatasi untuk menonaktifkan istilah juga.YIY

Istilah bisu adalah subkelas dari istilah nol yang merupakan subkelas dari istilah yang tidak dapat diselesaikan. Bersama-sama ini mungkin merupakan pilihan yang paling populer untuk konsep "tidak berarti" atau "tidak terdefinisi" dalam kalkulus lambda, yang sesuai dengan pohon Berarducci, Levy-Longo, dan B ohm yang sepele secara berurutan, masing-masing. telah dianalisis secara rinci oleh Paula Severi dan Fer-Jan de Vries. [1] Istilah bisu merupakan elemen dasar dalam kisi ini, yaitu gagasan paling ketat tentang "tidak terdefinisi".

2. Misalkan menjadi istilah bisu, dan Y menjadi combinator perulangan dengan properti yang Y saya = M .MYYI=M

Pertama kita berpendapat bahwa, untuk variabel segar , Y z benar-benar terlihat banyak seperti Y M Anda dijelaskan, diperoleh dengan "percikan z sekitar" beberapa mengecil dari M .zYzYMzM

Oleh Church-Rosser, dan M memiliki reduksi bersama, M . Ambil standar reduksi R : Y Saya s M ' . Setiap subterm M bersesuaian dengan subterm unik Y I Y z [ z : = I ] di bawah reduksi ini. Untuk setiap subterm C [ N ] = M , faktor R sebagai Y I C [YIMMR:YIsMMYIYz[z:=I]C[N]=MR , di mana kaki tengah merupakan reduksi kepala yang lemah (dan kaki terakhir adalah internal). N "dijaga" oleh z jika leg kedua ini mengontrak beberapa redex I P , dengan I turunan dari substitusi [ z : = I ] .YIC[N0]whC[N1]iC[N]NzIPI[z:=I]

Jelas, harus menjaga beberapa subterms M , karena jika tidak maka akan bisu juga. Di sisi lain, harus berhati-hati untuk tidak menjaga subterma yang diperlukan untuk non-terminasi, karena jika tidak, ia tidak dapat mengembangkan pohon B \ "ohm tak terbatas dari kombinator pengulangan.YM

Karena itu cukup untuk menemukan istilah bisu di mana setiap subterm, dari setiap reduksi, diperlukan untuk non-normalisasi, dalam arti bahwa menempatkan variabel di depan subterm itu menghasilkan istilah normalisasi.

Pertimbangkan , di mana W = λ w . w aku w w . Ini seperti Ω , tetapi pada setiap iterasi, kami memeriksa bahwa kemunculan W dalam posisi argumen tidak "diblokir" oleh variabel head, dengan memberinya identitas. Menempatkan z di depan subterm apa pun pada akhirnya akan menghasilkan bentuk normal z P 1P k , di mana masing-masing P i adalah I , W atau " z- sprinkling". Jadi ΨΨ=WWW=λw.wIwwΩWzzP1PkPisayaWzΨ adalah contoh tandingan terhadap pertanyaan umum.

DALIL. Tidak ada kombinator pengulangan sehingga Y I = Ψ .YYsaya=Ψ

BUKTI. Himpunan semua reducts dari adalah { W W , W I W W , saya saya saya saya W W , saya saya saya W W , saya saya W W , saya W W } . Agar dapat dikonversi dengan Ψ , Y saya harus mengurangi salah satunya. Argumennya identik dalam semua kasus; untuk konkrit, misalkan Y saya saya Saya W W .Ψ{WW,WsayaWW,sayasayasayasayaWW,sayasayasayaWW,sayasayaWW,sayaWW}ΨYsayaYsayasayasayaWW

Setiap penurunan standar dapat diperhitungkan sebagai Y saya w P N 4 , P w Q N 3 , Q w N 1 N 2 , sehingga  Y saya w N 1 N 2 N 3 N 4 N 1I , N 2I , N 3YsayassayasayaWW

YsayawPN4,PwQN3,QwN1N2,jadi YsayawN1N2N3N4N1saya,N2saya,N3W,N4W

Mari kita merujuk pada reduksi sebagai R 0 , dan reduksi dimulai dari N i sebagai R i .YsayawN1N2N3N4R0NsayaRsaya

Pengurangan ini dapat diangkat melalui substitusi untuk menghasilkan R z 0 : Y z z k ( M 1 M 2 M 3 M 4 ) N iM i [ z : = Saya ] sehingga R 0 adalah komposisi Y I R z 0 [ z : = I ] I[z: =saya]

R0z:Yzzk(M.1M.2M.3M.4)NsayaM.saya[z: =saya]
R0 .YsayaR0z[z: =saya]sayak(N1N4)wkN1N4

Demikian pula, kita dapat mengangkat setiap sebagai R z i : M iN z i R i : N i R z i [ z : = I ] N z i [ z : = I ] I NRsaya:NsayaN{saya,W}

Rsayaz:M.sayaNsayazRsaya:NsayaRsayaz[z: =saya]Nsayaz[z: =saya]sayaN

Bagian kedua dari faktorisasi ini tepatnya terdiri dari mengontrak I -redex yang dibuat oleh subtitusi N z i [ z : = I ] . (Khususnya, karena N adalah bentuk normal, begitu juga N z i .)RsayasayaNsayaz[z: =saya]NNsayaz

NsayazzNzNN{saya,W}Nsayaz

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

M.1M.2M.3M.4N1zN2zN3zN4zNsayazzsayasaya=1,2Wsaya=3,4

N1zN2zN3zN4zz(z(z()))zkjNsayaz

Nsayazsaya4kjj2+7saya-12

WsayasayaWWWz=λw.z(wsayaww)

sayasayaWWzsayaWWzWWzWzsayaWzWzz(sayasayasayasaya)WzWzzsayaWzWz

Ω

zM.N=λz.M.zNsaya=M.

Ysaya=M.YM.zM.YM.M.YM.M.

YM.z={z(YP[x: =Q]z)M.(λx.P)QYNzM. bukan redex dan M.whN

[1] Severi P., de Vries FJ. (2011) Menguraikan Kisi-Kisi Set Yang Tidak Berarti dalam Kalkulus Infinitary Lambda. Dalam: Beklemishev LD, de Queiroz R. (eds) Logika, Bahasa, Informasi dan Komputasi. WoLLIC 2011. Catatan Kuliah di Ilmu Komputer, vol 6642.

[2] Richard Statman. Tidak ada kombinator S, K yang berulang. Laporan Penelitian 91–133, Departemen Matematika, Universitas Carnegie Mellon, Pittsburgh, PA, 1991.

Andrew Polonsky
sumber
YY saya=Ω3
Poin yang bagus. Saya baru saja memperbarui jawabannya.
Andrew Polonsky