Computability

In this paper we show how to define a halting decidability decider that rejects all finite string Turing machine descriptions that would otherwise make halting undecidable. All of the conventional halting problem proof counter-examples would be rejected on the basis that they specify an infinitely recursive evaluation sequence thus are malformed expressions of the language of Turing Machine descriptions.

In this paper I address the question of whether the incompleteness theorems imply that “the mind cannot be mechanized,” where this is understood in the specific sense that “the mathematical outputs of the idealized human mind do not coincide with the mathematical outputs of any idealized finite machine.” Gödel argued that his incompleteness theorems implied a weaker, disjunctive conclusion to the effect that either “the mind cannot be mechanized” or “mathematical truth outstrips the idealized human mind.” Others, most notably, Lucas (...) and Penrose, have claimed more—they have claimed that the incompleteness theorems actually imply the first disjunct. I will show that by sharpening the fundamental concepts involved and articulating the background assumptions governing them, one can prove Gödel’s disjunction, one can show that the arguments of Lucas and Penrose fail, and one can see what likely led proponents of the first disjunct astray. (shrink)

In this paper we consider three potential simplifications to a result of Solovay’s concerning the Turing degrees of nonstandard models of arbitrary completions of first-order Peano Arithmetic (PA). Solovay characterized the degrees of nonstandard models of completions T of PA, showing that they are the degrees of sets X such that there is an enumeration R ≤T X of an “appropriate” Scott set and there is a family of functions (tn)n∈ω, ∆0 n(X) uniformly in n, such that lim tn(s) s→∞.

If there truly is a proof that shows that no universal halt decider exists on the basis that certain tuples: (H, Wm, W) are undecidable, then this very same proof (implemented as a Turing machine) could be used by H to reject some of its inputs. When-so-ever the hypothetical halt decider cannot derive a formal proof from its input strings and initial state to final states corresponding the mathematical logic functions of Halts(Wm, W) or Loops(Wm, W), halting undecidability has been (...) decided. (shrink)

When we understand that every potential halt decider must derive a formal mathematical proof from its inputs to its final states previously undiscovered semantic details emerge. -/- When-so-ever the potential halt decider cannot derive a formal proof from its input strings to its final states of Halts or Loops, undecidability has been decided. -/- The formal proof involves tracing the sequence of state transitions of the input TMD as syntactic logical consequence inference steps in the formal language of Turing Machine (...) Descriptions. (shrink)

Let \Gamma_{n} denote (k-1)!, where n \in {3,...,16} and k \in {2} \cup [2^{2^{n-3}}+1,\infty) \cap N. For an integer n \in {3,...,16}, let \Sigma_n denote the following statement: if a system of equations S \subseteq {\Gamma_{n}(x_i)=x_k: i,k \in {1,...,n}} \cup {x_i \cdot x_j=x_k: i,j,k \in {1,...,n}} with Gamma instead of \Gamma_n has only finitely many solutions in positive integers x_1,...,x_n, then every tuple (x_1,...,x_n) \in (N\{0})^n that solves the original system S satisfies x_1,...,x_n \leq 2^{2^{n-2}}. Our hypothesis claims that the (...) statements \Sigma_{3},...,\Sigma_{16} are true. The statement \Sigma_6 proves the following implication: if the equation x(x+1)=y! has only finitely many solutions in positive integers x and y, then each such solution (x,y) belongs to the set {(1,2),(2,3)}. The statement \Sigma_6 proves the following implication: if the equation x!+1=y^2 has only finitely many solutions in positive integers x and y, then each such solution (x,y) belongs to the set {(4,5), (5,11), (7,71)}. The statement \Sigma_9 implies the infinitude of primes of the form n^2+1. The statement \Sigma_9 implies that any prime of the form n!+1 with n \geq 2^{2^{9-3}} proves the infinitude of primes of the form n!+1. The statement \Sigma_{14} implies the infinitude of twin primes. The statement \Sigma_{16} implies the infinitude of Sophie Germain primes. A modified statement \Sigma_7 implies the infinitude of Wilson primes. (shrink)

Turing’s analysis of computability has recently been challenged; it is claimed that it is circular to analyse the intuitive concept of numerical computability in terms of the Turing machine. This claim threatens the view, canonical in mathematics and cognitive science, that the concept of a systematic procedure or algorithm is to be explicated by reference to the capacities of Turing machines. We defend Turing’s analysis against the challenge of ‘deviant encodings’.Keywords: Systematic procedure; Turing machine; Church–Turing thesis; Deviant encoding; Acceptable encoding; (...) Turing’s analysis of computability; Turing’s Notational Thesis. (shrink)

Many cognitive scientists, having discovered that some computational-level characterization f of a cognitive capacity φ is intractable, invoke heuristics as algorithmic-level explanations of how cognizers compute f. We argue that such explanations are actually dysfunctional, and rebut five possible objections. We then propose computational-level theory revision as a principled and workable alternative.

