Undecidability

Using the ideas in this article, we find for every Turing machine a lattice with local interactions. Thus, for every undecidable question we find that the long term dynamics of the corresponding lattice system is undecidable as well. 

One of these undecidable questions is whether or not the spin wave associated with the copy process will ever occur. This is because the spin wave spreads out as soon as the computation has finished. The question of whether a computation ever finishes is Turing s famous halting problem, which is undecidable. 

A summary and certain remarks with an emphasis on the universal quantum Turing machines that have been analyzed in the last three sections are in order  

We showed that it is possible to implement Turing computation on a two-dimensional spin lattice system. The correspondence between reversible Turing machines and the system described in this work is very close. This makes it easy to apply complexity theoretical results about reversible machines to locally acting quantum computers. 

Certain questions about the dynamics of classical chaotic systems are rmdecidable, as shown in [36,37]. Since it was shown that quantum computation can be universal, it follows that there are many undecidable questions concerning the long term dynamics of quantum systems. 

---

A distinction is made between two varieties of the grass Sofia and "motla, but st is for the present undecided whpthev they are hotanioaJ varieties, or only different condiiiousof maiiiiniy of ihe same species. 

Unschlit n. tallow, suet, -seife,/. tallow soap, un-schliissig, a. undecided, irresolute, -schmackhaft, a. insipid, unpalatable, -schmelzbar, a. infusible. 

More specifically, the basic notions of a Turing Machine, of computable functions and of undecidable properties are needed for Chapter VI (Decision Problems) the definitions of recursive, primitive recursive and partial recursive functions are helpful for Section F of Chapter IV and two of the proofs in Chapter VI. The basic facts regarding regular sets, context-free languages and pushdown store automata are helpful in Chapter VIII (Monadic Recursion Schemes) and in the proof of Theorem 3.14. For Chapter V (Correctness and Program Verification) it is useful to know the basic notation and ideas of the first order predicate calculus a highly abbreviated version of this material appears as Appendix A. 

The alert reader will object that we are dealing with problems that are unsolvable in full generality and this of course is true. We shall see how often we do indeed end in the "Turing swamp" of undecidable properties. However, the hope is that in applications of interest we can try to skirt the swamp and concentrate on what can be done - and in particular what can. be achieved using heuristic methods or interactive systems. 

We shall study the question of the strong equivalence of flowcharts at length, and in particular examine when the strong equivalence problem is decidable. We shall see that in the general case it is undecidable and not even partially... 

Since it is undecidable whether a particular statement can ever be reached in any computation under any interpretation for any input, this condition will be undecidable and thus in our view undesirable. We prefer definitions to be effective, particularly definitions of the basic object under discussion. So this problem is avoided either by using the condition we have given which obviously implies the alternative one, or by always assuming all variables to be input variables, which shortcuts the whole problem. 

Unfortunately, "ffeeness" is not itself a decidable property. This is the first undecidability result we encounter. The proof employs the Post Correspondence Problem. 

THEOREM 3.15 For 1 > 2, it is undecidable whether the Post Correspondence Problem has a solution. 

Now we want to show that given a pair (A,B) of lists over a two symbol alphabet, say a,b, we can effectively construct a scheme P(A,B) such that P(A,B) is free if and only if the Correspondence Problem for (A,B) has NO solution. It will then follow that freeness is undecidable. For it if were decidable whether a scheme is free, then we could decide the Correspondence Problem as follows Given (A,B), construct P(A,B), turn on the machine which decides whether P(A,B) is free if P(A,B) is free print the answer NO - (A,B) has no... 

THEOREM 3.16 It is undecidable whether a program scheme is free. 

THEOREM 3.17 It is undecidable whether there is a free scheme which is strongly equivalent to a given scheme. 

There is no way to change undecidable properties to decidable properties without a loss of power of expression. So that sort of consideration cannot be an argument for or against the use of any particular canonical form. However, when the property happens to be decidable in general or for a particular subclass, use of a particular format may make life easier. Further, although WILE schemes form a canonical form for the whole class of schemes, they do not do so for many subclasses. That is, If we have a canonical transformation... 

This corollary is the starting point for most of our proofs of undecidability. The general strategy will be to show that a property P of schemes is not partially decidable by finding an algorithm to transform each scheme S into a two-tape oneway deterministic finite state acceptor M(S) such that L (M(S)) O D = if and... 

We shall show our undecidability results for monadic schemes with one function letter, one predicate letter and two program variables. Let Sn be the family of all schemes with ... 

Now it is clear that given an infinite binary tape t there is a free interpretation on Sn for which t - t (x). The schemes in Sn that we shall use to establish our undecidability results will actually test only expressions of the farm f Vx) far m > 2 and so for all purposes a tape t can be considered to correspond to a "unique" (unique as far as concerns operation of the schemes in question) free interpretation I such that... 

Now let us see some of the implications of these undecidability results. Perhaps the most important is that neither " P strongly equivalent to Q " nor " P is not strongly equivalent to Q " is partially decidable. This is why we could claim as we did that there is no point in giving a large list of elementary equivalence preserving transformations - either global or local - since no such list could be complete and result in ultimately establishing all possible equivalences. 

THEOREM 6.13 The following problems are undecidable for programs (P,I) where P is a monadic flowchart with three program variables and I is any interpretation over the natural numbers allowing x+1, x i 1, x = 0 and the constant 0. 

What does all this mean in a practical way Certainly we have no intention of writing programs for all partially computable functions indeed time and space considerations do not allow execution of all partially computable functions. The functions actually computed form a very small subset of the primitive recursive functions. We do not know, however, whether they fall into a class for which partial correctness is partially decidable one suspects not. In any case, since we obtain our undecidability results for programs with very simple structure, there can be nothing in the structure of "real" programs which will allow us by and of itself to conclude that the properties of interest are at least partially decidable. 

The undecidability results do not say that a task is always impossible - just that no program can be written to perform the task properly in all cases. But programs could be written to handle special cases. Thus we cannot completely mechanize the verification procedure so it will succeed eventually whenever it should succeed. We can of course verify particular programs and we can improve the verification procedure and increase the set of cases where it will work. As a practical matter, complexity questions will probably swamp one first - classes of programs for which verification is possible but it simply takes too long. 

It is undecidable whether a recursion scheme is translatable into a flowchart scheme. 

---