On the time complexity of 2-tag systems and small universal Turing machines

Details On the time complexity of 2-tag systems and small universal Turing machines On the time complexity of 2-tag systems and small universal Turing machines

2006-12-19

arxiv.org/abs/cs/0612089v1

FOCS 2006: 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE, pages 439-446, Berkeley, CA

Computer Science

Computational Complexity

Slightly expanded and updated from conference version

Scientific paper

We show that 2-tag systems efficiently simulate Turing machines. As a
corollary we find that the small universal Turing machines of Rogozhin, Minsky
and others simulate Turing machines in polynomial time. This is an exponential
improvement on the previously known simulation time overhead and improves a
forty year old result in the area of small universal Turing machines.

Affiliated with

Also associated with

No associations

Rating

On the time complexity of 2-tag systems and small universal 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 On the time complexity of 2-tag systems and small universal Turing machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the time complexity of 2-tag systems and small universal Turing machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-315093