MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Could you give some motivation for this? Why do you suspect it is not strongly normalizing? Also, why is this particular combinator interesting? – Noah Schweber May 7 '13 at 21:18
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. – Pierre Lescanne May 9 '13 at 6:09

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.