**Stephen P. King** (*stephenk1@home.com*)

*Sat, 20 Mar 1999 13:47:40 -0500*

**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]**Next message:**Matti Pitkanen: "[time 41] Re: [time 37] Re:The ordering of spatial states and temporalevents"**Previous message:**Stephen P. King: "[time 39] Re: [time 37] Re:The ordering of spatial states and temporalevents"**In reply to:**Matti Pitkanen: "[time 38] Re: [time 37] Re:The ordering of spatial states and temporal events"

Dear Hitoshi and Friends,

Hitoshi Kitada wrote:

*>
*

*> Dear Stephen,
*

*>
*

*> A Turing machine is a local system that evolves along its local time producing
*

*> a tape. Each square cell of a tape you write is a state of the LS at each
*

*> corresponding time. The total history of the LS is the infinite length tape,
*

*> and hence cannot be read by any observer due to the "infinity" of the length
*

*> (note that it is said that Turing machine has a finite length tape, i.e. the
*

*> effective number of holes on the tape is finite. But there is no finite method
*

*> of judging at which point of the tape the holes end). This supports your
*

*> statement
*

*>
*

*> >"a infinite length tape divided into square cells..." can
*

*> >neither be read or written to by a "head which can be in in a finite
*

*> >number of internal states"
*

*>
*

*> without any additional condition. I.e. "iff part" in your post is unnecessary.
*

Interesting! This takes us into the arena of quantum computational

complexity! I have a very good paper that Peter references in one of his

papers:

Quantum Complexity Theory by Ethan Bernstein & Umesh Vazirani available

at

http://http.cs.berkeley.edu/~vazirani/bv.ps

http://http.cs.berkeley.edu/~vazirani/

http://hera.eecs.berkeley.edu/Seminars/Old.97/February/970228.bernstein.html

(Please indulge my lengthy quotation, there is a subtle point to be

made! :) )pg. 11-13 ibid.

It mentions: "This model may be thought of as a quantum physical

analogue of a probabilistic TM - it has an infinite tape and a finite

state control, and the actions of the machine are local and completely

specified by this finite state control. In full generality, on any given

input a quantum TM produces a random sample from a probability

distribution."

How the 'size' of the sample is defined seems to be given by: "In full

generality, on any given input a quantum TM produces a random sample

from a probability distribution. We say that quantum TM T' simulates T

with accuracy e, if on every input x, T; outputs a sample from a

distribution which is within total variation distance e of the

corresponding distribution for T. We prove that there is a universal

quantum Tm which takes as an input the description of a quantum TM T,

time t, and input x, and simulates T(x) for time t with accuracy e. The

slowdown is polynomial in t and 1/e."

continuing...

"...[it was shown] that there is an oracle relative to which there is a

problem that can be solved in polynomial time on a quantum TM, whereas

any classical probabilistic TM, which is restricted to *always* give the

correct answer, requires exponential time. However, the crucial

assumption in all the above results is that the classical TM is required

to be error-free. For all the above problems, quantum TMs exhibit *no*

advantage in running time over classical probabilistic TMs that are

allowed a small probability of outputting the wrong answer on any input.

It is well known that the error probability of such a probabilistic TM

can be reduced to be a negligible value (for example, much smaller than

the chance of hardware failure) at a very modest increase of running

time."

"We prove that there is a oracle relative to which there is a language

that can be accepted in polynomial time by a quantum TM but cannot be

accepted in n^0(log n) time by a bounded-error classical probabilistic

TM."

[I am very wary of these "oracles", they tend to assume a priori

information that is not constructible in finite space/time, much like

classical physics use of Cauchy hypersurfaces to fix ab initio the

Universe!]

"Before we can formally define a QTM, we must introduce some new

terminology... The new terminology is necessary because quantum

mechanical systems cannot be observed without without being altered. Let

us consider how can describe the computation of a PTM if we are not

allowed to observe it while it is working. Therefore, we imagine that

the PTM, T, is placed in a black box. The rules of the game are that we

know the finite state control of T, as well as its initial

configuration, and the interval of time between successive steps. What

is we must not observe are the outcomes of any coin-flips that T makes.

If we mentally keep track of T's configuration, then we would know when

it flipped its first coin, but we would not know which of the two

possible successive configurations it entered. Instead we will say that

the machine is in a linear superposition of the two configurations, and

assuming that the coin is fair, the coefficient for each configuration

is 1/2."

[this constructs a binary Farey tree of possible configurations...?!

http://www.hotbot.com/?MT=Farey+tree&SM=phrase&DV=0&LG=any&DC=100&DE=2&clickSrc=search&_v=2&OPs=MDRTP&ACF=1]

"We shall refer to the coefficient of a configuration as its

*amplitude*. As the machine continues to compute and flip coins, it

will, in general, be in some linear superposition of its configurations.

Given the linear superposition at one time step, how do we compute the

amplitude of a configuration in the superposition at the next time step?

First we apply the finite state control's rules separately to each

configuration in the superposition, and then we take the sum of these

contributions weighted according to the superposition's amplitudes.

Notice that this means the machine's finite state control is really

specifying a linear mapping in the space of superposition's of

configurations. This will remain true even if we give up the assumption

that the machine must toss a fair two-sided coin, and instead allow the

machine several arbitrary many-sided coins [dice! :)] Suppose we think

of the transition function ó of a randomized TM on state set Q and an

alphabet £ as

ó : Q x £ x £ x Q x {L, R}-[0,1]

[ó = \delta £ = \sum]

where ó(p,\sigma,\tau, q, d) gives the probability that if the machine

is in state p reading a \sigma it will write a \tau, enter state q, and

move in the direction d. Then the machine's transition function is a

linear map, given by the matrix where the entry corresponding to the

