Отображение сетевого контента Отображение сетевого контента

Skip banner

Навигационная цепочка Навигационная цепочка

Навигация Навигация

Отображение сетевого контента Отображение сетевого контента

Podstawy Informatyki

Organizers: Marek Zaionc
Usual time and place: środa, 12:15-14:00, sala 0086
event-date: 27.10.2010
Speaker: Katarzyna Grygiel
Title of the talk: Asymptotically almost all lambda terms are strongly normalizing (1)
Abstract:

We present quantitative analysis of various (syntactic and behavioral) properties of random lambda terms. Our main results are that asymptotically all the terms are strongly normalizing and that any fixed closed term almost never appears in a random term. Surprisingly, in combinatory logic (the translation of the lambda calculus into combinators), the result is exactly opposite. We show that almost all terms are not strongly normalizing. This is due to the fact that any fixed combinator almost always appears in a random combinator.

Отображение сетевого контента Отображение сетевого контента