DJ Strouse

The Zealot King Problem
Let’s say you’re the king of a far-off land inhabited by Turing machines. As a highly religious king, you have strict morals and lately, you’ve been frustrated to see many of your citizens acting immorally. You’ve been especially aghast at their frequent and flagrant violation of restriction R. Restriction R isn’t a law, but you simply find its violation morally repugnant. Your department of mad scientists has shown that Turing machines operating under restriction R are just as powerful as those that don’t, so you don’t feel bad about taking away your citizen’s privileges to break restriction R. Thus, the religious zealot you are, you do it; you declare a law that no Turing machine may violate restriction R on any input.

Now you need to enforce your law. You need to make a Turing machine police force that runs around testing passerbys to see whether they are upstanding, R-abiding Turing machine citizens. Can you do it?

Further Motivation for the Theoretical CS Junkie
After an awesome course in mathematical logic with Len Adleman at USC that flirted with issues of computability, I’ve been addicted to theoretical CS textbooks, including Michael Sipser’s excellent Introduction to the Theory of Computation. One exercise (5.28) introduces Rice’s theorem, which states that the question of whether or not a Turing machine’s language has some non-trivial property is undecideable. But this only holds for “linguistic” properties – those of the Turning machine’s language. You might wonder (at least I did), what about “operational” properties?

Certainly there are some operational properties we can decide. Does [insert your favorite Turning machine here] move left on step 6 for any input of length 10? Beats me, but I could sure simulate your Turing machine for 6 steps on each of the n^10 strings of length 10 (where n is the number of symbols in your tape alphabet) and check.

But there are plenty more operational properties that we can’t decide. I was interested in identifying the conditions that make an operational property undecideable, and I’ve at least found a sufficient set.

I post this little result here for several reasons:

1. Someone has very likely already cooked up a much tighter solution to this (or a similarly stated) problem already.  If anyone reading this knows of such work, please point it out!
2. I’m a TCS noob and would love for someone to prove my conditions wrong.
3. Is there a more general set of conditions than the ones I give?  Are there other more interesting tweaks to Rice’s theorem?  Any ideas here are welcome.
4. I’m a sucker for open science.

Formalism & Proofs
First, let’s define two conditions that the restrictions we will consider must have.

Definition 1: A restriction R is “gentle” if for every Turing machine T, there exists another Turing machine T2 that operates under the restriction R and recognizes the same language as T.

In other words, R does not reduce the power of Turing machines.

Definition 2: A restriction R is “non-expiring” if, given any Turing machine T and input w, there does not exist a number of steps N such that if T has run for N steps on w without halting, it is no longer possible for T to violate R.

In other words, R can be violated at any point in a computation and there is nothing a Turing machine can do to “lose” the opportunity to break R, besides halting.

Lemma: Given a “gentle” restriction R, it is possible to create a Turing machine S that never violates R and upon input <T,w>, where T is a Turing machine and w is some string in the tape alphabet of T, S simulates T on w.

Proof:
Its well-known that we can create a universal Turing machine U that given inputs of the type <T,w> simulates T on w (if you don’t believe me, go try to do it yourself or check out Wikipedia). By the definition of “gentle”, we can also create U2 that operates under restriction R and for inputs <T,w>, simulates T on w. This U2 is our desired S.

Theorem: Given a “gentle” and “non-expiring” restriction R, the language BEHAVED = {<T>: T is a Turing machine that does not violate R on any input} is undecideable.

Proof:
We’ll prove this by reduction to the halting problem, described by the language HALT={<T,w>: T is a Turing machine and T halts on w}. That is, we’ll assume we have a Turing machine deciding BEHAVED and build one that decides HALT.

Let B be a Turing machine that decides BEHAVED. Construct the following machine H that decides HALT.

H= “On input <T,w>,

1. Construct the following machine N.  On any input x,
   1. Run R-abiding simulator S (from the lemma) on <T,w>.
   2. If S accepts, violate R and halt.
   3. If S rejects, violate R and halt.
2. Run B on <N>.
3. If B accepts <N>, reject <T,w>.
4. If B rejects <N>, accept <T,w>.”

If S halts (accepts or rejects), N violates R and halts.  If S doesn’t halt, N never violates R and doesn’t halt.  So N violates R if and only if S halts.  By definition, S halts if and only if T halts on w.  So N violates R if and only if T halts on w.  Also, by definition, B accepts <N> if and only if N does not violate R for any input.  So B accepts <N> if and only if T does not halt on w.  So by steps 3 and 4 of H’s description, H decides HALT.

Justification of “Gentle” and “Non-Expiring” Conditions
I needed the “gentle” condition for the lemma.  If the restriction actually reduces the power of Turing machines, the above method of building some Turing machine simulator that operates under that restriction and only violates it to signal some particular situation (i.e. halting) won’t work, since the simulator won’t be universal.

I needed the “non-expiring” condition to make sure that when S finishes simulating T on w, its still possible for N to violate R.  This condition kicks out those easily decideable restrictions that I mentioned earlier.

Any suggestions on tweaking these conditions are welcome.

Some Examples of “Gentle”, “Non-Expiring” Restrictions
Turing machines are robust little guys and we can come up with plenty of plenty of restrictions that won’t reduce their power. Here are some examples mostly adapted from Sipser’s text:

• Only move left to “reset” like a typewriter (that is, if you want to move left, you have to go all the way to the left edge of the tape and then work your way to the right again).
• No writing on multiple tapes (for instance, we could lay out several tapes to “tempt” a Turing machine, then demand that it only use one).
• No exploiting non-determinism (similarly to the multi-tape case, we could give a Turing machine the option of “branching”, then demand it not do so).
• Alter each tape square only once.
• No using squares of a doubly infinite tape to the left of some given square (that is, we give a Turing machine a doubly infinite tape, then demand it not cross a certain boundary, effectively restricting it to the usual semi-infinite tape).

I’m sure you can come up with many more and feel free to share your favorites.

Tags:   computability · theoretical computer science · turing machinesNo Comments.

My recent hacks at trying to find the scattering and bound states of a semi-infinite line attached to a single weighted edge (the simplest graph imaginable) hadn’t been too successful until today. I had not really been sure about how to approach the problem and had only written down a Hamiltonian and postulated some qualitative behavior of the eigenstates (scattering states should scatter, bound states should be bound, etc). Fortunately, I had a very helpful phone call with Andrew this morning.

I told him what I had been able to work out and where I was stuck and he guided me towards the right approach. The key lessons were that (1) we can assume that scattering states look like plane waves where the graph edges are unweighted, (2) while the reflection coefficient for this baby graph does have amplitude one, it crucially also as a nontrivial phase, and (3) the basic strategy for these types of problems is to investigate the “boring” parts of the graph (unweighted semi-infinite lines), postulate solutions that work there with some undetermined constants, and then use the “interesting” regions (single weighted edge in this case) to pin down the constants.

I’m really looking forward to my time in Waterloo because so far, Andrew is proving to be a great advisor. He was patient enough on the phone to offer hints and then wait for me to think about them and calculate in real time. (I’ve seen far too many professors begin twitching and intervening in the presence of a student deviating slightly from the method of calculation that professor prefers.) His suggestions were just helpful enough so that I understood how to approach a calculation, but vague enough that there was still plenty of the puzzle to figure out.

After the phone call, I spent the next couple of hours jiggling around some equations (anyone who’s ever calculated a reflection coefficient knows scattering problems are an algebraic hellstorm) and was able to find the scattering states and their energies, the bound states and their energies, and some nifty “alternating” bound states and their energies (these states are “alternating” because they are similar to the regular bound states except there’s a sign flip in the amplitude at every other vertex).

For the bound states, I found that:

• the spectrum is discrete
• there is only one bound state
• the transcendental equation yielding that bound states only has solutions for certain minimum strengths of the weight on the weighted edge

Stumbling across the transcendental equation was a nice surprise because last night, my friend and web dev/computational physics guru Casey Stark gave me a crash course in using Mathematica (check out his tips here), and transcendental equations are a great excuse for exploiting Mathematica’s plotting tools.

I’ve still got some algebraic housekeeping to do to clean up the expressions I obtained today, but given today’s success, I should be ready to tackle big boy graphs in no time!

Tags:   analytic · levinsons theorem · quantum information · quantum walks · scattering4 Comments

Before Professor Lidar and I dive into optimization, I’m trying to reproduce the results found in Table 1 of the Invisible Quantum Tripwire paper, specifying the efficiency of the IFM procedure for various settings of the parameters (number of times the photon cycles through the interferometer, total phase rotation angle, and amount of loss in the detection arm).

I’ve been iterating back and forth between Mathematica and my own simplifications, trying to clean up the formulas that feed into the efficiency calculation so that we can analyze them further.

Unfortunately, I’m currently frustrated by two problems that I’ve poured about six hours into now.

First, I’ve successfully reproduced the probabilities of all the various experimental outcomes, but when I collect them together and calculate the Chernoff distance C2 found on page 3, my values are consistently higher than the authors’. I’ve checked and re-checked my work and I can’t find any mistakes. Either there is a misprint in the article or I’m incorrectly using some function in Mathematica. I emailed the authors, asking for their code, and I’ll also try to consult with a Mathematica veteran. (Another pair of eyes would be really helpful right now.)

Second, I’m trying to perform an eigendecomposition of the evolution matrix. The eigenvalues I obtained by simplifying Mathematica’s symbolic calculation and plugging in the parameters I’m using match up with those yielded directly by a numerical Mathematica calculation. However, the eigenvectors don’t. For some reason, Mathematica returns a different set of eigenvectors, depending on whether I calculate symbolically and then substitute parameters, or whether I substitute parameters and then calculate numerically.

At this point, I’m out of ideas until I find a fresh pair of eyes to confirm that I’m not doing something crazy.

Tags:   Math · mathematica · physics · quantum computing · quantum information · science3 Comments