Turing Machines on Graphs and Inescapable Groups

Details Turing Machines on Graphs and Inescapable Groups Turing Machines on Graphs and Inescapable Groups

2010-05-14

arxiv.org/abs/1005.2636v1

Mathematics

Logic

18 pages, one table

Scientific paper

We present a generalization of standard Turing machines based on allowing unusual tapes. We present a set of reasonable constraints on tape geometry and classify all tapes conforming to these constraints. Surprisingly, this generalization does not lead to yet another equivalent formulation of the notion of computable function. Rather, it gives an alternative definition of the recursively enumerable Turing degrees that does not rely on oracles. The definitions give rise to a number of questions about computable paths inside Cayley graphs of finitely generated groups, and several of these questions are answered.

Affiliated with

Also associated with

No associations

Rating

Turing Machines on Graphs and Inescapable Groups 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 Turing Machines on Graphs and Inescapable Groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Turing Machines on Graphs and Inescapable Groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-240779