Talk:Fixed-point combinator: Difference between revisions

Revision as of 04:28, 17 October 2023

Latest revision as of 20:05, 21 May 2025

(2 intermediate revisions by 2 users not shown)

Line 1:

{{summary in|Lambda calculus}}

{{WikiProject Computerbanner scienceshell|class=C|importance=Mid}}

{{WikiProject Computer science|importance=Mid}}

{{maths_rating|class=C|priority=low|field=foundations}}

{{WikiProject Mathematics|priority=low}}

}}

{{To do}}

Line 610 ⟶ 612:

This is mostly about the "values and domains" section, but there are also various other comments scattered throughout the article that I think need clearing up.

I'm not an expert, but it seems to me that there are at least two ways to think about the semantics of untyped lambda calculus. One is the "___domain" approach, explained (though not very clearly) in the linked [[Deductive lambda calculus]] article. In this interpretation every lambda expression has a value, even the non-halting ones. But there is also the more obvious semantics where each lambda expression is a partial function. It has a value if it haltsbeta reduces to a normal form, but otherwise it doesn't have a value. I believe that both of these are consistent and it's really a matter of choice which one to use.

The issue is that the article sometimes talks in terms of one and sometimes in terms of the other. For example, in the lede it states

Line 618 ⟶ 620:

This sounds like it's taking the partial function view: the argument function might not have a fixed point, and in that case the fixed-point combinator doesn't return a value.

(Though now I come to think of it, this statement is not actually correct. Consider the Y combinator applied to the identity function. It's easy to see that no value is returned in this case, even though any lambda term at all is a fixed point of the identity function. I guess the correct statement would be that it returns some fixed point of its argument function if it halts.)

On the other hand the article also makes statements like

Line 633 ⟶ 635:

[[User:Nathanielvirgo|Nathaniel Virgo]] ([[User talk:Nathanielvirgo|talk]]) 04:28, 17 October 2023 (UTC)

== Article is unintelligible ==

The article, as currently written, is unintelligible to anybody who isn't already an expert in the field.

The article needs to be rewritten from the beginning, in such a way as to answer the question "What is a fixed-point combinator?" '''in terms that can be understood by somebody who does not already know the answer.'''

[[User:Geoffrey.landis|Geoffrey.landis]] ([[User talk:Geoffrey.landis|talk]]) 20:05, 21 May 2025 (UTC)