Andrew J Bromage
Thu, 15 May 2003 17:45:28 +1000
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
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.