We study $\Sigma_1$ theory of the Turing degrees in the (both finite and transfinite levels of ) Ershov hierarchy. By the author's recent work joint with Slaman, Stephan and Yang, we prove that most of them have different $\Sigma_1$-theory in the case parameters permitted

We give the computable Riesz representation theorems on two different cases. One is for the dual of $C[a,b]$. By the Riesz representation theorem for the dual of $C[a,b]$, for every continuous linear operator $F:C[a,b]\to \IR$, there is a function $g:[a,b]\to\IR$ of bounded variation such that $\[F(f)=\int f\,dg \ \ \ (f\in C[a,b])\]$ and the function $g$ can be normalized such that $V(g)=\| F\|$. In this paper we prove a computable version of this theorem in the framework of TTE. For given natural representations of the spaces we prove that there are computable operators mapping $F$ to $g$ and mapping $g$ to $F$. Another is for locally compact Hausdorff space. We know that Riesz Representation Theorem plays an important role in Functional Analysis and General Topology. That is, let $X$ be a locally compact Hausdorff space, and let I be positive linear functional on $\KK(X)$. Then there is unique regular Borel measure $\mu$ on $X$ such that $\[I(f)=\int f\,d\mu \]$ holds for each $f$ in $\KK (X)$.\cite{GP65} In this paper, we prove a computable version of this theorem. $\I2$

We first introduce the definition of approximation, i.e. a sub-formula with less variables. We present a method to construct the most accurate approximations. Furthermore, we consider the variable minimal approximations with some characteristics, so-called variable minimal equivalence (VME), variable minimal satisfiability (VMS), and variable minimal unsatisfiability (VMU), respectively. We investigate these classes and show that the relevant determining problems are intractable in general.

We introduce the concepts of complex and autocomplex sets, where a set A is complex if there is a recursive, nondecreasing and unbounded lower bound on the Kolmogorov complexity of the prefixes (of the characteristic sequence) of A, and autocomplex is defined likewise with recursive replaced by A-recursive. We observe that exactly the autocomplex sets allow to compute words of given Kolmogorov complexity and demonstrate that a set computes a diagonally nonrecursive (DNR) function if and only if the set is autocomplex. The class of sets that compute DNR functions is intensively studied in recursion theory and is known to coincide with the class of sets that compute fixed-point free functions. Consequently, the Recursion Theorem fails relative to a set if and only if the set is autocomplex, that is, we have a characterization of a fundamental concept of theoretical computer science in terms of Kolmogorov complexity. Moreover, we obtain that recursively enumerable sets are autocomplex if and only if they are complete, which yields an alternate proof of the well-known completeness criterion for recursively enumerable sets in terms of computing DNR functions. All results on autocomplex sets mentioned in the last paragraph extend to complex sets if the oracle computations are restricted to truth-table or weak truth-table computations, for example, a set is complex if and only if it wtt-computes a DNR function. Moreover, we obtain a set that is complex but does not compute a Martin-L¡§of random set, which gives a partial answer to the open problem whether all sets of positive constructive Hausdorff dimension compute Martin-L¡§of random sets. Furthermore, the following questions are addressed: Given n, how difficult is it to find a word of length n that (a) has at least prefix-free Kolmogorov complexity n, (b) has at least plain Kolmogorov complexity n or (c) has the maximum possible prefix-free Kolmogorov complexity among all words of length n. All these questions are investigated with respect to the oracles needed to carry out this task and it is shown that (a) is easier than (b) and (b) is easier than (c). In particular, we argue that for plain Kolmogorov complexity exactly the PA-complete sets compute incompressible words, while the class of sets that compute words of maximum complexity depends on the choice of the universal Turing machine, whereas for prefix-free Kolmogorov complexity exactly the complete sets allow to compute words of maximum complexity.

Interpreting in a structure M another structure N is a model theoretic technique to reduce properties of some kind of structures to those of another kind, e.g. decidability/undecidability, definability, rigidity. Investigations of "big pictures" of degree structures always involve such technique. We will review two variations in r.e. degrees, namely Harring-Shelah coding and Slaman-Woodin coding, and a shortcoming claimed by Nies of known codings. Finally we will suggest a way to walk around this shortcoming, though our solution does not lead to any valuable insight. To this end we will briefly introduce the construction of Harrington-Shelah coding.

Given a bounded linear mapping $T$ of separable Hilbert spaces and an element $y$ from the range of $T$, can we effectively solve the equation $Tx = y$? If one formulates this problem within the representation based approach to effective analysis (i.e. using Turing machines operating on infinite binary sequences representing the objects of consideration), it is well known that the answer is ``No'' in general. Taking inspiration in a result from Information Based Complexity and applying Tikhonov Regularization, we show that the inverse of $T$ can still be computed as a point in an $L^2$ space with respect to a Gaussian measure if additional information on the adjoint of $T$ and on the $L^2$ norm of the inverse is available.

This talk will survey some of the principle ideas and methods involved in measuring the strength of arithmetical proof systems, in terms of the complexity of their provably recursive functions. Transfinite subrecursive hierarchies of bounding functions provide a linear scale against which proof-theoretic strength can be measured and compared. They also give a direct link to various well-known combinatorial independence results for theories. The methods are those of proof theory - cut elimination, ordinal analysis etc.

Hilbert's Tenth Problem (HTP) asks for an effective algorithm to test whether an arbitrary polynomial equation with integer coefficients has integral solutions. On the basis of the important work of Davis, Putnam and Robinson, in 1970 Matijasevich took the last step to show the unsolvability of HTP. Since 1970 reduction of involved unknowns and various extended HTP have become research themes in the field. In this talk we will give a survey of problems and results in the two aspects.

Based on a result of Nies on definability the upper semilattice of computably enumerable degrees (denoted by R), we find that in R filters generated by definable subsets are also definable. As applications we demonstrate two new definable filters and study their supremum. Finally we demonstrate a counterexample.

We investigate aspects of effectivity and computability on closed and compact subsets of locally compact spaces. We use the framework of the representation approach, TTE, where continuity and computability on finite and infinite sequences of symbols are defined canonically and transferred to abstract sets by means of notations and representations. This work is a generalization of the concepts introduced in \cite{BW99} and \cite{Wei00} for the Euclidean case and in \cite{BP03} for metric spaces. Whenever reasonable, we transfer a representation of the set of closed or compact subsets to locally compact spaces and discuss its properties and their relations to each other.

Back