Hacker Newsnew | comments | show | ask | jobs | submit login

You are right that the power necessary to parse a language is completely different from the power of the language itself.

There is however a different correspondence between recognizing things and computing functions. If we encode a function as taking a bit string as input and generating a bit string as output, we can turn it into a series of recognition problems as follows: "recognize given S as input, whether bit i of f(S) is 1".

Given all these recognizers, we can compute the function, and given a method to compute the function, we can implement the recognizers.

That is, you can reformulate the question "is f computable" to a series of language recognition problems.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: