patternMinor
Finite number of Turing machines running concurrently on multi-tapes Turing-machine-equivalent?
Viewed 0 times
numberfinitemultiequivalenttapesrunningmachinesmachineturingconcurrently
Problem
So basically, there are several (finite number of) Turing machines being able to read off and write to the same set of tapes (the number of tapes is finite, but each tape may have infinite tape spaces). And then we consider a group/machine of these machines to solve a problem. Would this machine be Turing machine-equivalent?
Solution
A roung, informal sketch of how I would prove this:
-
We can simulate multiple threads running concurrently in a programming language like C. (Note that this is without hardware support! There are some cool ways to do this, my favorite is using continuations in Scheme, inserting a call to a thread scheduler whenever a function returns).
-
We can simulate a multi-tape TM with a single-tape TM.
-
We can simulate a single-tape TM in a programming language like C.
From this, we get that we can simulate a multi-tape TM in our programming language. Since we can simulate threads, we can now simulate multiple multi-tape TM's running concurrently.
And, since we can simulate C with a single-tape TM, we can simulate the whole thing with a single-tape TM.
The transitivity of turing-completeness is a useful tool. That is, if A simulates B, and B simulates C, then A simulates C.
-
We can simulate multiple threads running concurrently in a programming language like C. (Note that this is without hardware support! There are some cool ways to do this, my favorite is using continuations in Scheme, inserting a call to a thread scheduler whenever a function returns).
-
We can simulate a multi-tape TM with a single-tape TM.
-
We can simulate a single-tape TM in a programming language like C.
From this, we get that we can simulate a multi-tape TM in our programming language. Since we can simulate threads, we can now simulate multiple multi-tape TM's running concurrently.
And, since we can simulate C with a single-tape TM, we can simulate the whole thing with a single-tape TM.
The transitivity of turing-completeness is a useful tool. That is, if A simulates B, and B simulates C, then A simulates C.
Context
StackExchange Computer Science Q#32491, answer score: 4
Revisions (0)
No revisions yet.