Talk:The Church

I'm not sure if it's optimal (considering it contains the entire C combinator inside it), but *(+^)(**(*^)) is a decently short expression for S. –PkmnQ (talk) 11:19, 9 June 2026 (UTC)

Yup, it is. I still hope my bruteforcer would find something shorter. --Blashyrkh (talk) 11:43, 9 June 2026 (UTC)

Your solution is optimal. There's no size-6 solution for S. --Blashyrkh (talk) 10:48, 14 June 2026 (UTC)

isnt this syntactically invalid? ((+^) and (*^) have an even number of exprs) --MarkFan8901 (talk | contribs) 23:01, 15 October 2026 (UTC)

They used normal CC syntax, not The Church infix syntax to write that expression. --Blashyrkh (talk) 23:46, 15 October 2026 (UTC)

ah --MarkFan8901 (talk | contribs) 01:38, 16 October 2026 (UTC)

1

if this were right-associative then the EOF K 256 may be written (^**10)1414, but whatever... Cleverxia (talk) 12:16, 15 October 2026 (UTC)

Quine is almost ready, too late to change a thing. --Blashyrkh (talk) 12:46, 15 October 2026 (UTC)

syntax

the syntax section could probably be rewritten to be a few short sentences saying something like "Expressions are written in infix syntax. All operators are left-associative, and follow the precedence +*^0123456789. Brackets group expressions accordingly, and take precedence over all operators." --MarkFan8901 (talk | contribs) 23:06, 15 October 2026 (UTC)

You're welcome to improve the article! Since it's published at this wiki, anyone is free to edit it (as long as the information is factually correct and not off-topic). --Blashyrkh (talk) 23:51, 15 October 2026 (UTC)

oki, we were checking to make sure it was okay with you. probably should have said that upfront :P --MarkFan8901 (talk | contribs) 01:38, 16 October 2026 (UTC)

You've almost destroyed the original page. Not that it's something bad, it just means it wasn't good enough to be kept as is. I think I got your idea: do not describe things everyone knows; describe things nobody knows. Particularly, I'm going to add some clarifications on operators priority (because one corner case was covered just a little bit, and now it's not covered at all), and give a bracket abstraction algorithm for this weird basis. --Blashyrkh (talk) 13:05, 16 October 2026 (UTC)

Is that "Completeness of the basis" section correct?

The codeblock under the "Translation from SKI" subsection uses The Church's notation, while all the rest of the codeblocks use usual combinator notation. Though, I'm unsure which would be preferred here. (Mildly related, while the two expressions given for S are optimal in terms of combinator count, does that necessarily mean that the translation of them into The Church notation would be the shortest? I might try seeing if there's shorter.) –PkmnQ (talk) 13:52, 16 October 2026 (UTC)

I'll fix the page on weekend.

Regarding the lengths of expressions: when I said "shortest" I meant "shortest in terms of number of combinators", not "the shortest in The Church infix notation". The latter may be somewhat confusing: K combinator has length-5 The Church expression, but (Kx) would have length 6+len(x) because intermediate "1" appears. And vice versa - some (X) combinator's expression may have length 5 but this 5 includes intermediate "1", and Xx would be length 5 as well. --Blashyrkh (talk) 14:09, 16 October 2026 (UTC)

Since I'm going to write a description of my bracket abstraction algorithm (and it's better to do it in CC prefix syntax), I'm going to use both syntaxes on the page (no changes to the language specification, the page only). The Church syntax would use ()-parentheses, and CC syntax would use []-square brackets. At least, that's what I was doing when been writing the examples. --Blashyrkh (talk) 14:22, 16 October 2026 (UTC)

Hmm, now I'm wondering if including spaces for the CC syntax but excluding them for The Church syntax would work (i.e. * (+ ^) (* * (* ^)) and (+1^*(***1^)). Either way I think the bracket distinction would probably better, but it's an idea. –PkmnQ (talk) 15:06, 16 October 2026 (UTC)

In fact, I used both spaces and different style of brackets. ()-style with spaces is still valid The Church syntax, and I wanted to distinguish them more clearly. Presence of unhandled [] triggers interpreter's syntax error. --Blashyrkh (talk) 15:14, 16 October 2026 (UTC)

Alright, I've done enough checking for my standards to be confident enough that there's no shorter expression for S in The Church than what's already known. I mostly ignored digits greater than 2, though, so for all I know there might be some crazy expression that uses 9 or something (I think it's unlikely). –PkmnQ (talk) 15:33, 16 October 2026 (UTC)

For S I have only these:

• [+[*[+^]][^^]*]
• [++[+1**]^]
• [++[**[**]]^]
• [*[*[+^]*][*^]]
• [*[+^][**[*^]]]

But in general you'll be surprised:

• G: [+*[+1]*[*^]*]
• G: [+*[+3]*[*^]*]
• G: [+*[+5]*[*^]*]
• G: [+*[+7]*[*^]*]
• G: [+*[+9]*[*^]*]
• G: [+^+[**]^[*^]]
• B3: [+*[+3]^[**]]
• B3: [+2*[*^[**]]]
• B3: [+3^[*^[**]]]
• B3: [3[^[*^[**]]]2]
• B3: [4[^[*^[**]]]*]
• B3: [5[^[*^[**]]]^]
• B3: [5[^[*^[**]]]1]
• B3: [6[^[*^[**]]]0]
• R*: [4[^[**]]+[2^]]
• R*: [7[^[**]]3[2^]]

--Blashyrkh (talk) 15:50, 16 October 2026 (UTC)