Bug Vanquisher

17 May 2007

What Turing Machines are not!

Filed under: Computer Theory, Decontamination — Tanveer Badar @ 2:15 PM

I read this on Eric Lippert’s blog:

“Because the number of states is so large, it is often more helpful to model machines as “Turing machines”, which can have unlimited internal storage”

Immediately, a pain started in my head. I had to write what follows as a comment and on my blog!

A Turing machine is a Turing machine because it can read/write its storage in random order. This makes it recognize languages of type anbncn. Take away the write capability, it reduces to a FSA, capable of only recognizing an. Strip away the random access, languages recognized reduce to anbn.

Turing machines never have infinite states. No model for a computing machine has infinite states. What can be infinite is

1- input set (can be infinite in any case)
2- output set (can be infinite in any case)
3- memory (aka. internal storage, is infinite only starting from push down automata)

Consider the problem of having infinite states in Raymond style: What would happen if a machine could be constructed which had infinite states?

1- There would be no way to encode those states in any base. A simple state machine can be encoded in ceil( log2(states) ) number of bits. This number is always infinite for infinite states.
2- The machine’s control would alone require infinite storage.

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: