Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSmooth relaxation preserving Turing machines
209
0
0.0
(
0
)
Authors
Adrian K. Xu
Ask ChatGPT about the research
No Arabic abstract
Clift and Murfet (2019) introduced a naive Bayesian smooth relaxation of Turing machines motivated by work in differential linear logic; this was subsequently used to endow spaces of program codes of bounded length with a smooth manifold structure via the staged-pseudo universal Turing machine introduced by Clift, Murfet and Wallbridge (2021). In this paper, we give a general construction for simulating n-tape Turing machines on a single tape Turing machine such that the (naive Bayesian) uncertainty is propagated in an equivalent manner. This result suggests a stronger kind of equivalence between single tape and n-tape Turing machines than that established by classical results, however, the clarification of these implications is open to future work. We then construct a pseudo universal Turing machine which similarly preserves the propagation of uncertainty in its simulations, and observe that this gives rise to a particularly natural smooth relaxation of the space of programs.
rate research
Read More
This note introduces a generalization to the setting of infinite-time computation of the busy beaver problem from classical computability theory, and proves some results concerning the growth rate of an associated function. In our view, these results indicate that the generalization is both natural and promising.
The Posner-Robinson Theorem states that for any reals $Z$ and $A$ such that $Z oplus 0 leq_mathrm{T} A$ and $0 <_mathrm{T} Z$, there exists $B$ such that $A equiv_mathrm{T} B equiv_mathrm{T} B oplus Z equiv_mathrm{T} B oplus 0$. Consequently, any nonzero Turing degree $operatorname{deg}_mathrm{T}(Z)$ is a Turing jump relative to some $B$. Here we prove the hyperarithmetical analog, based on an unpublished proof of Slaman, namely that for any reals $Z$ and $A$ such that $Z oplus mathcal{O} leq_mathrm{T} A$ and $0 <_mathrm{HYP} Z$, there exists $B$ such that $A equiv_mathrm{T} mathcal{O}^B equiv_mathrm{T} B oplus Z equiv_mathrm{T} B oplus mathcal{O}$. As an analogous consequence, any nonhyperarithmetical Turing degree $operatorname{deg}_mathrm{T}(Z)$ is a hyperjump relative to some $B$.
We describe the Turing Machine, list some of its many influences on the theory of computation and complexity of computations, and illustrate its importance.
An {omega}-language is a set of infinite words over a finite alphabet X. We consider the class of recursive {omega}-languages, i.e. the class of {omega}-languages accepted by Turing machines with a Buchi acceptance condition, which is also the class {Sigma}11 of (effective) analytic subsets of X{omega} for some finite alphabet X. We investigate here the notion of ambiguity for recursive {omega}-languages with regard to acceptance by Buchi Turing machines. We first present in detail essentials on the literature on {omega}-languages accepted by Turing Machines. Then we give a complete and broad view on the notion of ambiguity and unambiguity of Buchi Turing machines and of the {omega}-languages they accept. To obtain our new results, we make use of results and methods of effective descriptive set theory.
The model of local Turing machines is introduced, including classical and quantum ones, in the framework of matrix-product states. The locality refers to the fact that at any instance of the computation the heads of a Turing machine have definite locations. The local Turing machines are shown to be equivalent to the corresponding circuit models and standard models of Turing machines by simulation methods. This work reveals the fundamental connection between tensor-network states and information processing.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
