Pourquoi les propriétés décidables de termes, comme la détermination de la première lettre de fonction primitive, ne peuvent-elles pas être définies par des prédicats complets dans le calcul combinatoire ?
Undefinability by predicates

The undecidable problems above (equivalence, existence of normal form, etc.) take as input syntactic representations of terms under a suitable encoding (e.g., Church encoding). One may also consider a toy trivial computation model where we "compute" properties of terms by means of combinators applied directly to the terms themselves as arguments, rather than to their syntactic representations. More precisely, let a predicate be a combinator that, when applied, returns either T or F (where T and F represent the conventional Church encodings of true and false, λx. λy. x and λx. λy. y, transformed into combinatory logic; the combinatory versions have T = K and F = (K I)). A predicate N is nontrivial if there are two arguments A and B such that N A = T and N B = F. A combinator N is complete if N M has a normal form for every argument M. An analogue of Rice's theorem for this toy model then says that every complete predicate is trivial. The proof of this theorem is rather simple.

By reductio ad absurdum. Suppose there is a complete non trivial predicate, say N. Because N is supposed to be non trivial there are combinators A and B such that

Fixed point theorem gives: ABSURDUM = (NEGATION ABSURDUM), for

Because N is supposed to be complete either:

Hence (N ABSURDUM) is neither T nor F, which contradicts the presupposition that N would be a complete non trivial predicate. Q.E.D.

From this undefinability theorem it immediately follows that there is no complete predicate that can discriminate between terms that have a normal form and terms that do not have a normal form. It also follows that there is no complete predicate, say EQUAL, such that:

If EQUAL would exist, then for all A, λx. (EQUAL x A) would have to be a complete non trivial predicate.

However, note that it also immediately follows from this undefinability theorem that many properties of terms that are obviously decidable are not definable by complete predicates either: e.g., there is no predicate that could tell whether the first primitive function letter occurring in a term is a K. This shows that definability by predicates is a not a reasonable model of decidability.
L'indéfinissabilité par prédicats

Les problèmes indécidables mentionnés ci-dessus (équivalence, existence d'une forme normale, etc.) prennent en entrée des représentations syntaxiques de termes selon un encodage approprié (par exemple, l'encodage de Church). On peut également considérer un modèle de calcul trivial où nous "calculons" les propriétés des termes au moyen de combinateurs appliqués directement aux termes eux-mêmes comme arguments, plutôt qu'à leurs représentations syntaxiques. Plus précisément, soit un prédicat un combinateur qui, lorsqu'il est appliqué, renvoie soit T soit F (où T et F représentent les encodages de Church conventionnels de vrai et faux, λx. λy. x et λx. λy. y, transformés en logique combinatoire ; les versions combinatoires ont T = K et F = (K I)). Un prédicat N est non trivial s'il existe deux arguments A et B tels que N A = T et N B = F. Un combinateur N est complet si N M a une forme normale pour tout argument M. Un analogue du théorème de Rice pour ce modèle trivial stipule que tout prédicat complet est trivial. La preuve de ce théorème est assez simple.

Par réduction à l'absurde. Supposons qu'il existe un prédicat complet et non trivial, disons N. Puisque N est supposé être non trivial, il existe des combinateurs A et B tels que :

Le théorème du point fixe donne : ABSURDUM = (NEGATION ABSURDUM), pour

Puisque N est supposé être complet, soit :

Par conséquent, (N ABSURDUM) n'est ni T ni F, ce qui contredit la présupposition selon laquelle N serait un prédicat complet et non trivial. C.Q.F.D.

De ce théorème d'indéfinissabilité, il découle immédiatement qu'il n'existe aucun prédicat complet capable de distinguer les termes qui ont une forme normale de ceux qui n'en ont pas. Il découle également qu'il n'existe aucun prédicat complet, disons ÉGAL, tel que :

Si ÉGAL existait, alors pour tout A, λx. (ÉGAL x A) devrait être un prédicat complet et non trivial.

