2
$\begingroup$

Please let me mention certain idea here, although it is probably vague (and new, at least as related to experiment mentioned below, as far as I know).

The general notion of algorithm is model of computation with finite number of steps which my be performed on device from "set of computational devices". Up to now "Set of Computational devices" consists of quantum and classical computers which both may be simulated on Universal Turing Machine. It means that Turing machine remains the most general model for computations ( which is in harmony with other notions of effective computable functions like lambda-calculus or recursive functions).

So let me explain motivation to as question at the end:

Turing Machine is in some way connected with notion of time (it is idealisation of computation by performing "one operation" at a time). As we discover new interesting phenomena ( famous discovery: http://arxiv.org/abs/1101.2565 mentioned also here http://www.technologyreview.com/blog/arxiv/26270/ ) probably it is time to ask what is the role of time in Turing Computation model and if it has rigorous enough definition.

Let's imagine a simple Gedankenexperiment: Imagine a class of TM for which initial Data and Result has to be at least 4 ( in general n - natural number) cells one after other - it looks like artificial idea, but when we refer to separation in time - it sound very natural. We use "separation in time" as very natural notion: in fact we require it - answer has to be obtained after question - right?. So, in a light of existence of phenomenon like time-entanglement - mentioned in references above - it is probably time for review... It is not clear for me if this phenomenon point on something new but it may...

Of course "notion of time" is not so important here at all, probably the notion of order is sufficient enough ( although I do not know how such change would result in quantum computations where time is important parameter I suppose, but we may say - in mathematical idelisation/model probably it may be not important).

The questions:

(1) Order dependency of TM - is it new idea?

(2) Is it interesting?

(3) Even for finite sets we still may use abstract concept of lattice to model order of algorithm steps. Is it useful for example for parallel computation model?

(4) It looks like Universal Turing Machine definition use strict order of algorithm steps. Why? If ten we change notion of time order in UTM to notion of abstract order, will that change notion of algorithm/Turing Machine definition? Was that analysed by someone?

(5) When we go to hypercomputational models: may we use continuous index as "time order" replacement? Are there any important consequences of such change?

(6) Was there any influence of time-entitlement on our computational model discussed?

Improve this question
$\endgroup$
9
  • 4
    $\begingroup$ (4) If you have a partial order instead of a total order, then you will have exactly what people have studied in circuit complexity, parallel computing, distributed computing, etc. for decades. $\endgroup$
    – Jukka Suomela
    Mar 3, 2011 at 10:17
  • $\begingroup$ (1), (2) I'm not sure if I was able to follow your description. In general, adding artificial restrictions like this does not change anything relevant. If you have a "traditional" Turing machine, and it happened to print its output in the "wrong" place (too close to the input), it can easily fix it afterwards and move the output in the right place. In the end, you will usually have the same complexity classes, regardless of which variant of Turing machines you use. $\endgroup$
    – Jukka Suomela
    Mar 3, 2011 at 10:25
  • $\begingroup$ In general, I am not sure if this question is on-topic here. It does not seem to be research-level TCS. $\endgroup$
    – Jukka Suomela
    Mar 3, 2011 at 10:26
  • $\begingroup$ @Jukka - thank a lot for Your answer - it is very helpful. Please let me ask about one more thing: time-entanglement means that certain probabilities in quantum computations both in the future or in the past are tied together. Is that phenomenon anything new here? I cannot translate it on TM terminology. Also Could You give an example of paper or book in which partial order in TM is mentioned explicate? I suppose You are right here mentioning parallel computations but do they use order formalism to describe that explicit? $\endgroup$
    – kakaz
    Mar 3, 2011 at 10:38
  • 2
    $\begingroup$ @kakaz: For computation with partial order, look at any introductory book on distributed computing. $\endgroup$
    – Peter Shor
    Mar 3, 2011 at 11:58

2 Answers 2

Reset to default
13
$\begingroup$

Time-entanglement means that quantum information from the past may be teleported into the future without actually being present in the interval between. However, teleportation of one qubit requires two classical bits and one EPR pair, and these must exist in the interval, so there is no saving of space: you need to get half of the EPR pair and both classical bits into the future, and that requires a qubit's worth of quantum memory. So this process does not effect complexity classes.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank You a lot! Could I have one more question? There are two interesting physical phenomena: time (a) and space (b) - entanglements of data representation. Whilst turning on (b) transform us from classical to quantum algorithms, the first one was probably not analysed. Was there any influence of time-entitlement on our computational model discussed? It may do not change complexity classes but provide us with interesting results. From Your answer I presume it will be mainly practical but not theoretical ones. Is that true? $\endgroup$
    – kakaz
    Mar 3, 2011 at 12:06
  • 6
    $\begingroup$ Space-teleportation is in some sense much more interesting than time-teleportation, because in time-teleportation, the data is in some sense present at all times, it's just disassociated into a number of parts, but at any given intermediate time somebody who wanted to could reconstruct it, whereas in space-teleportation, the data never actually passes through the intermediate locations (or, if you want to take Charlie Bennett's point of view, the quantum part of the data passes through the intermediate locations before the teleportation process starts and before Alice receives the data). $\endgroup$
    – Peter Shor
    Mar 3, 2011 at 15:01
  • 5
    $\begingroup$ Comment continued: Time-entanglement is not really a new concept; it's a new way of looking at quantum phenomena that were previously known. You should be able to view the quantum eraser experiment in terms of time-entanglement, and the quantum eraser experiment was invented and performed well before the concept of time-entanglement was introduced. So you're not going to get anything new in terms of complexity from time-entanglement, although maybe you'll get a better way to explain the quantum eraser experiment. $\endgroup$
    – Peter Shor
    Mar 3, 2011 at 15:04
