Essentially, you can consider a classic Turing machine to consist of a
data/input/output tape, and a program consisting of

-- elementary tape operations
-- boolean operations

I.e. a Turing machine program is a tape plus a program expressed in a
Boolean algebra that includes some tape-control primitives.

-- Ben G

> -----Original Message-----
> From: Stephen Paul King [mailto:[EMAIL PROTECTED]]
> Sent: Tuesday, November 26, 2002 9:25 AM
> Subject: Re: turing machines = boolean algebras ?
> Dear Ben and Bruno,
>     Your discussions are fascinating! I have one related and pehaps even
> trivial question: What is the relationship between the class of Turing
> Machines and the class of Boolean Algebras? Is one a subset of the other?
> Kindest regards,
> Stephen

Reply via email to