โทโพโลยีเชิงคำนวณเป็นสาขาหนึ่งในคณิตศาสตร์ที่ศึกษาโครงสร้างทางโทโพโลยีและพีชคณิตของการคำนวณโทโพโลยีเชิงคำนวณไม่ควรสับสนกับโทโพโลยีเชิงอัลกอริทึมหรือโทโพโลยีเชิงคำนวณซึ่งศึกษาการประยุกต์ใช้การคำนวณกับโทโพโลยี

ดังที่Alan TuringและAlonzo Church ได้แสดงให้เห็น λ -calculusมีความแข็งแกร่งเพียงพอที่จะอธิบายฟังก์ชันที่คำนวณได้ทางกลไกทั้งหมด (ดูวิทยานิพนธ์ Church–Turing ) ^{[ 1 ] [ 2 ] [ 3 ]}ดังนั้น Lambda-calculus จึงเป็นภาษาโปรแกรมที่มีประสิทธิภาพ ซึ่งสามารถสร้างภาษาอื่นๆ ขึ้นได้ ด้วยเหตุนี้ เมื่อพิจารณาถึงโทโพโลยีของการคำนวณ จึงมักจะเน้นไปที่โทโพโลยีของ λ-calculus โปรดทราบว่านี่ไม่ใช่คำอธิบายที่สมบูรณ์ของโทโพโลยีของการคำนวณเสมอไป เนื่องจากฟังก์ชันที่เทียบเท่ากันในความหมายของ Church-Turing อาจยังมีโทโพโลยีที่แตกต่างกัน

โทโพโลยีของแลมบ์ดาแคลคูลัสคือโทโพโลยีของสก็อต ต์ และเมื่อจำกัดเฉพาะฟังก์ชันต่อเนื่อง แล มบ์ดาแคลคูลัสแบบไร้ชนิดจะมีค่าเท่ากับ ปริภูมิ โทโพโลยีที่อาศัยโทโพโลยีแบบต้นไม้ทั้งโทโพโลยีของสก็อตต์และต้นไม้แสดงความต่อเนื่องเมื่อเทียบกับตัวดำเนินการทวิภาคของการประยุกต์ใช้ (f ประยุกต์ใช้กับ a = fa) และการนามธรรม ((λx.t(x))a = t(a)) ด้วยความสัมพันธ์สมมูลแบบโมดูลาร์ที่อิงตามความสอดคล้อง แลมบ์ดาแอลเจบราที่อธิบายโครงสร้างพีชคณิตของแลมบ์ดาแคลคูลัสพบว่าเป็นส่วนขยายของพีชคณิตเชิงการจัดเรียง โดยมีการนำองค์ประกอบเข้ามาเพื่อรองรับการนามธรรม

แคลคูลัสแลมบ์ดาแบบไร้ประเภทถือว่าฟังก์ชันเป็นกฎและไม่แยกความแตกต่างระหว่างฟังก์ชันและวัตถุที่นำไปใช้ ซึ่งหมายความว่าแคลคูลัสแลมบ์ดาเป็นแบบ ไร้ ประเภทผลพลอยได้จากแคลคูลัสแลมบ์ดาแบบไร้ประเภทคือความสามารถในการคำนวณที่มีประสิทธิภาพเทียบเท่ากับการเรียกซ้ำทั่วไปและเครื่องจักรทัวริง [ ^{4 ] เซต}ของเทอมแลมบ์ดาสามารถพิจารณาได้ว่าเป็นโทโพโลยีเชิงฟังก์ชันซึ่งสามารถฝังปริภูมิฟังก์ชัน ได้ ซึ่งหมายความว่าการแมปแลมบ์ดาภายในปริภูมิ X เป็นเช่นนั้น λ:X → X ^{[ 4 ] [ 5 ]}แบบจำลองทฤษฎีเซตแบบไร้ประเภทของDana Scottซึ่งเปิดตัวในเดือนพฤศจิกายน พ.ศ. 2512 ได้สร้างโทโพโลยีที่เหมาะสมสำหรับแบบจำลองแคลคูลัสแลมบ์ดาใดๆ ที่มีปริภูมิฟังก์ชันจำกัดเฉพาะฟังก์ชันต่อเนื่อง ^{[ 4 ] [ 5 ]}ผลลัพธ์ของ โทโพโลยีแคลคูลัสแลมบ์ดา แบบต่อเนื่องของ Scottคือปริภูมิฟังก์ชันที่สร้างขึ้นบนความหมายเชิงการเขียนโปรแกรมที่อนุญาตให้มีการจัดเรียงจุดคงที่ เช่นตัวจัดเรียง Yและประเภทข้อมูล^{[ 6 ] [ 7 ]}ภายในปี 1971 แคลคูลัสแลมบ์ดาได้รับการออกแบบมาเพื่อกำหนดการคำนวณแบบลำดับใดๆ และสามารถปรับให้เข้ากับการคำนวณแบบขนานได้อย่างง่ายดาย^{[ 8 ]}ความสามารถในการลดทอนการคำนวณทั้งหมดให้เหลือเพียงแคลคูลัสแลมบ์ดาทำให้คุณสมบัติเชิงทอพอโลยีแลมบ์ดาเหล่านี้ได้รับการยอมรับจากภาษาโปรแกรมทั้งหมด^{[ 4 ]}