Cependant, il découle également immédiatement de ce théorème d'indéfinissabilité que de nombreuses propriétés de termes qui sont évidemment décidables ne sont pas définissables par des prédicats complets non plus : par exemple, il n'existe aucun prédicat capable de déterminer si la première lettre de fonction primitive apparaissant dans un terme est un K. Cela montre que la définissabilité par prédicats n'est pas un modèle raisonnable de décidabilité.
### Query ###
Pourquoi les propriétés décidables de termes, comme la détermination de la première lettre de fonction primitive, ne peuvent-elles pas être définies par des prédicats complets dans le calcul combinatoire ?

### Main Text ###
Undefinability by predicates

The undecidable problems above (equivalence, existence of normal form, etc.) take as input syntactic representations of terms under a suitable encoding (e.g., Church encoding). One may also consider a toy trivial computation model where we "compute" properties of terms by means of combinators applied directly to the terms themselves as arguments, rather than to their syntactic representations. More precisely, let a predicate be a combinator that, when applied, returns either T or F (where T and F represent the conventional Church encodings of true and false, λx. λy. x and λx. λy. y, transformed into combinatory logic; the combinatory versions have T = K and F = (K I)). A predicate N is nontrivial if there are two arguments A and B such that N A = T and N B = F. A combinator N is complete if N M has a normal form for every argument M. An analogue of Rice's theorem for this toy model then says that every complete predicate is trivial. The proof of this theorem is rather simple.

By reductio ad absurdum. Suppose there is a complete non trivial predicate, say N. Because N is supposed to be non trivial there are combinators A and B such that

Fixed point theorem gives: ABSURDUM = (NEGATION ABSURDUM), for

Because N is supposed to be complete either:

Hence (N ABSURDUM) is neither T nor F, which contradicts the presupposition that N would be a complete non trivial predicate. Q.E.D.

From this undefinability theorem it immediately follows that there is no complete predicate that can discriminate between terms that have a normal form and terms that do not have a normal form. It also follows that there is no complete predicate, say EQUAL, such that:

If EQUAL would exist, then for all A, λx. (EQUAL x A) would have to be a complete non trivial predicate.

However, note that it also immediately follows from this undefinability theorem that many properties of terms that are obviously decidable are not definable by complete predicates either: e.g., there is no predicate that could tell whether the first primitive function letter occurring in a term is a K. This shows that definability by predicates is a not a reasonable model of decidability.

### Supplementary Text ###
L'indéfinissabilité par prédicats

Les problèmes indécidables mentionnés ci-dessus (équivalence, existence d'une forme normale, etc.) prennent en entrée des représentations syntaxiques de termes selon un encodage approprié (par exemple, l'encodage de Church). On peut également considérer un modèle de calcul trivial où nous "calculons" les propriétés des termes au moyen de combinateurs appliqués directement aux termes eux-mêmes comme arguments, plutôt qu'à leurs représentations syntaxiques. Plus précisément, soit un prédicat un combinateur qui, lorsqu'il est appliqué, renvoie soit T soit F (où T et F représentent les encodages de Church conventionnels de vrai et faux, λx. λy. x et λx. λy. y, transformés en logique combinatoire ; les versions combinatoires ont T = K et F = (K I)). Un prédicat N est non trivial s'il existe deux arguments A et B tels que N A = T et N B = F. Un combinateur N est complet si N M a une forme normale pour tout argument M. Un analogue du théorème de Rice pour ce modèle trivial stipule que tout prédicat complet est trivial. La preuve de ce théorème est assez simple.

Par réduction à l'absurde. Supposons qu'il existe un prédicat complet et non trivial, disons N. Puisque N est supposé être non trivial, il existe des combinateurs A et B tels que :

Le théorème du point fixe donne : ABSURDUM = (NEGATION ABSURDUM), pour

Puisque N est supposé être complet, soit :

Par conséquent, (N ABSURDUM) n'est ni T ni F, ce qui contredit la présupposition selon laquelle N serait un prédicat complet et non trivial. C.Q.F.D.

De ce théorème d'indéfinissabilité, il découle immédiatement qu'il n'existe aucun prédicat complet capable de distinguer les termes qui ont une forme normale de ceux qui n'en ont pas. Il découle également qu'il n'existe aucun prédicat complet, disons ÉGAL, tel que :

Si ÉGAL existait, alors pour tout A, λx. (ÉGAL x A) devrait être un prédicat complet et non trivial.

