Decidability and undecidability in cellular automata

We survey results on decidability questions concerning cellular automata. Properties discussed include reversibility and surjectivity and their variants, time-symmetry and conservation laws, nilpotency and other properties of the limit set and the trace, properties chaoticity related such as sensitivity to initial conditions and mixing of the space, and dynamics from finite initial configurations. We also discuss briefly the tiling problem and its variants, and consider the influence of the dimension of the space on the decidability status of the questions.     

Quantum Hypercomputability?

A recent proposal to solve the halting problem with the quantum adiabatic algorithm is criticized and found wanting. Contrary to other physical hypercomputers, where one believes that a physical process “computes” a (recursive-theoretic) non-computable function simply because one believes the physical theory that presumably governs or describes such process, believing the theory (i.e., quantum mechanics) in the case of the quantum adiabatic “hypercomputer” is tantamount to acknowledging that the hypercomputer cannot perform its task.     

Undecidability in the Imitation Game

This paper considers undecidability in the imitation game, the so-called Turing Test. In the Turing Test, a human, a machine, and an interrogator are the players of the game. In our model of the Turing Test, the machine and the interrogator are formalized as Turing machines, allowing us to derive several impossibility results concerning the capabilities of the interrogator. The key issue is that the validity of the Turing test is not attributed to the capability of human or machine, but rather to the capability of the interrogator. In particular, it is shown that no Turing machine can be a perfect interrogator. We also discuss meta-imitation game and imitation game with analog interfaces where both the imitator and the interrogator are mimicked by continuous dynamical systems.     

Alan Turing and the Mathematical Objection

This paper concerns Alan Turing's ideas about machines, mathematical methods of proof, and intelligence. By the late 1930s, Kurt Gödel and other logicians, including Turing himself, had shown that no finite set of rules could be used to generate all true mathematical statements. Yet according to Turing, there was no upper bound to the number of mathematical truths provable by intelligent human beings, for they could invent new rules and methods of proof. So, the output of a human mathematician, for Turing, was not a computable sequence (i.e., one that could be generated by a Turing machine). Since computers only contained a finite number of instructions (or programs), one might argue, they could not reproduce human intelligence. Turing called this the ``mathematical objection' to his view that machines can think. Logico-mathematical reasons, stemming from his own work, helped to convince Turing that it should be possible to reproduce human intelligence, and eventually compete with it, by developing the appropriate kind of digital computer. He felt it should be possible to program a computer so that it could learn or discover new rules, overcoming the limitations imposed by the incompleteness and undecidability results in the same way that human mathematicians presumably do.     

Some Undecidable Approximations of TRSs

In this paper we study the decidability of reachability, normalisation, and neededness in n-shallow and n-growing TRSs. In an n-growing TRS, a variable that occurs both on the left- and right-hand side of a rewrite rule must be at depth n on the left-hand side and at depth greater than n on the right-hand side. In an n-shallow TRS, a variable that occurs both on the left- and right-hand side of a rewrite rule must be at depth n on both sides.The n-growing and n-shallow TRSs are generalisations of the growing and shallow TRSs as introduced by Jacquemard and Comon. For both shallow and growing TRSs reachability, normalisation, and (in the orthogonal case) neededness are decidable. However, as we show, these results do not generalise to n-growing and n-shallow TRSs. Consequently, no algorithm exists that performs a needed reduction strategy in n-growing or n-shallow TRSs.     

Some Undecidable Problems on Approximability of NP Optimization Problems

'1IntroductionManydecisionproblemsareNPcompleteandtheirassociatedoptimizationproblemsareNPequivalent.ButtheseoptimizationproblemshaveverydifferentaPprokimabilities.Forexample,knapsackproblemhasapolynomial-timeapproki-mationscheme,whileTSPisnotconstall-aPprotimable,unlessP=NP.WhatmakesdifferenceamongNPoptimizationproblems(NPOPs)?In[3],KolaitisandThakurinvestigatedtheapprokimabilityofNPOPsbymeansofrepresentingNPOPswithfirst-orderselltences-TheyprovedthatifP/NP,thenitisanundecidable…     

Exposure to deadlock for communicating processes is hard to detect

It is shown that the applicability of global state analysis as a tool for proving correctness of communication protocols is limited. Brand and Zafiropulo (1983) showed that reachability of global deadlock states for protocols with unbounded FIFO channels is undecidable. It is shown that the same is true for unbounded non-FIFO channels. For bounded FIFO channels the problem is shown to be PSPACE-hard.