Miguel Bazdresch miguel at
Fri Feb 14 04:31:40 PST 2003

* Jonathan Wright <mail at> [03-0210 20:16]:
> At around Fri, Feb 07, 2003 at 09:24:21PM +0100, Miguel Bazdresch constructed the following notation:
> > * Jonathan Wright <mail at> [03-0207 16:55]:
> > > At around Fri, Feb 07, 2003 at 03:22:28PM +0100, Miguel Bazdresch constructed the following notation:
> > > > - Turing machines. Imagine the power of a discipline where all you
> > > >   really need to understand is an extremely simple device. A problem for
> > > >   hardware engineers: what's something a Turing machine can do but a
> > > >   finite-state machine can't?
> > > 
> > > Carry though memory into a decision making process?
> > > 
> > 
> > I don't know this problem; would you care to elaborate?
> Hang on, i'll have to get the text book out :) Some of this is taken
> from "Discrete Mathematics and It Appliations".
> A finite state machine is one which can exists in a number of finite
> states with or without input. Using these states (with a designated
> starting state), an input alphabet and a transition function (which
> assigned a new state to the machine for every input and state pair),
> this machine can recognise regular languages sets.

You're right, that's indeed a problem a finite state machine can't
handle. Thanks for taking the time to explain it :)

Another one I know is multiplying two sequences. It's similar to the
pattern recognition problem in that the bits are fed to the machine one
at a time. A finite state machine can't multiply all sequences, and a
turing machine can't.

Note that the thing isn't that a finite state machine can't handle infinite
sequences, it's that there are finite sequences it can't handle.

Miguel Bazdresch
Unsubscribe: send email to listar at
and put 'unsubscribe lfs-chat' in the subject header of the message

More information about the lfs-chat mailing list