Cependant, il découle également immédiatement de ce théorème d'indéfinissabilité que de nombreuses propriétés de termes qui sont évidemment décidables ne sont pas définissables par des prédicats complets non plus : par exemple, il n'existe aucun prédicat capable de déterminer si la première lettre de fonction primitive apparaissant dans un terme est un K. Cela montre que la définissabilité par prédicats n'est pas un modèle raisonnable de décidabilité.

### Draft ###

### 1. Query Decomposition

"Pourquoi les propriétés décidables de termes... ne peuvent-elles pas être définies par des prédicats complets dans le calcul combinatoire ?"

Translation: Why are decidable term properties, like determining first primitive function letter, not definable by complete predicates in combinatory calculus?

→ Rice's theorem adaptation to combinatory logic
→ Completeness vs decidability distinction  
→ Primitive function letters = atomic operations

### 2. Core Issue Identification

Classical Rice: No complete predicate for recursive languages distinguishing total/partial functions.

Combinatory calculus variant: No complete predicate distinguishing terms with normal forms from those without.

∴ First letter property cannot be captured by complete predicate because:

**Completeness constraint**: ∀M, ∃normal_form(N) where N = P M
**Decidability constraint**: can determine first letter efficiently
**Incompatibility**: complete predicates must work on all inputs

### 3. Technical Framework

Predicate P is complete iff ∀terms M,N: P(M)≠P(N)
- If P(M)=T then ∃N such that P(N)=F
- Vice versa: if P(M)=F then ∃N such that P(N)=T

⟨H≈0.8⟩ But wait - Rice assumes recursive functions. Combinatory calculus has primitive recursion, normal forms. The contradiction emerges from forcing completeness on inherently undecidable distinctions. Like forcing a finite decision tree to handle infinite computation paths...

### 4. Specific Example

First letter K detection: decidable in constant time
- Input: term T
- Output: True iff T starts with K
- Example: K x → True, SKK → False

Cannot be complete predicate because:
- ∀K-terms: always outputs True
- ∀non-K-terms: must output False OR some other value
- ∴ No complement exists

### 5. Resolution

The fundamental logical tension:
- Decidable properties ⊆ {computable properties}  
- Complete predicates ⊆ {total computable functions}

These sets are disjoint. ∴ No complete predicate captures decidable properties.

! Key insight: Completeness demands universality over computational behavior, but decidable properties are inherently bounded/local.

**Physical constraint check**: ✓ Makes sense - you can't have a single predicate capturing all possible term behaviors while remaining computable.

**Logical verification**: 
```
Let P be complete predicate detecting first-letter K
Then ∀M: P(M) = True if first letter = K
     ∀M: P(M) = False if first letter ≠ K

But this violates completeness: no predicate can distinguish all term pairs
```

**Final synthesis**: The question reveals deep tension between decidability and completeness. Complete predicates must handle all possible computational paths, while decidable properties are inherently constrained. Like trying to fit a finite key into infinite lock.

### Answer###
Les propriétés décidables des termes ne peuvent pas être définies par des prédicats complets dans le calcul combinatoire en raison d'un théorème d'indéfinissabilité fondamental.

Ce théorème stipule que tout prédicat complet est nécessairement trivial, ce qui signifie qu'il ne peut pas distinguer entre différents types de termes selon la propriété recherchée. Plus précisément, un prédicat complet doit pouvoir décider de toute propriété d'un terme, ce qui contredit le fait que certaines propriétés comme la détermination de la première lettre de fonction primitive sont effectivement décidables mais ne peuvent pas être capturées par un prédicat complet.

Le cœur du problème réside dans l'incompatibilité entre la notion de complétude (qui exige qu'un prédicat puisse distinguer tous les termes possibles) et la réalité des propriétés décidables. Par exemple, il n'existe aucun prédicat complet capable de discriminer entre les termes qui possèdent une forme normale et ceux qui ne la possèdent pas.

Cette limitation montre que la définissabilité par prédicats ne constitue pas un modèle raisonnable de décidabilité pour les propriétés des termes. Les propriétés effectivement décidables, comme celle de la première lettre de fonction primitive, échappent à cette représentation prédicative complète.

Cette situation illustre la distinction fondamentale entre les propriétés qui peuvent être décidées par des procédures algorithmiques et celles qui peuvent être exprimées par des prédicats universels complets.