A simple inductive argument shows natural languages to have infinitly many sentences, but workers in the field have uncovered clear evidence of a diverse group of ‘exceptional’ languages from Proto-Uralic to Dyirbal and most recently, Pirahã, that appear to lack recursive devices entirely. We argue that in an information-theoretic setting non-recursive natural languages appear neither exceptional nor functionally inferior to the recursive majority.

In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure λ, a choice needs to be made. One approach is to allow randomness tests to access the measure λ as an oracle . The other approach is the opposite one, where the randomness tests are completely effective and do not have access to the information contained in λ . While the Hippocratic approach is in general much more restrictive, there are cases where the (...) two coincide. The first author showed in 2010 that in the particular case where the notion of randomness considered is Martin-Löf randomness and the measure λ is a Bernoulli measure, classical randomness and Hippocratic randomness coincide. In this paper, we prove that this result no longer holds for other notions of randomness, namely computable randomness and stochasticity. (shrink)

We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.

Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth-table Schnorr randomness and truth-table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth-table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's (...) Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth-table Schnorr randomness. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

A real x is -Kurtz random if it is in no closed null set . We show that there is a cone of -Kurtz random hyperdegrees. We characterize lowness for -Kurtz randomness as being -dominated and -semi-traceable.

We generalize standard Turing machines, which work in time ω on a tape of length ω, to α-machines with time α and tape length α, for α some limit ordinal. We show that this provides a simple machine model adequate for classical admissible recursion theory as developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-recursive or α-recursively enumerable are equivalent to being computable or computably enumerable by an α-machine, respectively. We emphasize the (...) algorithmic approach to admissible recursion theory by indicating how the proof of the Sacks–Simpson theorem, i.e., the solution of Post’s problem in α-recursion theory, could be based on α-machines, without involving constructibility theory. (shrink)

A central object of study in the field of algorithmic randomness are notions of randomness for sequences, i.e., infinite sequences of zeros and ones. These notions are usually defined with respect to the uniform measure on the set of all sequences, but extend canonically to other computable probability measures. This way each notion of randomness induces an equivalence relation on the computable probability measures where two measures are equivalent if they have the same set of random sequences. In what follows, (...) we study the equivalence relations induced by Martin-Löf randomness, computable randomness, Schnorr randomness and Kurtz randomness, together with the relations of equivalence and consistency from probability theory. We show that all these relations coincide when restricted to the class of computable strongly positive generalized Bernoulli measures. For the case of arbitrary computable measures, we obtain a complete and somewhat surprising picture of the implications between these relations that hold in general. (shrink)

We show that if a real x2ω is strongly Hausdorff -random, where h is a dimension function corresponding to a convex order, then it is also random for a continuous probability measure μ such that the μ-measure of the basic open cylinders shrinks according to h. The proof uses a new method to construct measures, based on effective continuous transformations and a basis theorem for -classes applied to closed sets of probability measures. We use the main result to derive a (...) collapse of randomness notions for Hausdorff measures, and to provide a characterization of effective Hausdorff dimension similar to Frostman’s Theorem. (shrink)

This paper initiates the study of sets in Euclidean spaces ℝn that are defined in terms of the dimensions of their elements. Specifically, given an interval I ⊆ [0, n ], we are interested in the connectivity properties of the set DIMI, consisting of all points in ℝn whose dimensions lie in I, and of its dual DIMIstr, consisting of all points whose strong dimensions lie in I. If I is [0, 1) or.

The category of Scott-domains gives a computability theory for possibly uncountable topological spaces, via representations. In particular, every separable Banach-space is representable over a separable domain. A large class of topological spaces, including all Banach-spaces, is representable by domains, and in domain theory, there is a well-understood notion of parametrizations over a domain. We explore the link with parameter-dependent collections of spaces in e. g. functional analysis through a case study of "Lp" -spaces. We show that a well-known domain representation (...) of "Lp" as a metric space can be made uniform in the sense of parametrizations of domains. The uniform representations admit lifting of continuous functions and are effective in p. Dependent type constructions apply, and through the study of the sum and product spaces, we clarify the notions of uniformity and uniform computability. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

We show that there exists a real α such that, for all reals β, if α is linear reducible to β then β≤Tα. In fact, every random real satisfies this quasi-maximality property. As a corollary we may conclude that there exists no ℓ-complete Δ2 real. Upon realizing that quasi-maximality does not characterize the random reals–there exist reals which are not random but which are of quasi-maximal ℓ-degree–it is then natural to ask whether maximality could provide such a characterization. Such hopes, (...) however, are in vain since no real is of maximal ℓ-degree. (shrink)

