Analog computation attempts to capture any type of computation, that can be realized by any type of physical system or physical process, including but not limited to computation over continuous measurable quantities. ...
详细信息
Analog computation attempts to capture any type of computation, that can be realized by any type of physical system or physical process, including but not limited to computation over continuous measurable quantities. A pioneering model is the General Purpose Analog Computer (GPAC), initially presented by Shannon in 1941. The GPAC is capable of manipulating real-valued data streams;however, it has been shown to be strictly less powerful than other models of computation on the reals, such as computable analysis. In previous work, we proposed an extension of the Shannon GPAC, denoted LGPAC, designed to overcome its limitations. Not only is the LGPAC model capable of expressing computation over general data spaces X, but it also directly incorporates approximating computations by means of a limit module. An important feature of this work is the generalisation of the framework of the computation theory from Banach to Frechet spaces. In this paper, we compare the LGPAC with a digital model of computation based on effective representations (tracking computability). We establish general conditions under which LGPAC-generable functions are tracking computable.
We characterize the intrinsically recursive functions over the algebraic closure of a finite field in terms of Turing machine complexity classes and derive some structural properties about the family of such functions...
详细信息
We characterize the intrinsically recursive functions over the algebraic closure of a finite field in terms of Turing machine complexity classes and derive some structural properties about the family of such functions. In particular, we show that the domain of convergence of any partial recursive function is again recursive, and, under complexity theoretic hypotheses, that the class of tail recursive functions is strictly smaller than the class of recursive functions (cf. Theorems 5.4, 5.2, and Section 8). Underlying these results is the "meta-result" that we can perform a limited amount of arithmetic inside the field itself, with no access to a separate sort of natural numbers. (C) 2017 Published by Elsevier Inc.
We consider the following problem for various infinite-time machines. If a real is computable relative to a large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeage...
详细信息
We consider the following problem for various infinite-time machines. If a real is computable relative to a large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable? We show that the answer is independent of ZFC for ordinal Turing machines with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite-time Turing machines, unresetting and resetting infinite-time register machines, and alpha-Turing machines for countable admissible ordinals alpha.
The unfolding of schematic formal systems is a novel concept which was initiated in Feferman (in: Hajek (Ed.), Godel '96, Lecture Notes in Logic, Springer, Berlin, 1996, pp. 3-22). This paper is mainly concerned w...
详细信息
The unfolding of schematic formal systems is a novel concept which was initiated in Feferman (in: Hajek (Ed.), Godel '96, Lecture Notes in Logic, Springer, Berlin, 1996, pp. 3-22). This paper is mainly concerned with the proof-theoretic analysis of various unfolding systems for non-finitist arithmetic NFA. In particular, we examine two restricted unfoldings U-0(NFA) and U-1(NFA), as well as a full unfolding, U(NFA). The principal results then state: (i) U-0(NFA) is equivalent to PA;(ii) U-1(NFA) is equivalent to RA(
Analog computation attempts to capture any type of computation, that can be realized by any type of physical system or physical process, including but not limited to computation over continuous measurable quantities. ...
详细信息
ISBN:
(纸本)9783030367558;9783030367541
Analog computation attempts to capture any type of computation, that can be realized by any type of physical system or physical process, including but not limited to computation over continuous measurable quantities. A pioneering model is the General Purpose Analog Computer (GPAC), initially presented by Shannon in 1941. The GPAC is capable of manipulating real-valued data streams;however, it has been shown to be strictly less powerful than other models of computation on the reals, such as computable analysis. In previous work, we proposed an extension of the Shannon GPAC, denoted LGPAC, designed to overcome its limitations. Not only is the LGPAC model capable of expressing computation over general data spaces X, it also directly incorporates approximating computations by means of a limit module. In this paper, we compare the LGPAC with a digital model of computation based on effective representations (tracking computability). We establish general conditions under which LGPAC-generable functions are tracking computable.
暂无评论