Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory internal-categories k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

nLab > Latest Changes: fixed-point combinator

Bottom of Page

1 to 25 of 25

  1.  
    • CommentRowNumber1.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 1st 2012

    After looking at Russell’s paradox, one thing led to another and I wound up writing fixed-point combinator.

    • CommentRowNumber2.
    • CommentAuthorMike Shulman
    • CommentTimeAug 6th 2012

    Lovely! I added some remarks on general recursion and typed λ\lambda-calculus.

    • CommentRowNumber3.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 6th 2012

    Very cool additions, Mike!

    • CommentRowNumber4.
    • CommentAuthorUrs
    • CommentTimeAug 12th 2012

    Some trivial edits, check if you like them:

    In the Idea-section after

    term YY

    I included

    term YY (of function type)

    to make clear what kind of term we are talking about (necessary, since the line above says we can do this generally in type theory).

    Then the word “applied” just a little bit further down I gave a hyperlink to evaluation map. Maybe there should be a more dedicated entry for this, but I think in any case “function application” is a technical term that should be hyperlinked to its explanation.

    I also made “recursive function” and “programming language” into hyperlinks, even though the entries do not exist yet.

    • CommentRowNumber5.
    • CommentAuthorUrs
    • CommentTimeAug 12th 2012
    • (edited Aug 12th 2012)

    You really mean to write “unityped λ\lambda-calculus” instead of “untyped λ\lambda-calculus”?

    In any case, I made that term, too, redirect to lambda-calculus.

    • CommentRowNumber6.
    • CommentAuthorTobyBartels
    • CommentTimeAug 12th 2012

    They really mean the same thing; an untyped whatever doesn’t really have zero types; it has one type, which you then don’t bother to mention.

    • CommentRowNumber7.
    • CommentAuthorUrs
    • CommentTimeAug 12th 2012
    • (edited Aug 12th 2012)

    I understand that non-typed means that there is precisely one type. But I am still wondering if the author of those lines did indeed mean to write and link to “unityped”.

    We did have a redirect for “untyped lambda-calculus”. Google knows no “unityped lambda-calculus”. My impression is that – whatever the logic of terminology might be – the conventional term is “untyped” and that it would be clearer to use that.

    But anyway, both terms now redirect to “lambda-calculus”. I suggest that whoever is fond of “unityped” should there add a corresponding comment.

    • CommentRowNumber8.
    • CommentAuthorMike Shulman
    • CommentTimeAug 12th 2012

    I did mean to write and link to “unityped”. Thanks for making the redirect; I added a comment to lambda calculus.

    On the other hand, I don’t really like the parenthetical “(of function type)” because of the unityped case (and also because it makes an already long and involved sentence more long and involved). Surely in a (multi)typed context, the fact that we are applying YY to something means automatically that it must be of function type?

    • CommentRowNumber9.
    • CommentAuthorUrs
    • CommentTimeAug 13th 2012

    Surely in a (multi)typed context, the fact that we are applying Y to something means automatically that it must be of function type?

    Let’s just add some link behind which the user can find an explanation of what it means to “apply a term to another term”.

    • CommentRowNumber10.
    • CommentAuthorMike Shulman
    • CommentTimeAug 13th 2012

    Okay, done!

    • CommentRowNumber11.
    • CommentAuthorUrs
    • CommentTimeAug 13th 2012
    • (edited Aug 13th 2012)

    Thanks!! (I already said this in another thread, but I should say it here :-)

    I have just added a few more links back and forth, here and there.

    • CommentRowNumber12.
    • CommentAuthorDaniilFrumin
    • CommentTimeNov 2nd 2014
    Hey, everyone. Long time lurker, first time editor. I've updated the page, mentioning a cool Klop's fixed-point combinator
    • CommentRowNumber13.
    • CommentAuthorMike Shulman
    • CommentTimeNov 3rd 2014

    Thanks! I haven’t looked at the paper, but the brief description you added to the entry looks a bit weird. Can you say anything about what the purpose of this example is? Is it that one can make lots of fixed-point combinators by adding lots of stuff that gets ignored?

    • CommentRowNumber14.
    • CommentAuthorDaniilFrumin
    • CommentTimeNov 3rd 2014
    The example is mostly just for fun, but the paper is about constructing new fixed point combinators from old ones. I don't know if "ignored" is the right word, but I guess in the paper Klop uses the phrase "dummy parameters"
    • CommentRowNumber15.
    • CommentAuthorMike Shulman
    • CommentTimeNov 3rd 2014

    What’s the value in constructing new fixed point combinators from old ones?

    • CommentRowNumber16.
    • CommentAuthorjoseville
    • CommentTimeDec 12th 2021
    • (edited Dec 12th 2021)

    In general, can Y KY_K be constructed to have any number of LLs (as long as we modify LL accordingly)? Is the YY-combinator a special case of Y KY_K with K=2K = 2? If so, let me know and I’ll elaborate on this in the Untyped λ\lambda-calculus section.

    • CommentRowNumber17.
    • CommentAuthorjoseville
    • CommentTimeDec 12th 2021
    • (edited Dec 12th 2021)

    The SKI fixed-point combinator mentioned in the Combinatory logic section:

    Y=S(K(SII))(S(S(KS)(S(KK)I)))(K(SII))Y = S(K (S I I))(S(S (K S)(S(K K)I)))(K (S I I))

    does not seem to actually be a fixed-point combinator upon closer inspection. Maybe a typo was made. See my math.se post. I’m waiting on confirmation either from math.se or from this forum before editing. Thanks.

    • CommentRowNumber18.
    • CommentAuthorUrs
    • CommentTimeDec 12th 2021

    Just to highlight that the expression in question in comment #17 (the one here) was added in rev 1, Aug 2012 by Todd Trimble (who may no longer be reading the forum here). Later in rev 6 Todd added what seems to be meant as a pointer to a proof.

    • CommentRowNumber19.
    • CommentAuthorGuest
    • CommentTimeDec 12th 2021

    Re: comment #18. I think there might be an error in:

    Y = λy.(sII)(s(ky)(sII)) = s(λy.sII)(λy.s(ky)(sII))\array{ Y &= & \lambda y. (s I I)(s(k y)(s I I)) \\ &= & s(\lambda y. s I I)(\lambda y. s(k y)(s I I)) }

    I think the second line, s(λy.sII)(λy.s(ky)(sII))s(\lambda y. s I I)(\lambda y. s(k y)(s I I)) is actually equal to λy.((sII)y)(s(ky)(sII))\lambda y. ((s I I)y)(s(k y)(s I I)) which is slightly different than the first line.

    • CommentRowNumber20.
    • CommentAuthorjoseville
    • CommentTimeDec 12th 2021
    • (edited Dec 12th 2021)

    Re: comment #18. I think there might be an error in:

    Y = λy.(sII)(s(ky)(sII)) = s(λy.sII)(λy.s(ky)(sII))\array{ Y &= & \lambda y. (s I I)(s(k y)(s I I)) \\ &= & s(\lambda y. s I I)(\lambda y. s(k y)(s I I)) }

    I think the second line, s(λy.sII)(λy.s(ky)(sII))s(\lambda y. s I I)(\lambda y. s(k y)(s I I)), is actually equal to λy.((sII)y)(s(ky)(sII))\lambda y. ((s I I)y)(s(k y)(s I I)) which is slightly different than the first line.

    • CommentRowNumber21.
    • CommentAuthorUrs
    • CommentTimeDec 12th 2021

    If you see a way to fix the entry (or entries), it would be much appreciated.

    • CommentRowNumber22.
    • CommentAuthorjoseville
    • CommentTimeDec 12th 2021

    Please disregard comments #19 and #20. I was mistaken - that is not the error in pointer to a proof. The step from the first line to the second line is correct. On the other hand there’s an error in the third step. If possible, delete those comments.

    On the other hand, I did find the error in pointer to a proof. The error is in the third line and I describe it in detail in this other math.se post. Please double check my work. Thanks.

    • CommentRowNumber23.
    • CommentAuthorMike Shulman
    • CommentTimeDec 13th 2021

    If Todd isn’t reading the forum right now, there may not be anyone here who can check your work. I probably could in principle, but my brain isn’t currently formatted for combinatory logic and I don’t have the time to reformat it for the foreseeable future. If you and the others at math.se are confident in your fixes, please go ahead and edit the pages. Thanks!

    • CommentRowNumber24.
    • CommentAuthorjoseville
    • CommentTimeDec 13th 2021

    The error and fix are discussed here: https://math.stackexchange.com/a/4331329/833760 Special thanks to Taroccoesbrocco.

    diff, v15, current

    • CommentRowNumber25.
    • CommentAuthorDavidRoberts
    • CommentTimeDec 13th 2021
    • (edited Dec 13th 2021)

    Thanks for chasing this down!

1 to 25 of 25

  1.