科研之友
微信
新浪微博
Facebook
分享链接
摘要
A natural question in the lambda-calculus asks what is the possible number of fixed points of a combinator (closed term). A complete answer to this question is still missing (Problem 25 of TLCA Open Problems List) and we investigate the related question about the number of fixed points of a combinator in lambda-theories. We show the existence of a recursively enumerable lambda theory where the number is always one or infinite. We also show that there are lambda-theories such that some terms have only two fixed points. In a first example, this is obtained by means of a non-constructive (more precisely non-r. e.) lambda-theory where the range property is violated. A second, more complex example of a non-r. e. lambda-theory (with a higher unsolvability degree) shows that some terms can have only two fixed points while the range property holds for every term.
- 出版日期2017-3
