5 ms·
as far as I understand it, turing completeness is a weaker property than combinatory completeness, which Craig's theorem is addressing. The nonexistence of a si
by v64 7mo ago
as far as I understand it, turing completeness is a weaker property than combinatory completeness, which Craig's theorem is addressing. The nonexistence of a singleton combinatory basis doesn't necessarily imply the nonexistence of a turing complete combinator.