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?
Time-entanglement phenomenon
ds.algorithms;computability;quantum computing
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.