Content deleted Content added
rv and put a disclaimer on what remains. (1) This is a large chunk of unsourced original research (WP:V, WP:OR). That alone makes it a no-go. (2) Despite the deceptive claims, this argument does not in any way prove the undecidability of combinatorial logic, but a much, much weaker, essential trivial statement that has nothing to do with actual undecidability. |
m Dating maintenance tags: {{Original research section}} |
||
Line 316:
=== Undefinability by predicates ===
{{original research section|date=April 2024}}
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 {{math|'''T'''}} and {{math|'''F'''}} represent the conventional [[Church encoding]]s of true and false, ''λx''.''λy''.''x'' and ''λx''.''λy''.''y'', transformed into combinatory logic; the combinatory versions have {{math|1='''T''' = '''K'''}} and {{math|1='''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.
| |||