Computability

We study the logical and computational properties of basic theorems of uncountable mathematics, in particular Pincherle's theorem, published in 1882. This theorem states that a locally bounded function is bounded on certain domains, i.e. one of the first ‘local-to-global’ principles. It is well-known that such principles in analysis are intimately connected to (open-cover) compactness, but we nonetheless exhibit fundamental differences between compactness and Pincherle's theorem. For instance, the main question of Reverse Mathematics, namely which set existence axioms are necessary to (...) prove Pincherle's theorem, does not have an unique or unambiguous answer, in contrast to compactness. We establish similar differences for the computational properties of compactness and Pincherle's theorem. We establish the same differences for other local-to-global principles, even going back to Weierstrass. We also greatly sharpen the known computational power of compactness, for the most shared with Pincherle's theorem however. Finally, countable choice plays an important role in the previous, we therefore study this axiom together with the intimately related Lindelöf lemma. (shrink)

We show that there is a minimal pair in the nonuniform generic degrees, and hence also in the uniform generic degrees. This fact contrasts with Igusa’s result that there are no minimal pairs for relative generic computability and answers a basic structural question mentioned in several papers in the area.

Conditions (1)-(8) below concern sets X⊆N . (1) There are a large number of elements of X and it is conjectured that X is infinite. (2) No known algorithm decides the finiteness of X. (3) A known algorithm for every n∈N decides whether or not n∈X. (4) An explicitly known integer n satisfies: card(X)<ω ⇒ X⊆(-∞,n]. (5) X is widely known in number theory. (6) There is no known equality X = X_1 ∪ X_2, where X_1 and X_2 are defined (...) simpler than X . (7) No known set Y is defined simpler than X and satisfies (Y⊆X) ∧ (card(X\Y)<ω). (8) No known set Y is defined simpler than X and satisfies card((X\Y)∪(Y\X))<ω. We do not know any set X⊆N that satisfies conditions (1)-(4) and (5). The same is true, if condition (5) is replaced by condition (6) or (7) or (8). For every explicitly known integer n, some simply defined set X⊆N includes the set (-∞,n]∩N and satisfies conditions (1)-(4). Let P(n^2+1) denote the set of primes of the form n^2+1. The set X=P(n^2+1) satisfies conditions (1)-(3) and (5)-(8). The set X={k∈N: the number of digits of k belongs to P(n^2+1)} contains 10^{10^{450}} consecutive integers and satisfies conditions (1)-(3) and (6)-(8). Some hypothetical statement implies that these sets X satisfy condition (4). (shrink)

Eu li muitas discussões recentes sobre os limites da computação e do universo como computador, na esperança de encontrar alguns comentários sobre o trabalho surpreendente do físico polimatemático e teórico da decisão David Wolpert, mas não encontrei uma única citação e assim que eu apresento este muito breve Resumo. Wolpert provou alguma impossibilidade impressionante ou teoremas da incompletude (1992 a 2008-Veja arxiv dot org) nos limites à inferência (computação) que são tão gerais que são independentes do dispositivo que faz a (...) computação, e mesmo independente das leis da física, para que eles se apliquem em computadores, física e comportamento humano. Eles fazem uso da diagonalização de cantor, o paradoxo mentiroso e worldlines (linhas do mundo) para fornecer o que pode ser o teorema final na teoria da máquina de Turing, e, aparentemente, fornecer insights sobre a impossibilidade, incompletude, os limites da computação, e do universo como computador, em todos os universos possíveis e todos os seres ou mecanismos, gerando, entre outras coisas, um princípio de incerteza mecânica não quântica e uma prova de monoteísmo. Há umas conexões óbvias ao trabalho clássico de Chaitin, Solomonoff, Komolgarov e Wittgenstein e à noção que nenhum programa (e assim nenhum dispositivo) pode gerar uma seqüência (ou dispositivo) com maior complexidade do que possui. Pode-se dizer que este corpo de trabalho implica ateísmo, uma vez que não pode haver qualquer entidade mais complexa do que o universo físico e do ponto de vista Wittgensteiniano, ' mais complexo ' é sem sentido (não tem condições de satisfação, ou seja, criador de verdade ou teste). Mesmo um ' Deus ' (ou seja, um ' dispositivo ' com tempo ilimitado/espaço e energia) não pode determinar se um determinado ' número ' é ' aleatório ', nem encontrar uma determinada maneira de mostrar que uma determinada ' fórmula ', ' teorema ' ou ' sentença ' ou ' Device ' (todos estes sendo linguagem complexa jogos) faz parte de um determinado «sistema». Aqueles que desejam um quadro até à data detalhado para o comportamento humano da opinião moderna dos dois sistemas consultar meu livros Falando Macacos 3ª Ed (2019), A Estrutura Lógica da Filosofia, Psicologia, Mente e Linguagem em Ludwig Wittgenstein e John Searle 2a Ed (2019), Suicídio Pela Democracia,4aEd(2019), Entendendo as Conexões entre Ciência, Filosofia, Psicologia, Religião, Política e Economia Artigos e Análises 2006-2019 (2019), Ilusões Utópicas Suicidas no 21St século 5a Ed (2019), A Estrutura Lógica do Comportamento Humano (2019), e A Estrutura Lógica da Consciência (2019) y outras. (shrink)