configuration c_1 row and the configuration c_2 column is ó evaluated at

the tuple which transforms c_2 into c_1 in a single step, or 0 if no

such tuple exists. Since the number of possible configurations is

unbounded, this matrix has infinite dimension. Nevertheless, it's

finitely specified and satisfies a locality constraint. We shall refer

to this matrix as the *time evolution operator* of the PTM. Depending on

the particular machine, as the machine runs, its superposition may

easily include an exponential number of distinct configurations. But,

regardless of the machine, the linear superposition's will always

contain only non-negative amplitude and the amplitudes will always sum

to one.

Now, let's think about what happens when we open the box and observe the

machine. We will find the machine in a specific configuration - not a

linear superposition. The act of opening the box and observing the

machine, forces it to choose a configuration out of the linear

supposition - the rule is that each configuration is chosen to be

observed with probability equal to its amplitude in the linear

superposition. Next, consider the case where we are only interested in

one particular bit of the configuration, and we take a quick peek inside

the box to examine just that bit. Then we will see a one with a

probability equal to the sum of the amplitude of configurations with a

one in that position, and a zero with probability equal to the sum for

configurations with a zero."

[I must say that the act of 'locating' the coordinate of that "one bit"

must be taking into account. The Maxwell Daemon stuff is relevant.]

"We will then think of the machine as being in a linear superposition

corresponding to the distribution of configurations corresponding to the

actual bit we saw. This superposition could be computed by first erasing

the amplitudes of all configurations inconsistent with the observed

value, and then scaling up the remaining amplitudes to maintain unit

sum. [artificially preserving unitarity!] Therefore, we think of the act

of observing a bit as operating on the machine to effect this

restriction and renormalization.

Finally, note that although the superposition (distribution) of the

machine after t steps may take exponential space to write, we can sample

from it online in the obvious way. Each time our simulation's

configuration splits, we can choose a single next configuration randomly

according to the split's weights. This on-line simulation may

alternatively be achieved by observing the PTM after each step. It is

easy to see that these multiple observations leave the final output

distribution undisturbed."

I must comment on this last statement! From what I have read of the

Quantum Zeno effect, the machine's evolution would be 'frozen' by these

on-line observations. How the authors propose to get around this I don't

know. :(

cf. etc.

http://feynman.stanford.edu/publications/recent_publications/q_measurement_computer.html

http://www.qubit.org/people/davidw/

http://www.theorie.physik.uni-goettingen.de/~sonderma/files/zeno.pvt.html

We also have Karl Svozil's paper

(http://tph.tuwien.ac.at/~svozil/publ/kraft.ps) discussing the Kraft

inequality "restricts the number of legal [consistent?] programs due to

the condition that to [a?] legal program can be the prefix of another

legal program. The Kraft inequality then states that no more than

maximally q=n^k programs can be coded by a successive array of k

identical beam splitters with n slots, corresponding to l_1 = l_2 = ...

= l_q. " and "the price of speedups of computations originating in

quantum parallelism is a corresponding attenuation of the computation of

the computational probability. In order to compensate for an exponential

decrease of execution probability, one would have to *exponentially

increase* the number of (bosonic) quanta in the beam paths. This,

however, is equivalent to the trivial solution of an arbitrarily complex

problem by the introduction of an arbitrary number of classical parallel

computers."

Another method to attack this question is the subject of Peter Wegner's

work on "Interaction Machines." And, I must mention that he conjectures

that quantum nondeterminism (such as that discussed by Hitoshi with

respect to the EPR problem) would be well modeled by 'secondary' on-line

observer interacting with the 'same' LS via a different interface. Peter

and I have discussed this at length and hope that some progress can be

made in the future.

http://www.cs.brown.edu/people/pw/papers/math1.ps

I have more ideas about this subject but I'll reserve them to later...

:)

*> Best wishes,
*

*> Hitoshi
*

*>
*

*> -----Original Message-----
*

*> From: Stephen P. King <stephenk1@home.com>
*

*> To: Time List <time@kitada.com>
*

*> Date: Thursday, March 18, 1999 1:19 AM
*

*> Subject: [time 27] Turing machines under difeomorphisms?
*

*>
*

*> >Hi all,
*

*> >
*

*> > A quick note: Can we think of Turing Machines as existing under the
*

*> >diffeomorphism invariance of GR, as Hitoshi explains it? It seems to me
*

*> >that the same conditions that prohibit clocks from being definable also
*

*> >imply that "a infinite length tape divided into square cells..." can
*

*> >neither be read or written to by a "head which can be in in a finite
*

*> >number of internal states" iff those cells are infinitesimal invariant
*

*> >under diffeomorphism transformations!
*

*> >
*

*> >cf. "Returning to the origin of the problem, i.e. to the idea of
*

*> >relativity theories, a cause of the problem of time seems to lie in associating time to each point
*

*> >which has no positive size. No clocks can reside in a sizeless point. At the stage of
*

*> >special theory of relativity, this difficulty does not appear: Time is associated to each
*

*> >inertial frame which can accommodate actual clocks. At the stage of general theory of
*

*> >relativity, the field equation with the invariance postulate with respect to
*

*> >diffeomorphisms requires one to eliminate the size of the frames in which clocks reside."
*

*> >
*

*> >http://www.kitada.com/
*

Onward to the Unknown!,

Stephen

**Next message:**Matti Pitkanen: "[time 41] Re: [time 37] Re:The ordering of spatial states and temporalevents"**Previous message:**Stephen P. King: "[time 39] Re: [time 37] Re:The ordering of spatial states and temporalevents"**In reply to:**Matti Pitkanen: "[time 38] Re: [time 37] Re:The ordering of spatial states and temporal events"

*
This archive was generated by hypermail 2.0b3
on Sat Oct 16 1999 - 00:29:45 JST
*