1
$\begingroup$

I highly speculate that combinator SSS(SS)SS is not strongly normalizing. What is the argument for the non strong normalization?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Could you give some motivation for this? Why do you suspect it is not strongly normalizing? Also, why is this particular combinator interesting? $\endgroup$
    – Noah Schweber
    Commented May 7, 2013 at 21:18
  • $\begingroup$ I suspect it is strongly normalizing because it reduces as follows (no room for that) This combinator is interesting because it is the smallest with is no SN. $\endgroup$
    – Pierre Lescanne
    Commented May 9, 2013 at 6:09

1 Answer 1

Reset to default
5
$\begingroup$

Did you have a look at the second part of Johannes Waldmann's thesis The Combinator S ?

He proves that the normalization of S-based combinators is decidable and provides a procedure. SSS(SS)SS does not normalize.

He also refers to Dobouè's combinator S(SS)SSSS which does not normalize.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ These are the same thing. $S(SS)SSSS \to SSS(SS)SS$ after its first S-combinator evaluation. $\endgroup$
    – Trev
    Commented Oct 13, 2021 at 19:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .