The basic theory of infinite time register machines

Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all ${\Pi^1_1}Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all P¹₁{\Pi^1_1} sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRM-clockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not n ? r{n \in r} with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond much better to ITTMs we hold that in future the resetting register machines should be called ITRMs.     

Infinite Time Turing Machines With Only One Tape

Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi‐tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for partial functions f : ℝ → ℕ, the same class of computable functions. Nevertheless, there are infinite time computable functions f : ℝ → ℝ that are not one‐tape computable, and so the two models of infinitary computation are not equivalent. Surprisingly, the class of one‐tape computable functions is not closed under composition; but closing it under composition yields the full class of all infinite time computable functions. Finally, every ordinal that is clockable by an infinite time Turing machine is clockable by a one‐tape machine, except certain isolated ordinals that end gaps in the clockable ordinals.     

Post’s Problem for ordinal register machines: An explicit approach

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.     

Σ-Subsets of Natural Numbers

It is shown that the class of all possible families of -subsets of finite ordinals in admissible sets coincides with a class of all non-empty families closed under e-reducibility and . The construction presented has the property of being minimal under effective definability. Also, we describe the smallest (w.r.t. inclusion) classes of families of subsets of natural numbers, computable in hereditarily finite superstructures. A new series of examples is constructed in which admissible sets lack in universal -function. Furthermore, we show that some principles of classical computability theory (such as the existence of an infinite non-trivial enumerable subset, existence of an infinite computable subset, reduction principle, uniformization principle) are always satisfied for the classes of all -subsets of finite ordinals in admissible sets.     

δ-Uniform BSS Machines

Aδ-uniform BSS machine is a standard BSS machine which does not rely on exact equality tests. We prove that, for any real closed archimedean fieldR, a set isδ-uniformly semi-decidable iff it is open and semi-decidable by a BSS machine which is locally time bounded; we also prove that the local time bound condition is nontrivial. This entails a number of results about BSS machines, in particular the existence of decidable sets whose interior (closure) is not even semi-decidable without adding constants. Finally, we show that the sets semi-decidable by Turing machines are the sets semi-decidable byδ-uniform machines with coefficients inQorT, the field of Turing computable numbers.     

Initial segments of computable linear orders with additional computable predicates

We study computable linear orders with computable neighborhood and block predicates. In particular, it is proved that there exists a computable linear order with a computable neighborhood predicate, having a Π₁⁰ -initial segment which is isomorphic to no computable order with a computable neighborhood predicate. On the other hand, every Σ₁⁰ -initial segment of such an order has a computable copy enjoying a computable neighborhood predicate. Similar results are stated for computable linear orders with a computable block predicate replacing a neighborhood relation. Moreover, using the results obtained, we give a simpler proof for the Coles–Downey–Khoussainov theorem on the existence of a computable linear order with Π₂⁰ -initial segment, not having a computable copy.     

Effectiveness in RPL, with applications to continuous logic

In this paper, we introduce a foundation for computable model theory of rational Pavelka logic (an extension of ?ukasiewicz logic) and continuous logic, and prove effective versions of some related theorems in model theory. We show how to reduce continuous logic to rational Pavelka logic. We also define notions of computability and decidability of a model for logics with computable, but uncountable, set of truth values; we show that provability degree of a formula with respect to a linear theory is computable, and use this to carry out an effective Henkin construction. Therefore, for any effectively given consistent linear theory in continuous logic, we effectively produce its decidable model. This is the best possible, since we show that the computable model theory of continuous logic is an extension of computable model theory of classical logic. We conclude with noting that the unique separable model of a separably categorical and computably axiomatizable theory (such as that of a probability space or an L^p Banach lattice) is decidable.     

Adjoint machines,state-behavior machines,and duality

A process X: $\text{K}$→$\text{K}$ is output if Dyn(X)→$\text{K}$ has a right adjoint; state-behavior if Dyn(X)→X has both left and right adjoints; and adjoint if X has a right adjoint and $\text{K}$ has countable coproducts. Output processes provide the proper setting for a general theory of state observability. We give a minimal realization theory using image factorization of a total response map. We give an adjointness theory for state-behavior machines and a duality theory for adjoint machines which clarifies classical linear system duality and yields an improved duality for nondeterministic automata. Adjoint machines (machines with adjoint input processes) provide the first integration of classical sequential machines (the only state-behavior machines in the category, Set, of sets), metric machines, topological machines, linear systems, nondeterministic automata and Boolean machines. There exist state-behavior machines which are not adjoint (but not in Set).     

A semantic study of the first-order predicate logic with uncertainty involved

In this paper, we provide a semantic study of the first-order predicate logic for situations involving uncertainty. We introduce the concepts of uncertain predicate proposition, uncertain predicate formula, uncertain interpretation and degree of truth in the framework of uncertainty theory. Compared with classical predicate formula taking true value in \(\{0,1\}\) , the degree of truth of uncertain predicate formula may take any value in the unit interval \([0,1]\) . We also show that the uncertain first-order predicate logic is consistent with the classical first-order predicate logic on some laws of the degree of truth.     

Computational bounds on polynomial differential equations

In this paper we study from a computational perspective some properties of the solutions of polynomial ordinary differential equations.We consider elementary (in the sense of Analysis) discrete-time dynamical systems satisfying certain criteria of robustness. We show that those systems can be simulated with elementary and robust continuous-time dynamical systems which can be expanded into fully polynomial ordinary differential equations in Q[π]. This sets a computational lower bound on polynomial ODEs since the former class is large enough to include the dynamics of arbitrary Turing machines.We also apply the previous methods to show that the problem of determining whether the maximal interval of definition of an initial-value problem defined with polynomial ODEs is bounded or not is in general undecidable, even if the parameters of the system are computable and comparable and if the degree of the corresponding polynomial is at most 56.Combined with earlier results on the computability of solutions of polynomial ODEs, one can conclude that there is from a computational point of view a close connection between these systems and Turing machines.     

Definable Ramsey and definable Erdös ordinals

This paper studies the relation between definable Ramsey ordinals and constructible sets which have a certain set of indiscernibles. It is shown that an ordinal κ is Σ₁-Ramsey if and only if κ is ∑_ω-Ramsey. Similar results are obtained for definable Erdös ordinals.     

Theories and Theories of Truth

Formal theories, as in logic and mathematics, are sets of sentences closed under logical consequence. Philosophical theories, like scientific theories, are often far less formal. There are many axiomatic theories of the truth predicate for certain formal languages; on analogy with these, some philosophers (most notably Paul Horwich) have proposed axiomatic theories of the property of truth. Though in many ways similar to logical theories, axiomatic theories of truth must be different in several nontrivial ways. I explore what an axiomatic theory of truth would look like. Because Horwich’s is the most prominent, I examine his theory and argue that it fails as a theory of truth. Such a theory is adequate if, given a suitable base theory, every fact about truth is a consequence of the axioms of the theory. I show, using an argument analogous to Gödel’s incompleteness proofs, that no axiomatic theory of truth could ever be adequate. I also argue that a certain class of generalizations cannot be consequences of the theory.     

Positive Presentations of Families Relative to <Emphasis Type="Italic">e</Emphasis>-Oracles

We introduce the notion of A-numbering which generalizes the classical notion of numbering. All main attributes of classical numberings are carried over to the objects considered here. The problem is investigated of the existence of positive and decidable computable A-numberings for the natural families of sets e-reducible to a fixed set. We prove that, for every computable A-family containing an inclusion-greatest set, there also exists a positive computable A-numbering. Furthermore, for certain families we construct a decidable (and even single-valued) computable total A-numbering when A is a low set; we also consider a relativization containing all cases of total sets (this in fact corresponds to computability with a usual oracle).     