Infinite time Turing machines represent a model of computability that extends the operations of Turing machines to transfinite ordinal time by defining the content of each cell at limit steps to be the lim sup of the sequences of previous contents of that cell. In this paper, we study a computational model obtained by replacing the lim sup rule with an ‘eventually constant’ rule: at each limit step, the value of each cell is defined if and only if the content (...) of that cell has stabilized before that limit step and is then equal to this constant value. We call these machines weak infinite time Turing machines. We study different variants of wITTMs adding multiple tapes, heads, or bidimensional tapes. We show that some of these models are equivalent to each other concerning their computational strength. We show that wITTMs decide exactly the arithmetic relations on natural numbers. (shrink)

Although Fuzzy logic and Fuzzy Mathematics is a widespread subject and there is a vast literature about it, yet the use of Fuzzy issues like Fuzzy sets and Fuzzy numbers was relatively rare in time concept. This could be seen in the Fuzzy time series. In addition, some attempts are done in fuzzing Turing Machines but seemingly there is no need to fuzzy time. Throughout this article, we try to change this picture and show why it is helpful to consider (...) the instants of time as Fuzzy numbers. In physics, though there are revolutionary ideas on the time concept like B theories in contrast to A theory also about central concepts like space, momentum… it is a long time that these concepts are changed, but time is considered classically in all well-known and established physics theories. Seemingly, we stick to the classical time concept in all fields of science and we have a vast inertia to change it. Our goal in this article is to provide some bases why it is rational and reasonable to change and modify this picture. Here, the central point is the modified version of “Unexpected Hanging” paradox as it is described in "Is classical Mathematics appropriate for theory of Computation".This modified version leads us to a contradiction and based on that it is presented there why some problems in Theory of Computation are not solved yet. To resolve the difficulties arising there, we have two choices. Either “choosing” a new type of Logic like “Para-consistent Logic” to tolerate contradiction or changing and improving the time concept and consequently to modify the “Turing Computational Model”. Throughout this paper, we select the second way for benefiting from saving some aspects of Classical Logic. In chapter 2, by applying quantum Mechanics and Schrodinger equation we compute the associated fuzzy number to time. These, provides a new interpretation of Quantum Mechanics.More exactly what we see here is "Particle-Fuzzy time" interpretation of quantum Mechanics, in contrast to some other interpretations of Quantum Mechanics like " Wave-Particle" interpretation. At the end, we propound a question about the possible solution of a paradox in Physics, the contradiction between General Relativity and Quantum Mechanics. (shrink)

Many philosophers contend that Turing’s work provides a conceptual analysis of numerical computability. In (Rescorla, 2007), I dissented. I argued that the problem of deviant notations stymies existing attempts at conceptual analysis. Copeland and Proudfoot respond to my critique. I argue that their putative solution does not succeed. We are still awaiting a genuine conceptual analysis.

In ‘Infinitism Regained’, Jeanne Peijnenburg argues for a version of infinitism wherein ‘beliefs may be justified by an infinite chain of reasons that can be actually completed’. I argue that Peijnenburg has not successfully argued for this claim, but rather has shown that certain infinite series can be computed.

