[PCE and Intermediate Degrees of Computability] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1

PCE and Intermediate Degrees of Computability
(Click here to view the original thread with full colors/images)

Posted by: Matthew Szudzik

Above all else, Stephen Wolfram's NKS is an attempt to provide a conceptual framework for scientific theories in which algorithms and computations are used to describe phenomena, rather than differential equations and other traditional forms of mathematical description. But there still remain many unanswered questions about the formulation of science in purely computational terms. For example, how does the existence of intermediate degrees of computability affect Wolfram's Principle of Computational Equivalence?

The Principle of Computation Equivalence states that "almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication" [pages 716-717 of NKS], where computational universality is understood to be "the highest level of computational sophistication" [page 717 of NKS]. Wolfram arrived at this principle empirically after performing many computational experiments, but what exactly does it mean? In particular, what constitutes a "process", and how does one judge whether or not "almost all" processes obey the principle?

A common attempt that a mathematically-minded individual might make at defining what is meant by a "process" is the following:

Attempted Definition: A "process" is a mathematical function (possibly undefined for some inputs) computed by an algorithm.

Thus, this attempted definition identifies the concept of "process" with the technical notion of a partially computable (i.e. partial recursive) function [see page 18 of Hartley Rogers' Theory of Recursive Functions and Effective Computability]. But this definition clearly does not agree with the Principle of Computational Equivalence. For example, consider any computationally universal function U. Now, consider the function f computed by the following algorithm.

f[x_] := (U[x];1)

Note that f[x] first computes U[x], and then discards the output of U[x], outputting 1 instead. But U[x] is not defined for all inputs x because it is computationally universal, and so f[x] will not be defined for all inputs either. Indeed, the set of inputs x for which U[x] is defined is called the halting set of U, and the halting set of any computationally universal function is known to be so complicated as to be formally non-computable (i.e. it is not a recursive set). The function f has the same non-computable halting set as U, and so we may conclude that f is "not obviously simple"--it exhibits the same sort of computational undecidability that U possesses. The Principle of Computational Equivalence then immediately implies (assuming that functions like f are common enough not to be excluded by the "almost all" proviso) that f is computationally universal. But this is clearly not true, for although the function f has a complicated domain of inputs on which it is defined, when f[x] is defined, it always outputs 1, and therefore can never be used to perform universal computation.

Clearly, the attempted definition above does not accurately capture the concept of "process" that is used by Wolfram. Indeed, the problem is that a mathematical function f is determined only by its input and output, without regard for the actual computation that might be required to produce the output. The computation that f[x] is actually performing, of course, does involve universal computation, since it explicitly calls U[x]. So, the definition of a "process" should take into account not only the input and output of a function, but also the particular sub-computations that are used to compute the output from the input. If a process involves sub-computations that are computationally universal, then that process is to be considered universal.

As far as I know, the idea of classifying functions according to their sub-computations is entirely original to Wolfram--it does not seem to correspond to any of the usual reducibilities studied in the theory of computation, for example. It is difficult to even formalize the concept. Does it depend on which programming language we use to express our algorithms? How does one know whether or not a Turing Machine, for example, is performing computationally universal sub-computations?

The question of how to define "sub-computation" is certainly non-trivial, and some individuals might wonder whether it is possible to provide a counter-example to the Principle of Computational Equivalence that entirely avoids the issue of defining "sub-computation". Occasionally, I have heard the claim that intermediate degrees of computability provide exactly such a counter-example.

Note that if one had an oracle which could magically compute the halting set of a computationally universal function U, then one would be able to compute the halting set of every partially computable function. Are there partially computable functions g that have non-computable halting sets, but that are unlike any computationally universal function U in that an oracle for computing the halting set of g is not sufficient to allow one to compute the halting set of every partial recursive function? Partially computable functions g that have this property are said to have an intermediate degree of computability, since their halting sets are so complicated as to be formally non-computable, but are still not as complicated as the halting sets of computationally universal functions. So, if a partially computable function g has an intermediate degree of computability, then the halting set of g is non-computable, and there is no computationally universal function U that has the same halting set.

The question of whether or not there exist any partially computable functions with intermediate degrees of computability was first asked by Emil Post in 1944. It was not until 1956 that two individuals, Richard Friedberg and Albert Muchnik, independently constructed algorithms that possess intermediate degrees of computability. Does the existence of these or similar constructions contradict the Principle of Computational Equivalence?

Unfortunately, the question of how intermediate degrees of computability relate to the Principle of Computational Equivalence again depends on the definition of a "sub-computation". This is because every known partially computable function g that has an intermediate degree of computability contains an implicit call to a computationally universal function U. For example, a typical algorithm for g is illustrated on page 1131 of the NKS book.

http://www.wolframscience.com/nksonline/page-1130c-text

In that illustration, g[n] is said to be defined if and only if the nth cell in the left sequence running horizontally in the graphic ever becomes black. The illustration's vertical axis enumerates all possible algorithms in a particular computationally universal language (in this case, register machines). To compute U[x], for any input x, one only needs to consider the "constant function"

h[z_] := U[x]

This constant function will have a specific location in the enumeration listed on the vertical axis, and to determine the output of U[x], one only needs to watch the computation being performed in that row of the illustration.

Is it possible to construct an algorithm with an intermediate degree of computability that does not implicitly depend on an enumeration of all possible algorithms? Would such a construction still involve computationally universal "sub-computations"? These are questions that remain to be answered.

Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings