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?
6
-
$\begingroup$ What are your thoughts on the matter? $\endgroup$– Yuval FilmusOct 30, 2014 at 19:27
-
$\begingroup$ My belief is in ordinary understanding of Church-Turing thesis. But I want rigorous understanding. If I have to give a reason for my belief, I would say: "The fact that we seem to be able to compute "every" problem that the machine above can compute in TM supports that the machine is Turing machine-equivalent." $\endgroup$– LamosOct 30, 2014 at 19:31
-
$\begingroup$ But the problem is, how do we know "every" is the case? $\endgroup$– LamosOct 30, 2014 at 19:31
-
$\begingroup$ Each sub-machine of the whole machine accepts only problems are recursively enumerable, but these sub-machines can read off the output from different sub-machines, suggesting this is not modelled by NTM (non-deterministic turing machine). $\endgroup$– LamosOct 30, 2014 at 19:33
-
$\begingroup$ You don't nned to know "every" you only need to prove that your construct can simulate a single turing machine $\endgroup$– slebetmanOct 31, 2014 at 4:01
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
In order to show formally that your model only computes computable functions, you need to prove a simulation result: given a set of Turing machines communicating according to some protocol, show how to simulate them on a single Turing machine. Such simulation results show, for example, that multitape Turing machines are no stronger than single tape Turing machines.
The first step in a formal proof would be to formally define your model of computation. Then, given an instance of your model, you have to show how it can be simulated on a Turing machine, or on any other equivalent model. This is going to be very messy, but probably doable.
We usually rely on the Church-Turing thesis and our intuition instead of proving things formally. The reason is that usually such extended computation models are given in order to simplify some proof - to present it in a more comprehensible manner. It would defeat the purpose if each time we would have had to spend many pages proving simulation results.
In the same way, proofs in mathematics are usually not formal in the sense that they are given in some formal axiom system, but rather they rely on the mathematical judgment of the reader. This is part of what is sometimes called mathematical maturity - presenting things using the correct amount of detail.
answered Oct 30, 2014 at 19:37
-
$\begingroup$ So there has been no formal model for such kind of machine? That's a surprise.. I thought given how many concurrent stuffs are going on, there would be a formal machine of this kind.. $\endgroup$– LamosOct 30, 2014 at 19:40
-
$\begingroup$ There might be a formal model, perhaps even several. But I imagine there are several different ways of formalizing it, and it's hard to say what you have in mind. You can search the literature yourself if you're interested. $\endgroup$ Oct 30, 2014 at 19:57