Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Busy Beaver Problem for Infinite-Time Turing Machines
177
0
0.0
(
0
)
Added by
James Long III
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
The halting problem is undecidable --- but can it be solved for most inputs? This natural question was considered in a number of papers, in different settings. We revisit their results and show that most of them can be easily proven in a natural framework of optimal machines (considered in algorithmic information theory) using the notion of Kolmogorov complexity. We also consider some related questions about this framework and about asymptotic properties of the halting problem. In particular, we show that the fraction of terminating programs cannot have a limit, and all limit points are Martin-Lof random reals. We then consider mass problems of finding an approximate solution of halting problem and probabilistic algorithms for them, proving both positive and negative results. We consider the fraction of terminating programs that require a long time for termination, and describe this fraction using the busy beaver function. We also consider approxima
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.
We define a new transfinite time model of computation, infinite time cellular automata. The model is shown to be as powerful than infinite time Turing machines, both on finite and infinite inputs; thus inheriting many of its properties. We then show how to simulate the canonical real computation model, BSS machines, with infinite time cellular automata in exactly omega steps.
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.
Robin Hirsch posed in 1996 the Really Big Complexity Problem: classify the computational complexity of the network satisfaction problem for all finite relation algebras $bf A$. We provide a complete classification for the case that $bf A$ is symmetric and has a flexible atom; the problem is in this case NP-complete or in P. If a finite integral relation algebra has a flexible atom, then it has a normal representation $mathfrak{B}$. We can then study the computational complexity of the network satisfaction problem of ${bf A}$ using the universal-algebraic approach, via an analysis of the polymorphisms of $mathfrak{B}$. We also use a Ramsey-type result of Nev{s}etv{r}il and Rodl and a complexity dichotomy result of Bulatov for conservative finite-domain constraint satisfaction problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
