Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I know everyone says SK combinators can express any computable function, but I don't get it. How do we write this function foo in terms of SK combinators alone? Is there some obvious programming trick I'm missing that makes it trivial? (It wouldn't be the first time.)

foo(x) = if (x == K) return S else return K



That's not a computable function. Function equality (x==K) is undecidable.


And that's covered in the last chapter of To Mock a Mockingbird (this submission prompted me to pull it off the shelf this morning).


Just postulate function extensionality and move on with life. :D


Are you asking how to do a if else statement?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: