# Infinite Sequences and Halting Problem. Thought of the Day 76.0

In attempting to extend the notion of depth from finite strings to infinite sequences, one encounters a familiar phenomenon: the definitions become sharper (e.g. recursively invariant), but their intuitive meaning is less clear, because of distinctions (e.g. between infintely-often and almost-everywhere properties) that do not exist in the finite case.

An infinite sequence X is called strongly deep if at every significance level s, and for every recursive function f, all but finitely many initial segments Xn have depth exceeding f(n).

It is necessary to require the initial segments to be deep almost everywhere rather than infinitely often, because even the most trivial sequence has infinitely many deep initial segments Xn (viz. the segments whose lengths n are deep numbers).

It is not difficult to show that the property of strong depth is invariant under truth-table equivalence (this is the same as Turing equivalence in recursively bounded time, or via a total recursive operator), and that the same notion would result if the initial segments were required to be deep in the sense of receiving less than 2−s of their algorithmic probability from f(n)-fast programs. The characteristic sequence of the halting set K is an example of a strongly deep sequence.

A weaker definition of depth, also invariant under truth-table equivalence, is perhaps more analogous to that adopted for finite strings:

An infinite sequence X is weakly deep if it is not computable in recursively bounded time from any algorithmically random infinite sequence.

Computability in recursively bounded time is equivalent to two other properties, viz. truth-table reducibility and reducibility via a total recursive operator.

By contrast to the situation with truth-table reducibility, Péter Gacs has shown that every sequence is computable from (i.e. Turing reducible to) an algorithmically random sequence if no bound is imposed on the time. This is the infinite analog of far more obvious fact that every finite string is computable from an algorithmically random string (e.g. its minimal program).

Every strongly deep sequence is weakly deep, but by intermittently padding K with large blocks of zeros, one can construct a weakly deep sequence with infinitely many shallow initial segments.

Truth table reducibility to an algorithmically random sequence is equivalent to the property studied by Levin et. al. of being random with respect to some recursive measure. Levin calls sequences with this property “proper” or “complete” sequences, and views them as more realistic and interesting than other sequences because they are the typical outcomes of probabilistic or deterministic effective processes operating in recursively bounded time.

Weakly deep sequences arise with finite probability when a universal Turing machine (with one-way input and output tapes, so that it can act as a transducer of infinite sequences) is given an infinite coin toss sequence for input. These sequences are necessarily produced very slowly: the time to output the n’th digit being bounded by no recursive function, and the output sequence contains evidence of this slowness. Because they are produced with finite probability, such sequences can contain only finite information about the halting problem.

# Roger Penrose and Artificial Intelligence: Revenance from the Archives and the Archaic.

Let us have a look at Penrose and his criticisms of strong AI, and does he come out as a winner. His Emperor’s New Mind: Concerning Computers, Minds, and The Laws of Physics

sets out to deal a death blow to the project of strong AI. Even while showing humility, like in saying,

My point of view is an unconventional among physicists and is consequently one which is unlikely to be adopted, at present, by computer scientists or physiologists,

he is merely stressing on his speculative musings. Penrosian arguments ala Searle, are definitely opinionated, in making assertions like a conscious mind cannot work like a computer. He grants the possibility of artificial machines coming into existence, and even superseding humans (1), but at every moment remains convinced that algorithmic machines are doomed to subservience. Penrose’s arguments proceed through showing that human intelligence cannot be implemented by any Turing machine equivalent computer, and human mind as not algorithmically based that could capture the Turing machine equivalent. He is even sympathetic to Searle’s Chinese Room argument, despite showing some reservations against its conclusions.

The speculative nature of his arguments question people as devices which compute that a Turing machine cannot, despite physical laws that allow such a construction of a device as a difficult venture. This is where his quantum theory sets in, with U and R (Unitary process and Reduction process respectively) acting on quantum states that help describe a quantum system. His U and R processes and the states they act upon are not only independent of observers, but at the same time real, thus branding him as a realist. What happens is an interpolation that occurs between Unitary Process and Reductive Process, a new procedure that essentially contains a non-algorithmic element takes shape, which effectuates a future that cannot be computable based on the present, even though it could be determined that way. This radically new concept which is applied to space-time is mapped onto the depths of brain’s structure, and for Penrose, the speculative possibility occurs in what he terms the Phenomenon of Brain Plasticity. As he says,

Somewhere within the depths of the brain, as yet unknown cells are to be found of single quantum sensitivity, such that synapses becoming activate or deactivated through the growth of contraction of dendritic spines…could be governed by something like the processes involved in quasi-crystal growth. Thus, not just one of the possible alternative arrangements is tried out, but vast numbers, all superposed in complex linear superposition.

From the above, it is deduced that the impact is only on the conscious mind, whereas the unconscious mind is left to do with algorithmic computationality. Why is this important for Penrose is, since, as a mathematician believes in the mathematical ideas as populating an ideal Platonic world, and which in turn is accessible only via the intellect. And harking back to the non-locality principle within quantum theory, it is clear that true intellect requires consciousness, and the mathematician’s conscious mind has a direct route to truth. In the meanwhile, there is a position in “many-worlds” (2) view that supersedes Penrose’s quantum realist one. This position rejects the Reduction Process in favor of Unitary Process, by terming the former as a mere illusion. Penrose shows his reservations against this view, as for him, a theory of consciousness needs to be in place prior to “many-worlds” view, and before the latter view could be squared with what one actually observes. Penrose is quite amazed at how many AI reviewers and researchers embrace the “many-worlds” hypothesis, and mocks at them, for their reasons being better supportive of validating AI project. In short, Penrose’s criticism of strong AI is based on the project’s assertion that consciousness can emerge by a complex system of algorithms, whereas for the thinker, a great many things humans involve in are intrinsically non-algorithmic in nature. For Penrose, a system can be deterministic without being algorithmic. He even uses the Turing’s halting theorem (3) to demonstrate the possibility of replication of consciousness. In a public lecture in Kolkata on the 4th of January 2011 (4), Penrose had this to say,

There are many things in Physics which are yet unknown. Unless we unravel them, we cannot think of creating real artificial intelligence. It cannot be achieved through the present system of computing which is based on mathematical algorithm. We need to be able to replicate human consciousness, which, I believe, is possible through physics and quantum mechanics. The good news is that recent experiments indicate that it is possible.

There is an apparent shift in Penrosean ideas via what he calls “correct quantum gravity”, which argues for the rational processes of the mind to be completely algorithmic and probably standing a bright chance to be duplicated by a sufficiently complex computing system. As he quoted from the same lecture in Kolkata,

A few years back, scientists at NASA had contemplated sending intelligent robots to space and sought my inputs. Even though we are still unable to create some device with genuine feelings and understanding, the question remains a disturbing one. Is it ethical to leave a machine which has consciousness in some faraway planet or in space? Honestly, we haven’t reached that stage yet. Having said that, I must add it may not be too far away, either. It is certainly a possibility.

Penrose does meet up with some sympathizers for his view, but his fellow-travelers do not tread along with him for a long distance. For example, in an interview with Sander Olson, Vernor Vinge, despite showing some reluctance to Penrose’s position, accepts that physical aspects of mind, or especially the quantum effects have not been studied in greater detail, but these quantum effects would simply be another thing to be learned with artifacts. Vinge does speculate on other paradigms that could be equally utilized for AI research hitting speed, rather than confining oneself to computer departments to bank on their progress. His speculations (5) have some parallel to what Penrose and Searle would hint at, albeit occasionally. Most of the work in AI could benefit, if AI, neural nets are closely connected to biological life. Rather than banking upon modeling and understanding of biological life with computers, if composite systems relying on biological life for guidance, or for providing features we do not understand quite well as yet to be implemented within the hardware, could be fathomed and made a reality, the program of AI would undoubtedly push the pedal to accelerate. There would probably be no disagreeing with what Aaron Saenz, Senior Editor of singularityhub.com said (6),

Artificial General Intelligence is one of the Holy Grails of science because it is almost mythical in its promise: not a system that simply learns, but one that reaches and exceeds our own kind of intelligence. A truly new form of advanced life. There are many brilliant people trying to find it. Each of these AI researchers have their own approach, their own expectations and their own history of failures and a precious few successes. The products you see on the market today are narrow AI-machines that have very limited ability to learn. As Scott Brown said, “today’s I technology is so primitive that much of the cleverness goes towards inventing business models that do not require good algorithms to succeed.” We’re in the infantile stages of AI. If that. Maybe the fetal stages.

(1) This is quite apocalyptic sounding like the singularity notion of Ray Kurzweil, which is an extremely disruptive, world-altering event that has the potentiality of forever changing the course of human history. The extermination of humanity by violent machines is not impossible, since there would be no sharp distinctions between men and machines due to the existence of cybernetically enhanced humans and uploaded humans.

(2) “Many-worlds” view was first put forward by Hugh Everett in 1957. According to this view, evolution of state vector regarded realistically, is always governed by deterministic Unitary Process, while Reduction Process remains totally absent from such an evolutionary process. The interesting ramifications of this view are putting conscious observers at the center of the considerations, thus proving the basic assumption that quantum states corresponding to distinct conscious experiences have to be orthogonal (Simon 2009). On the technical side, ‘Orthogonal’ according to quantum mechanics is: two eigenstates of a Hermitian operator, ψm and ψn, are orthogonal if they correspond to different eigenvalues. This means, in Dirac notation, that < ψm | ψn > = 0 unless ψm and ψn correspond to the same eigenvalue. This follows from the fact that Schrödinger’s equation is a Sturm–Liouville equation (in Schrödinger’s formulation) or that observables are given by hermitian operators (in Heisenberg’s formulation).

(3) Halting problem is a decisional problem in computability theory, and is stated as: Given a description of a program, decide whether the program finishes running or continues to run, and will thereby run forever. Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. In a way, the halting problem is undecidable over Turing machines.

(4) Penrose, R. AI may soon become reality. Public lecture delivered in Kolkata on the 4th of Jan 2011. <http://timesofindia.indiatimes.com/city/kolkata-/AI-may-soon-become-reality- Penrose/articleshow/7219700.cms>

(5) Olson, S. Interview with Vernor Vinge in Nanotech.Biz <http://www.nanotech.biz/i.php?id=01_16_09&gt;

(6) Saenz, A. Will Vicarious Systems’ Silicon Valley Pedigree Help it Build AI? in singularityhub.com <http://singularityhub.com/2011/02/03/will-vicarious-systems-silicon-valley-pedigree-help-it-build-agi/&gt;