A feasible theory of truth over combinatory algebra

We define an applicative theory of truth _TPT${\mathsf{T}}_{\mathsf{PT}}$ which proves totality exactly for the polynomial time computable functions. _TPT${\mathsf{T}}_{\mathsf{PT}}$ has natural and simple axioms since nearly all its truth axioms are standard for truth theories over an applicative framework. The only exception is the axiom dealing with the word predicate. The truth predicate can only reflect elementhood in the words for terms that have smaller length than a given word. This makes it possible to achieve the very low proof-theoretic strength. Truth induction can be allowed without any constraints. For these reasons the system _TPT${\mathsf{T}}_{\mathsf{PT}}$ has the high expressive power one expects from truth theories. It allows embeddings of feasible systems of explicit mathematics and bounded arithmetic.     

Zero-selectors and GO spaces

We are dealing with Vietoris continuous zero-selectors, i.e., they choose for each non-empty closed set F an isolated point in F. We show that the presence of a continuous zero-selector even on a small class of non-empty closed sets of a space X implies that X is scattered if X is metrizable or non-Archimedean or a P-space. Finally, using continuous zero-selectors, we characterize suborderable spaces which are subspaces of ordinals.     

Approximate decidability in euclidean spaces

We study concepts of decidability (recursivity) for subsets of Euclidean spaces ?^k within the framework of approximate computability (type two theory of effectivity). A new notion of approximate decidability is proposed and discussed in some detail. It is an effective variant of F. Hausdorff's concept of resolvable sets, and it modifies and generalizes notions of recursivity known from computable analysis, formerly used for open or closed sets only, to more general types of sets. Approximate decidability of sets can equivalently be expressed by computability of the characteristic functions by means of appropriately working oracle Turing machines. The notion fulfills some natural requirements and is hereditary under canonical embeddings of sets into spaces of higher dimensions. However, it is not closed under binary union or intersection of sets. We also show how the framework of resolvability and approximate decidability can be applied to investigate concepts of reducibility for subsets of Euclidean spaces.     

图灵机计算实数函数的稳定性

定义在全体实数上的可计算函数是一个很重要的概念．在这以前定义可计算的实数函数有两个途径．第一个途径是首先要定义可计算实数的指标．想要确定实数函数y=f（x）是不是可以计算就要看是否存在一个自然数的（部分）递归函数将可计算实数x的指标对应到可计算实数y的指标．这样一来对实数函数的研究依赖于对自然数函数的研究．第二个定义可计算的实数函数的途径是以逼近为基础的．一个实数函数是可以计算的如果它既是序列可计算的同时也是一致连续的．用这个途径来定义可计算实数函数使用的条件过强以至于很多有用的实数函数成为不可计算的实数函数．例如“〈”和“=”的命题函数就是不可以计算的因为它们是不连续的命题函数．本文讨论了图灵机的稳定性并且给出了一个基于稳定图灵机的可计算实数函数的定义．我们的定义不需要用到自然数的（部分）递归函数．根据我们的定义很多常用实数函数特别是一些不连续的常用实数函数都是可以计算的．用我们的定义来讨论可计算实数函数的性质比原来的定义要方便得多．     

Index sets of decidable models

We study the index sets of the class of d-decidable structures and of the class of d-decidable countably categorical structures, where d is an arbitrary arithmetical Turing degree. It is proved that the first of them is m-complete ∑ ₃ ^{0, d} , and the second is m-complete ∑ ₃ ^{0, d} \∑ ₃ ^{0, d} in the universal computable numbering of computable structures for the language with one binary predicate.     

The computable dimension of ordered abelian groups

Let G be a computable ordered abelian group. We show that the computable dimension of G is either 1 or ω, that G is computably categorical if and only if it has finite rank, and that if G has only finitely many Archimedean classes, then G has a computable presentation which admits a computable basis.