15 May
2003
15 May
'03
3:45 a.m.
G'day. On Thu, May 15, 2003 at 10:23:21AM +0300, Cagdas Ozgenc wrote:
It is not a power set. A language is a subset of the word monoid generated by the alphabet by applying reccurent production of the alphabet (the star operation).
You're right, sorry.
I always thought in a similar fashion. But literature insists that the decidability is always measured with respect to a Turing Machine.
That's probably because of the Church-Turing thesis (i.e. computation equals Turing Machine). However, there are smaller and larger definitions of "computation" than what can be accomplished on a TM. Cheers, Andrew Bromage