โดยอาศัยตัวดำเนินการภายในแคลคูลัสแลมบ์ดาได้แก่ การประยุกต์ใช้และการนามธรรม ทำให้สามารถพัฒนาพีชคณิตที่มีโครงสร้างกลุ่มซึ่งใช้การประยุกต์ใช้และการนามธรรมเป็นตัวดำเนินการทวิภาคได้ การประยุกต์ใช้ถูกนิยามว่าเป็นการดำเนินการระหว่างเทอมแลมบ์ดาที่สร้างเทอม λ เช่น การประยุกต์ใช้ λ กับเทอมแลมบ์ ดา aจะสร้างเทอม แลมบ์ดา λaการนามธรรมรวมตัวแปรที่ไม่นิยามไว้โดยการกำหนด λx.t(x) เป็นฟังก์ชันที่กำหนดค่าตัวแปรaให้กับเทอมแลมบ์ดาด้วยค่าt(a)ผ่านการดำเนินการ ((λ xt(x))a = t(a)) สุดท้ายความสัมพันธ์สมมูล จะเกิดขึ้นซึ่งระบุเทอม λ โมดูลเทอมที่แปลงได้ ตัวอย่างเช่นรูปแบบปกติของเบต้า

โทโพโลยีของสกอตต์มีความสำคัญอย่างยิ่งต่อการทำความเข้าใจโครงสร้างทางโทโพโลยีของการคำนวณที่แสดงออกผ่านแคลคูลัสแลมบ์ดา สกอตต์พบว่าหลังจากสร้างปริภูมิฟังก์ชันโดยใช้แคลคูลัสแลมบ์ดาแล้ว จะได้ปริภูมิโคลโมโกรอฟ${\displaystyle T_{o}}$พื้นที่โทโพโลยีซึ่งแสดงการบรรจบกันแบบจุดต่อจุดหรือเรียกสั้นๆ ว่า โท โพโลยีผลคูณ [ ^{9 ] ความ}สามารถในการโฮมีโอมอร์ฟิซึมในตัวเอง รวมถึงความสามารถในการฝังพื้นที่ทุกพื้นที่ลงในพื้นที่ดังกล่าว ซึ่งเรียกว่า Scott continuousดังที่ได้อธิบายไว้ก่อนหน้านี้ ทำให้โทโพโลยีของ Scott สามารถนำไปใช้กับตรรกศาสตร์และทฤษฎีฟังก์ชันแบบเรียกซ้ำได้ Scott เข้าถึงการพิสูจน์ของเขาโดย ใช้ แลตทิซที่สมบูรณ์ส่งผลให้โทโพโลยีขึ้นอยู่กับโครงสร้างของแลตทิซ เป็นไปได้ที่จะสรุปทฤษฎีของ Scott โดยใช้ลำดับบางส่วนที่สมบูรณ์ด้วยเหตุนี้ ความเข้าใจทั่วไปเกี่ยวกับโทโพโลยีการคำนวณจึงเกิดขึ้นผ่านลำดับบางส่วนที่สมบูรณ์ เราจะย้ำอีกครั้งเพื่อให้คุ้นเคยกับสัญลักษณ์ที่จะใช้ในระหว่างการอภิปรายเกี่ยวกับโทโพโลยีของ Scott

คำสั่งซื้อแบบบางส่วนที่สมบูรณ์จะถูกกำหนดไว้ดังนี้:

ประการแรก เมื่อกำหนดเซตที่มีลำดับบางส่วน D=(D,≤) แล้ว เซตย่อยที่ไม่ว่างX ⊆ Dจะเป็นเซตที่มีทิศทางถ้า ∀ x,y ∈ X ∃ z ∈ Xโดยที่x ≤ zและy ≤ z

Dเป็นลำดับบางส่วนที่สมบูรณ์ (cpo) ถ้า:

⋅เซต X ⊆D ที่มีทิศทางทุกเซตจะมีค่าสูงสุดและ:

∃ องค์ประกอบล่าง ⊥ ∈ Dที่ทำให้ ∀ x ∈ D ⊥ ≤ x

ขณะนี้เราสามารถกำหนดโทโพโลยี Scottบน cpo (D, ≤ ) ได้แล้ว

O ⊆ D เปิดอยู่ก็ต่อเมื่อ:

1. ถ้า x ∈ O และ x ≤ y แล้ว y ∈ O นั่นคือ O เป็นเซตบน
2. สำหรับเซตทิศทาง X ⊆ D และsupremum (X) ∈ O แล้ว X ∩ O ≠ ∅

เมื่อใช้คำจำกัดความเชิงทอพอโลยีของสก็อตต์เกี่ยวกับสิ่งเปิด จะเห็นได้ชัดว่าคุณสมบัติเชิงทอพอโลยีทั้งหมดเป็นไปตามข้อกำหนด

⋅ ∅ และ D ซึ่งก็คือเซตว่างและปริภูมิทั้งหมด เป็นเซตเปิด

⋅การรวมกันโดยพลการของเซตเปิดเป็นเซตเปิด:

พิสูจน์ : สมมติว่า${\displaystyle U_{i}}$เป็นเซตเปิดที่ i ∈ I โดยที่ I เป็นเซตดัชนี เรากำหนด U = ∪{${\displaystyle U_{i}}$ ; i ∈ I}. ให้bเป็นสมาชิกของเซตบนของ U ดังนั้น a ≤ b สำหรับบางa ∈ U จะต้องเป็นว่าa ∈${\displaystyle U_{i}}$สำหรับ i บางค่า ในทำนองเดียวกัน b ∈ upset(${\displaystyle U_{i}}$). ดังนั้น U ก็ต้องอยู่สูงกว่าด้วยเช่นกัน เนื่องจาก${\displaystyle U_{i}}$∈ U.

ในทำนองเดียวกัน ถ้า D เป็นเซตทิศทางที่มีค่าสูงสุดใน U แล้วตามสมมติฐาน sup(D) ∈${\displaystyle U_{i}}$ที่ไหน${\displaystyle U_{i}}$เป็นเซตเปิด ดังนั้นจึงมีb ∈ D โดยที่ b ∈${\displaystyle U_{i}\cap D\subseteq U\cap D}$การรวมกันของเซตเปิด${\displaystyle U_{i}}$ดังนั้นจึงเปิดกว้าง

⋅ชุดเปิดภายใต้จุดตัดคือชุดเปิด:

บทพิสูจน์ : กำหนดให้เซตเปิดสองเซตคือUและVเรากำหนดW = U ∩ Vถ้าW = ∅ แล้วW เป็นเซตเปิด ถ้า b ∈ upset(W) (เซตบนของ W) ไม่ว่างเปล่า แล้วสำหรับบาง a ∈ W จะ ได้ว่าa ≤ bเนื่องจากa ∈ U ∩ Vและbเป็นสมาชิกของเซตบนของทั้งUและVดังนั้นb ∈ W

