Re:HTML + CSS3 is Turing complete
by jules on Tuesday March 08, 2011 @06:31PM
(#2303054)
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.
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.