[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #45

Originator: M. Venturini-Zilli
Date: December 1991

Summary: Which ordinals correspond to reduction graphs in the λ-calculus?

Some reduction graphs in λ-calculus [VZ84] are isomorphic to ordinals. For example, the reduction graph of (λ x.y)((λ z.zzz)(λ z.zzz)) is isomorphic to ω + 1. Which ordinals appear in this way as reduction graphs? It is known that all ordinals less than є₀ can be so represented.

References

[VZ84]

M. Venturini-Zilli. Reduction graphs in the Lambda Calculus. Theoretical Computer Science, 29:251–275, 1984.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]