สุดท้ายนี้ ถ้าDเป็นเซตทิศทางที่มีค่าสูงสุดในWแล้วตามสมมติฐาน sup( D ) ∈${\displaystyle U\cap V}$ดังนั้นจึงมี∈${\displaystyle U\cap D}$และb ∈${\displaystyle V\cap D}$เนื่องจากDเป็นเมทริกซ์ทิศทาง จึงมีc ∈ Dที่มี${\displaystyle a\leq c,b\leq c}$และเนื่องจากUและVเป็นเซตบน ดังนั้นc ∈${\displaystyle U\cap V}$เช่นกัน.

แม้จะไม่ได้แสดงไว้ในที่นี้ แต่ความจริงก็คือแผนที่นั้น${\displaystyle f:D\rightarrow D^{'}}$ต่อเนื่องก็ต่อเมื่อ f (sup( X )) = sup( f ( X )) สำหรับทุกX ⊆ D ที่มีทิศทาง โดยที่f ( X ) = { f ( x ) | x ∈ X } และ supremum อันดับสองใน${\displaystyle D^{'}}$[ ^{4 ]​}

ก่อนที่เราจะเริ่มอธิบายว่าการประยุกต์ใช้ที่พบได้ทั่วไปในแคลคูลัสแลมบ์ดามีความต่อเนื่องภายในโทโพโลยีของสก็อตต์ เราจำเป็นต้องมีความเข้าใจบางอย่างเกี่ยวกับพฤติกรรมของค่าสูงสุดเหนือฟังก์ชันต่อเนื่อง ตลอดจนเงื่อนไขที่จำเป็นสำหรับผลคูณของปริภูมิที่จะมีความต่อเนื่อง กล่าวคือ