An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our first (...) main result states that KL-random sequences are close to Martin-Löf random sequences in so far as every KL-random sequence has arbitrarily dense subsequences that are Martin-Löf random. A key lemma in the proof of this result is that for every effective split of a KL-random sequence at least one of the halves is Martin-Löf random. However, this splitting property does not characterize KL-randomness; we construct a sequence that is not even computably random such that every effective split yields two subsequences that are 2-random. Furthermore, we show for any KL-random sequence A that is computable in the halting problem that, first, for any effective split of A both halves are Martin-Löf random and, second, for any computable, nondecreasing, and unbounded function g and almost all n, the prefix of A of length n has prefix-free Kolmogorov complexity at least n−g. Again, the latter property does not characterize KL-randomness, even when restricted to left-r.e. sequences; we construct a left-r.e. sequence that has this property but is not KL-stochastic and, in fact, is not even Mises–Wald–Church stochastic.Turning our attention to KL-stochasticity, we construct a non-empty class of KL-stochastic sequences that are not weakly 1-random; by the usual basis theorems we obtain such sequences that in addition are left-r.e., are low, or are of hyperimmune-free degree.Our second main result asserts that every KL-stochastic sequence has effective dimension 1, or equivalently, a sequence cannot be KL-stochastic if it has infinitely many prefixes that can be compressed by a factor of α<1. This improves on a result by Muchnik, who has shown that were they to exist, such compressible prefixes could not be found effectively. (shrink)

This paper is a sequel to our [7]. In that paper we constructed a Π1 0 tree of avoidable points. Here we construct a Π1 0 tree of shadow points. This tree is a tree of sharp filters, where a sharp filter is a nested sequence of basic open sets converging to a point. In the construction we assign to each basic open set on the tree an address in 2<ω. One interesting fact is that while our Π1 0 tree (...) of sharp filters (a subtree of Δ<ω) is isomorphic to the tree of addresses (a subtree of 2<ω), the tree of addresses is recursively enumerable but not recursive. To achieve this end we use a finite injury priority argument. (shrink)

Let I be a quasimaximal subset of a computable basis of the fully efective vector space V ∞ . We give a necessary and sufficient condition for the existence of an isomorphism between the principal filter respectivelly. We construct both quasimaximal sets that satisfy and quasimaximal sets that do not satisfy this condition. With the latter we obtain a negative answer to Question 5.4 posed by Downey and Remmel in [3].

The computational complexity of finding a shortest path in a two-dimensional domain is studied in the Turing machine-based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial-time computable two-dimensional domains: domains with polynomialtime computable boundaries, and polynomial-time recognizable domains with polynomial-time computable distance functions. It is proved that the shortest path problem has the polynomial-space upper bound for domains of both type and type ; and it has a polynomial-space lower (...) bound for the domains of type , and has a #P lower bound for the domains of type. (shrink)

We show that any partial order with a Σ3 enumeration can be effectively embedded into any partial order obtained by imposing a strong reducibility such as ≤tt on the c. e. sets. As a consequence, we obtain that the partial orders that result from imposing a strong reducibility on the sets in a level of the Ershov hiearchy below ω + 1 are co-embeddable.

The property of admissibility of representations plays an important role in Type–2 Theory of Effectivity . TTE defines computability on sets with continuum cardinality via representations. Admissibility is known to be indispensable for guaranteeing reasonable effectivity properties of the used representations.The question arises whether every function that is computable with respect to arbritrary representations is also computable with respect to closely related admissible ones. We define three operators which transform representations into admissible ones in such a way that relative computability (...) of functions is preserved. Thus the use of admissible representations rather than of non–admissible ones does not decrease the class of relatively computable functions. (shrink)

The paper builds on a simply typed term system ${\cal PR}^\omega $ providing a notion of partial primitive recursive functional on arbitrary Scott domains $D_\sigma$ that includes a suitable concept of parallelism. Computability on the partial continuous functionals seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (SCVR) is not reducible to partial primitive recursion. So an extension ${\cal PR}^{\omega e}$ is studied that is closed under SCVR and yet stays within the realm of subrecursiveness. The twist (...) are certain type 1 Gödel recursors ${\cal R}_k$ for simultaneous partial primitive recursion. Formally, the value ${\cal R}_k\vec{g}\vec{H} x i$ is a function $f_i$ of type $\iota \to \iota$ , however, ${\cal R}_k$ is modelled such that $f_i$ is a finite element of $D_{\iota\to\iota}$ or in other words, a partial sequence. It is shown that the Ackermann function is not definable in ${\cal PR}^{\omega e}$. (shrink)

Review by: Johanna N. Y. Franklin The Bulletin of Symbolic Logic, Volume 19, Issue 1, Page 115-118, March 2013.

Elvira Mayordomo and Wolfgang Merkle The Bulletin of Symbolic Logic, Volume 19, Issue 1, Page 135-136, March 2013.