It is known that K = (λx.(λy.x)) and S = (λx.(λy.(λz.((x z) (y z))))) define a turing complete system, and we know procedures to map back and forth from lambda calculus to SK calculus. Now, given two arbitrary combinators, A and B in the set of valid lambda terms, is there an algorithm that will answer whether those combinators define a turing-complete system, and what is the corresponding mapping between a lambda term and those combinators? If not, is there such an algorithm with additional restrictions on the shape of A and B (say, its depth), that could be effectively used to find systems that are similar to SK?

  • 1
    $\begingroup$ Your question is ill-posed, and once it gets fixed it is not research-level. How are the combinators specified, by equations? If so, then there won't be an algorithm because a special case of what you're asking for will be the undecidable semigroup word problem. $\endgroup$ – Andrej Bauer Nov 13 '14 at 7:52
  • 1
    $\begingroup$ @Viclib: I think you need to fix your manners too. $\endgroup$ – Dave Clarke Nov 13 '14 at 18:33
  • 3
    $\begingroup$ It's a perfectly valid question for cstheory. The word problem for (semi-)groups is probably not known in detail to most theoretical computer scientists and is not usually covered in undergraduate texts on group theory. The applicability of word problems to combinators would also be unclear to most CS folk. $\endgroup$ – Martin Berger Nov 14 '14 at 8:53
  • 1
    $\begingroup$ Isn't this undecidable simply because of Rice's theorem? $\endgroup$ – Emil Jeřábek Nov 14 '14 at 11:33
  • 2
    $\begingroup$ Whether Andrej is right or not about the question, I don't think he was "agressive". There was no emotion in his comment, just a technical opinion about a question not being well-posed. Viclib, if you don't know enough about your question to know if it is research level, you should ask it at CS.stackexchange.com $\endgroup$ – Sasho Nikolov Nov 16 '14 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.