1
$\begingroup$

When we studied Turing Machines, our teacher proved that a good many modifications you might want to make towards a Turing Machine to improve it could easily be simulated by the original Turing Machine, things like two tapes and two read/write heads, an infinite amount of tapes and an infinite amount of read/write heads, an infinite number of symbols to write, etc.

The theory was that the functionality of a computer is a subset of a Turing Machine. I'm not sure how quantum memory would work, but if there were blocks of data on the tape which change over time, it could be simulated by a few more states in the Turing Machine which specify that it should return to an old position and rewrite over it, then return to its old position, effectively simulating a block of data which changes over time. Of course "time" isn't existent in a Turing Machine, but you could write a number representing the number of steps until it needs to change a particular symbol on the tape at a certain position.

Again, perhaps not efficient, but it can be simulated, therefore it couldn't enhance the functionality of a Turing Machine any more than it is.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I agree, what You say is more or less obvious, thank You, but question consists of 2 related subquestions: one about time-entanglement and second about theoretical and abstract ordering notion. The second one is still not answered. $\endgroup$
    – kakaz
    Mar 3, 2011 at 18:06
  • 4
    $\begingroup$ I think the reason nobody has answered the second part is that there is a huge amount of work on the question of time ordering in the distributed computation/parallel processing literature, some of it very theoretical, and some of it undoubtedly applies to TM's, even if it doesn't strictly mention them. It's such a broad area it's impossible to describe adequately without writing a short monograph on the subject. I don't know whether anybody has looked at time ordering specifically for Turing Machines, but they certainly have for cellular automata. $\endgroup$
    – Peter Shor
    Mar 3, 2011 at 19:20
  • $\begingroup$ Thanks a lot for Your answers. I accept Peter answer because it point in interesting for me way. But Your answer Neil is also interesting ( although somehow obvious, I am appreciate Your effort) so I would like to give it the higher score. Unfortunately I do not have 15 or more points, so I cannot. Then I will do this in the future if I gather enough points. Thanks once more. $\endgroup$
    – kakaz
    Mar 4, 2011 at 6:56
  • $\begingroup$ I apologize if it was too evident what I was saying. My intentions were merely to share what I know, even if I perhaps don't know as much as others. With what concerns score, I don't really care one way or the other so long as I can post questions and respond to answers. $\endgroup$
    – Neil
    Mar 4, 2011 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.