El artículo formula una interpretación de la computabilidad desde la perspectiva del conceptualismo realista. En esta interpretación, la noción central es la de concepto computable, el cual se entiende como cierto tipo de capacidad cognitiva. Aquí se muestra cómo difiere esa interpretación conceptualista de la clásica, denominada teoría de la computabilidad efectiva, en la cual el concepto fundamental es el de algoritmo; también se discute la relación entre estas dos interpretaciones. La discusión explora las consecuencias de la idea de que (...) los contenidos de los conceptos computables se pueden expresar en algoritmos. En un apéndice se plantean, muy brevemente, las diferencias entre el enfoque conceptualista de la computabilidad y otros dos enfoques no clásicos: el intuicionista y el representacionista./// This paper formulates an interpretaron of computability from the perspective of realist conceptualism. The key notion within this theory is that of a computable concept, where a concept is a cognitive capacity of a certain sort. Differences and connections between the conceptualist interpretation and the classical one, customarily referred to as the theory of effective computability, for which the key concept is that of an algoríthm, are shown in the text. Consequences of the idea that the content of computable concepts can be expressed in algoríthms are explored. An appendix briefly outlines how the present conceptualist approach differs from two other non-classical interpretations of computability, the intuitionist and the representationist. (shrink)

We show that to every recursive total continuous functional $\Phi$ there is a PCF-definable representative $\Psi$ of $\Phi$ in the hierarchy of partial continuous functionals, where PCF is Plotkin's programming language for computable functionals. PCF-definable is equivalent to Kleene's S1-S9-computable over the partial continuous functionals.

Yuri Matiyasevich's theorem states that the set of all Diophantine equations which have a solution in non-negative integers is not recursive. Craig Smoryński's theorem states that the set of all Diophantine equations which have at most finitely many solutions in non-negative integers is not recursively enumerable. Let R be a subring of Q with or without 1. By H_{10}(R), we denote the problem of whether there exists an algorithm which for any given Diophantine equation with integer coefficients, can decide whether (...) or not the equation has a solution in R. We prove that a positive solution to H_{10}(R) implies that the set of all Diophantine equations with a finite number of solutions in R is recursively enumerable. We show the converse implication for every infinite set R \subseteq Q such that there exist computable functions \tau_1,\tau_2:N \to Z which satisfy (\forall n \in N \tau_2(n) \neq 0) \wedge ({\frac{\tau_1(n)}{\tau_2(n)}: n \in N}=R). This implication for R=N guarantees that Smoryński's theorem follows from Matiyasevich's theorem. Harvey Friedman conjectures that the set of all polynomials of several variables with integer coefficients that have a rational solution is not recursive. Harvey Friedman conjectures that the set of all polynomials of several variables with integer coefficients that have only finitely many rational solutions is not recursively enumerable. These conjectures are equivalent by our results for R=Q. (shrink)

Throughout this paper, we are trying to show how and why our Mathematical frame-work seems inappropriate to solve problems in Theory of Computation. More exactly, the concept of turning back in time in paradoxes causes inconsistency in modeling of the concept of Time in some semantic situations. As we see in the first chapter, by introducing a version of “Unexpected Hanging Paradox”,first we attempt to open a new explanation for some paradoxes. In the second step, by applying this paradox, it (...) is demonstrated that any formalized system for the Theory of Computation based on Classical Logic and Turing Model of Computation leads us to a contradiction. We conclude that our mathematical frame work is inappropriate for Theory of Computation. Furthermore, the result provides us a reason that many problems in Complexity Theory resist to be solved.(This work is completed in 2017 -5- 2, it is in vixra in 2017-5-14, presented in Unilog 2018, Vichy). (shrink)

I give a detailed review of 'The Outer Limits of Reason' by Noson Yanofsky from a unified perspective of Wittgenstein and evolutionary psychology. I indicate that the difficulty with such issues as paradox in language and math, incompleteness, undecidability, computability, the brain and the universe as computers etc., all arise from the failure to look carefully at our use of language in the appropriate context and hence the failure to separate issues of scientific fact from issues of how language works. (...) I discuss Wittgenstein's views on incompleteness, paraconsistency and undecidability and the work of Wolpert on the limits to computation. To sum it up: The Universe According to Brooklyn---Good Science, Not So Good Philosophy. -/- Those wishing a comprehensive up to date framework for human behavior from the modern two systems view may consult my book ‘The Logical Structure of Philosophy, Psychology, Mind and Language in Ludwig Wittgenstein and John Searle’ 2nd ed (2019). Those interested in more of my writings may see ‘Talking Monkeys--Philosophy, Psychology, Science, Religion and Politics on a Doomed Planet--Articles and Reviews 2006-2019 3rd ed (2019) and Suicidal Utopian Delusions in the 21st Century 4th ed (2019) . (shrink)

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)

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.

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 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)

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.