Symmetries and transitions of bounded Turing machines

Details Symmetries and transitions of bounded Turing machines Symmetries and transitions of bounded Turing machines

1998-12-16

arxiv.org/abs/cs/9812019v1

Computer Science

Logic in Computer Science

21 pages, submitted

Scientific paper

We consider the structures given by repeatedly generalising the definition of finite state automata by symmetry considerations, and constructing analogues of transition monoids at each step. This approach first gives us non-deterministic automata, then (non-deterministic) two-way automata and bounded Turing machines --- that is, Turing machines where the read / write head is unable to move past the end of the input word. In the case of two-way automata, the transition monoids generalise to endomorphism monoids in compact closed categories. These use Girard's resolution formula (from the Geometry of Interaction representation of linear logic) to construct the images of singleton words. In the case of bounded Turing machines, the transition homomorphism generalises to a monoid homomorphism from the natural numbers to a monoid constructed from the union of endomorphism monoids of a compact closed category, together with an appropriate composition. These use Girard's execution formula (also from the Geometry of Interaction representation of linear logic) to construct images of singletons.

Affiliated with

Also associated with

No associations

Rating

Symmetries and transitions of bounded Turing machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Symmetries and transitions of bounded Turing machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symmetries and transitions of bounded Turing machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-703722