1. กับ${\displaystyle {f_{i}}_{i}\subseteq [D\rightarrow D^{'}]}$ถ้าเป็นกลุ่มแผนที่ที่มีทิศทางแล้ว${\displaystyle f(x)=\cup _{i}f_{i}(x)}$ถ้าหากมีการกำหนดไว้อย่างชัดเจนและต่อเนื่อง
2. ถ้า F${\displaystyle \subseteq [D\rightarrow D^{'}]}$ได้รับการกำกับดูแลและซีพีโอและ${\displaystyle [D\rightarrow D^{'}]}$cpo ที่ sup({ f ( x ) | f ∈ F })

ต่อไปนี้เราจะแสดงให้เห็นถึงความต่อเนื่องของการประยุกต์ใช้โดยใช้คำจำกัดความของการประยุกต์ใช้ดังต่อไปนี้:

เอพี:${\displaystyle [D\rightarrow D^{'}]\times D\rightarrow D^{'}}$โดยที่Ap ( f , x ) = f ( x )

Ap มีความต่อเนื่องเมื่อเทียบกับโทโพโลยี Scott บนผลคูณ (${\displaystyle [D\rightarrow D^{'}]\times D\rightarrow D^{'}}$)  :

บทพิสูจน์ : λx.f(x) = f เป็นฟังก์ชันต่อเนื่อง ให้ h = λ ff(x) สำหรับฟังก์ชันทิศทาง F${\displaystyle \subseteq [D\rightarrow D^{'}]}$

h (sup( F )) = sup( F )( x )

= sup( { f ( x ) | f ∈ F } )

= sup( { h ( f ) | f ∈ F } )

= sup( h ( F ) )

ตามนิยามของความต่อเนื่องของ Scott นั้นhได้รับการพิสูจน์แล้วว่ามีความต่อเนื่อง สิ่งที่ต้องพิสูจน์ต่อไปคือการประยุกต์ใช้จะมีความต่อเนื่องเมื่อตัวแปรอิสระแต่ละตัวมีความต่อเนื่อง กล่าวคือ${\displaystyle [D\rightarrow D^{'}]}$และ${\displaystyle D\rightarrow D^{'}}$เป็นค่าต่อเนื่อง ในกรณีของเราคือfและh

ตอนนี้เราจะสรุปข้อโต้แย้งของเราเพื่อแสดงให้เห็นว่า${\displaystyle f:D\times D^{'}\rightarrow D^{''}}$กับ${\displaystyle g=\lambda xf(x,x_{0})}$และ${\displaystyle d=\lambda x^{'}.f(x_{0},x^{'})}$เนื่องจากข้อโต้แย้งสำหรับDและ${\displaystyle D^{'}}$ตามลำดับ จากนั้นสำหรับทิศทาง X ⊆ D

${\displaystyle g(\sup(X))=f(\sup(X),x_{0}^{'}))}$

= f( sup( (x,${\displaystyle x_{0}^{'}}$) | x ∈ X} ))

(เนื่องจากfเป็นฟังก์ชันต่อเนื่องและ {(x,${\displaystyle x_{0}^{'}}$) | x ∈ X}) เป็นทิศทาง):

= sup( {f(x,${\displaystyle x_{0}^{'}}$) | x ∈ X} )

= sup(g(X))

ดังนั้น g จึงเป็นฟังก์ชันต่อเนื่อง และสามารถใช้กระบวนการเดียวกันนี้เพื่อแสดงว่า d ก็เป็นฟังก์ชันต่อเนื่องเช่นกัน

ขณะนี้ได้มีการพิสูจน์แล้วว่าการประยุกต์ใช้งานเป็นไปอย่างต่อเนื่องภายใต้โทโพโลยีแบบสก็อตต์

เพื่อแสดงให้เห็นว่าโทโพโลยีของสก็อตต์เหมาะสมกับแคลคูลัสแลมบ์ดา จำเป็นต้องพิสูจน์ว่าการนามธรรมยังคงต่อเนื่องบนโทโพโลยีของสก็อตต์ เมื่อทำสำเร็จแล้ว จะแสดงให้เห็นว่ารากฐานทางคณิตศาสตร์ของแคลคูลัสแลมบ์ดาเป็นแบบแผนเชิงฟังก์ชันที่กำหนดไว้อย่างดีและเหมาะสมสำหรับโทโพโลยีของสก็อตต์

กับ${\displaystyle f\in [D\times D^{'}\rightarrow D^{''}]}$เรากำหนด${\displaystyle {\check {f}}}$(x) =λ y ∈${\displaystyle D^{'}}$เราจะแสดงให้เห็นว่า: f(x,y)

(ฉัน)${\displaystyle {\check {f}}}$มีความต่อเนื่อง หมายความว่า${\displaystyle {\check {f}}}$∈${\displaystyle [D\rightarrow [D^{'}\rightarrow D^{''}]}$

(ii) λ${\displaystyle f.{\check {f}}:[D\times D^{'}\rightarrow D^{''}]\rightarrow [D\rightarrow [D^{'}\rightarrow D^{''}]}$เป็นค่าต่อเนื่อง

บทพิสูจน์ (i): ให้ X ⊆ D เป็นเวกเตอร์ทิศทาง แล้ว

${\displaystyle {\check {f}}}$(sup(X)) = λ yf( sup(X),y )

= λ y.${\displaystyle \sup _{x\in X}}$( f(x,y) )

=${\displaystyle \sup _{x\in X}}$( λy.f(x,y) )

= sup(${\displaystyle {\check {f}}}$(X))

บทพิสูจน์ (ii): กำหนดให้ L = λ${\displaystyle f.{\check {f}}}$จากนั้นสำหรับ F${\displaystyle \subseteq [D\times D^{'}\rightarrow D^{''}]}$กำกับ

L(sup(F)) = แลมบ์ แลม แล (สนับสนุน(F))(x,y))

= λ x λ y.${\displaystyle \sup _{y\in F}}$ฟ(x,y)

=${\displaystyle \sup _{y\in F}}$λx λy.f(x,y)

= sup(L(F))

ยังไม่มีการพิสูจน์ว่าแคลคูลัสแลมบ์ดา (λ-calculus) กำหนดโทโพโลยีของสก็อตต์ (Scott topology) ได้อย่างไรและเพราะเหตุใด

ต้นไม้ Böhmซึ่งสามารถแสดงเป็นกราฟิกได้อย่างง่ายดาย แสดงถึงพฤติกรรมการคำนวณของเทอมแลมบ์ดาเป็นไปได้ที่จะคาดการณ์การทำงานของนิพจน์แลมบ์ดาที่กำหนดโดยอ้างอิงจากต้นไม้ Böhm ที่เกี่ยวข้อง^{[ 4 ]}ต้นไม้ Böhm สามารถมองได้ว่าคล้ายคลึงกับ${\displaystyle \mathbb {R} }$โดยที่ต้นไม้โบห์มของเซตที่กำหนดนั้นคล้ายกับเศษส่วนต่อเนื่องของจำนวนจริง และยิ่งไปกว่านั้น ต้นไม้โบห์มที่สอดคล้องกับลำดับในรูปแบบปกติจะมีจำนวนจำกัด คล้ายกับเซตย่อยตรรกยะของจำนวนจริง

ต้นไม้โบห์ม (Böhm tree) ถูกกำหนดโดยการแมปขององค์ประกอบภายในลำดับของตัวเลขที่มีลำดับ (≤, lh) และตัวดำเนินการไบนารี * ไปยังเซตของสัญลักษณ์ ต้นไม้โบห์มจึงเป็นความสัมพันธ์ระหว่างเซตของสัญลักษณ์ผ่านการแมปแบบบางส่วน ψ

โดยทั่วไปแล้ว อาจอธิบายแนวคิดของต้นไม้โบห์มได้ดังนี้:

กำหนดให้: Σ =${\displaystyle \perp \cup }${ λ x_{1}${\displaystyle \cdots }$x_{n} . y | n ∈${\displaystyle \mathbb {N} ,x_{1}...x_{n}}$โดยที่ y เป็นตัวแปร และเมื่อกำหนดให้ BT(M) เป็นต้นไม้ Böhm สำหรับเทอมแลมบ์ดา M เราจะได้ว่า:

BT(M) = ⊥ ถ้า M หาคำตอบไม่ได้ (ดังนั้นจึงมีโหนดเดียว)

กล่าวอย่างเป็นทางการมากขึ้น:

Σ ถูกกำหนดให้เป็นเซตของสัญลักษณ์ ต้นไม้โบห์มของเทอม λ M ซึ่งเขียนแทนด้วย BT(M) คือต้นไม้ที่มีป้ายกำกับ Σ ซึ่งกำหนดไว้ดังนี้:

ถ้าMไม่สามารถหาคำตอบได้:

${\displaystyle BT(M)(\langle \ \rangle )=\perp ,}$

บีที(เอ็ม)(${\displaystyle \langle k\rangle *\alpha }$) ไม่สามารถแก้ไขได้${\displaystyle \forall k,\alpha }$

ถ้า M สามารถหาคำตอบได้ โดยที่ M = λ x_{1}${\displaystyle \cdots x_{n}.yM_{0}\cdots M_{m-1}}$:

BT(M)(< >) = λ x_{1}${\displaystyle \cdots x_{n}.y}$

บีที(เอ็ม)(${\displaystyle \langle k\rangle *\alpha }$) = BT(M_k)(${\displaystyle \alpha }$)${\displaystyle \forall \alpha }$และ k < m

= ไม่ได้กำหนด ${\displaystyle \forall \alpha }$และ k ≥ m

ต่อไปนี้เราจะแสดงให้เห็นว่าต้นไม้ Böhm ทำหน้าที่เป็นแผนที่ที่เหมาะสมจากโทโพโลยีแบบต้นไม้ไปยังโทโพโลยีแบบ Scott ซึ่งทำให้เราสามารถมองเห็นโครงสร้างการคำนวณ ไม่ว่าจะเป็นภายในโทโพโลยีแบบ Scott หรือแบบต้นไม้ ในรูปแบบของต้นไม้ Böhm ได้

วิธีการตีความแคลคูลัส λ แบบใหม่นั้นไม่เพียงแต่น่าสนใจในตัวเองเท่านั้น แต่ยังเปิดโอกาสให้เกิดแนวคิดใหม่ๆ เกี่ยวกับพฤติกรรมของวิทยาศาสตร์คอมพิวเตอร์อีกด้วย ตัวดำเนินการไบนารีภายในพีชคณิต λ A คือ การประยุกต์ใช้ การประยุกต์ใช้จะถูกแทนด้วย⋅และกล่าวกันว่าให้โครงสร้าง${\displaystyle A=(X,\cdot )}$พีชคณิตเชิงการจัดเรียงช่วยให้สามารถใช้ตัวดำเนินการประยุกต์และทำหน้าที่เป็นจุดเริ่มต้นที่มีประโยชน์ แต่ยังคงไม่เพียงพอสำหรับแคลคูลัส λ เนื่องจากไม่สามารถแสดงนามธรรมได้ พีชคณิต λ กลายเป็นพีชคณิตเชิงการจัดเรียง M ที่รวมกับตัวดำเนินการทางไวยากรณ์ λ* ที่แปลงเทอมB(x,y)ที่มีค่าคงที่ในMไปเป็น C(${\displaystyle {\hat {y}}}$)≡ λ* xB(x,${\displaystyle {\hat {y}}}$นอกจากนี้ ยังสามารถกำหนด แบบจำลอง ส่วนขยายเพื่อหลีกเลี่ยงความจำเป็นของตัวดำเนินการ λ* โดยอนุญาตให้ ∀x (fx =gx) ⇒ f =g ได้อีกด้วย การสร้างพีชคณิต λ ผ่านการแนะนำตัวดำเนินการนามธรรมดำเนินไปดังนี้:

เราต้องสร้างพีชคณิตที่อนุญาตให้มีคำตอบสำหรับสมการเช่น axy = xyy โดยที่ a = λ xy.xyy ซึ่งจำเป็นต้องใช้พีชคณิตเชิงการจัดเรียง (combinatory algebra) คุณสมบัติที่เกี่ยวข้องของพีชคณิตเชิงการจัดเรียงมีดังนี้:

ในพีชคณิตเชิงการจัดเรียง มีโครงสร้างประยุกต์ อยู่ โครงสร้างประยุกต์ W คือพีชคณิตเชิงการจัดเรียงก็ต่อเมื่อ:

⋅ W ไม่ใช่เซตว่าง หมายความว่า W มีจำนวนสมาชิกมากกว่า 1

⋅ W แสดงให้เห็นถึงความสมบูรณ์แบบเชิงการจัดเรียง (ดูความสมบูรณ์แบบของฐาน SK ) โดยเฉพาะอย่างยิ่ง: สำหรับทุกพจน์ A ∈ เซตของพจน์ของ W และ${\displaystyle x_{1},...,x_{n}}$โดยมีตัวแปรอิสระของ A อยู่ภายใน${\displaystyle {x_{1},...,x_{n}}}$แล้ว:

${\displaystyle \exists f\forall x_{1}\cdot \cdot \cdot x_{n}}$ที่ไหน${\displaystyle fx_{1}\cdot \cdot \cdot x_{n}=A}$

พีชคณิตเชิงการจัดเรียงคือ:

• ไม่เคยสลับที่กัน
• ไม่มีความสัมพันธ์กัน
• ไม่มีวันสิ้นสุด
• ไม่มีการเรียกซ้ำ

พีชคณิตเชิงการจัดเรียงยังคงไม่สามารถทำหน้าที่เป็นโครงสร้างพีชคณิตสำหรับแคลคูลัส λ ได้ เนื่องจากขาดการเรียกซ้ำซึ่งเป็นข้อเสียเปรียบที่สำคัญ อย่างไรก็ตาม การมีอยู่ของเทอมประยุกต์นั้นเป็นข้อดี${\displaystyle A(x,{\vec {y}}}$) เป็นจุดเริ่มต้นที่ดีในการสร้างพีชคณิตแคลคูลัส λ สิ่งที่จำเป็นคือการแนะนำเทอมแลมบ์ดากล่าวคือรวม λx.A(x,${\displaystyle {\vec {y}}}$)

เราเริ่มต้นด้วยการใช้ประโยชน์จากข้อเท็จจริงที่ว่าภายในพีชคณิตเชิงการจัดเรียง M โดยมี A(x,${\displaystyle {\vec {y}}}$) ภายในชุดเงื่อนไขนั้นแล้ว:

${\displaystyle \forall {\vec {y}}}$${\displaystyle \exists b}$st bx = A(x,${\displaystyle {\vec {y}}}$)

จากนั้นเราต้องการให้ b มีความสัมพันธ์กับ${\displaystyle {\vec {y}}}$ส่งผลให้:

${\displaystyle \forall x}$บี(${\displaystyle {\vec {y}}}$)x = A(x,${\displaystyle {\vec {y}}}$)

บี(${\displaystyle {\vec {y}}}$) เทียบเท่ากับเทอม λ และจึงกำหนดได้อย่างเหมาะสมดังนี้: B(${\displaystyle {\vec {y}})\equiv }$λ*.

ขณะนี้สามารถกำหนดนิยามของพรี-λ-แอลจีบรา (pλA) ได้แล้ว

pλA คือโครงสร้างประยุกต์ W = (X, ⋅ ) โดยที่สำหรับแต่ละเทอม A ภายในเซตของเทอมภายใน W และสำหรับทุก x จะมีเทอม λ*xA ∈ T(W) (T(W) ≡ เทอมของ W) โดยที่ (เซตของตัวแปรอิสระของ λ*xA) = (เซตของตัวแปรอิสระของ A) - {x} W ต้องแสดงให้เห็นด้วยว่า:

${\displaystyle (\beta )}$(λ*xA)x = A

${\displaystyle \alpha _{1}}$λ*xA≡ λ*xA[x:=y] โดยที่ y ไม่ใช่ตัวแปรอิสระของ A

${\displaystyle \alpha _{2}}$(λ*xA)[y:=z]≡λ*xA[x:=y] โดยมีเงื่อนไขว่า y,z ≠ x และ z ไม่ใช่ตัวแปรอิสระของ A

ก่อนที่จะกำหนดนิยามของพีชคณิต λ อย่างสมบูรณ์ เราต้องแนะนำนิยามต่อไปนี้สำหรับเซตของเทอม λ ภายใน W ซึ่งแสดงด้วยสัญลักษณ์${\displaystyle \Gamma (W)}$โดยมีข้อกำหนดดังต่อไปนี้:

a ∈ W${\displaystyle \Rightarrow c_{a}\in \Gamma (W)}$

x ∈${\displaystyle \Gamma (W)}$สำหรับ x ∈ (${\displaystyle v_{0},v_{1},...}$)

M,N ∈${\displaystyle \Gamma (W)\Rightarrow }$(MN) ∈${\displaystyle \Gamma (W)}$

M ∈${\displaystyle \Gamma (W)\Rightarrow }$(λx.M) ∈${\displaystyle \Gamma (W)}$

การจับคู่จากเงื่อนไขภายใน${\displaystyle \Gamma (W)}$สำหรับเทอม λ ทั้งหมดภายใน W ซึ่งแสดงด้วยเครื่องหมาย*  :${\displaystyle \Gamma (W)\rightarrow \mathrm {T} (W)}$จากนั้นสามารถออกแบบได้ดังนี้:

${\displaystyle v_{i}^{*}=w_{i},c_{a}^{*}=c_{a}}$

(MN)* = M* N*

(λx.M)* = λ* x*.M*

ต่อไปนี้เราจะกำหนดλ (M) เพื่อแสดงถึงส่วนขยายหลังจากประเมินเงื่อนไขภายใน${\displaystyle \Gamma (W)}$.

λx.(λy.yx)${\displaystyle c_{a}}$= λx.${\displaystyle c_{a}}$x ในλ (W)

ในที่สุดเราก็จะได้พีชคณิต λ ที่สมบูรณ์ ผ่านนิยามต่อไปนี้:

(1) λ-algebra คือ pλA W โดยที่สำหรับ M,N ∈ Ɣ(W):

λ (W) ⊢ M = N ⇒ W ⊨ M = N.

แม้จะเป็นเรื่องยากลำบาก แต่รากฐานสำหรับกรอบพีชคณิตที่เหมาะสมซึ่งจะช่วยให้สามารถศึกษาแคลคูลัสแลมบ์ และการคำนวณ ในเชิงทฤษฎีกลุ่มได้ นั้นได้ถูกวางไว้แล้ว