HN2new | past | comments | ask | show | jobs | submitlogin

A single point basis (like X = \z. z K S K for which X X = K K, X X X = K, and X (X X) = S) is not in itself a combinator.

A combinator is not just a closed lambda term; it must have all lambdas in leading position. Like S = \x \y \z. x z (y z)



Does this mean that the Y combinator, Y = λf.(λx.f (x x)) (λx.f (x x)), is not a combinator?


> A single point basis [...] is not in itself a combinator.

> A combinator [...] must have all lambdas in leading position.

What's your opinion on:

  ωabcd = bd(cd) if a has no normal form[0][1]
    or  = c      if b has no normal form
    or  = d      if c has no normal form
    or  = dd     otherwise
  where
  SII = ωωωω
  Ω = SII(SII) = ωωωω(ωωωω)
  S = ωΩ = ω(ωωωω(ωωωω))
  K = ωωΩ = ωω(ωωωω(ωωωω))
  I = ωωωΩ = ωωω(ωωωω(ωωωω))
as a single-'combinator' basis?

0: Aka, does not halt.

1: Evaluation diverges if a (or b or c, if queried) is somthing like:

  SII(C(C(B(ωωx(KI)K)(SII))Ω)I)
(from https://en.wikipedia.org/wiki/Combinatory_logic#Undecidabili...) that tries to diagonalize ω.


Such a combinator ω cannot exist.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: