Iteration, inequalities, and differentiability in analog computers
Journal of complexity, 2000•Elsevier
Shannon's general purpose analog computer (GPAC) is an elegant model of analog
computation in continuous time. In this paper, we consider whether the set G of GPAC-
computable functions is closed under iteration, that is, whether for any function f (x)∈ G
there is a function F (x, t)∈ G such that F (x, t)= ft (x) for nonnegative integers t. We show that
G is not closed under iteration, but a simple extension of it is. In particular, if we relax the
definition of the GPAC slightly to include unique solutions to boundary value problems, or …
computation in continuous time. In this paper, we consider whether the set G of GPAC-
computable functions is closed under iteration, that is, whether for any function f (x)∈ G
there is a function F (x, t)∈ G such that F (x, t)= ft (x) for nonnegative integers t. We show that
G is not closed under iteration, but a simple extension of it is. In particular, if we relax the
definition of the GPAC slightly to include unique solutions to boundary value problems, or …
Shannon's general purpose analog computer (GPAC) is an elegant model of analog computation in continuous time. In this paper, we consider whether the set G of GPAC-computable functions is closed under iteration, that is, whether for any function f(x)∈G there is a function F(x, t)∈G such that F(x, t)=ft(x) for nonnegative integers t. We show that G is not closed under iteration, but a simple extension of it is. In particular, if we relax the definition of the GPAC slightly to include unique solutions to boundary value problems, or equivalently if we allow functions xkθ(x) that sense inequalities in a differentiable way, the resulting class, which we call G +θk, is closed under iteration. Furthermore, G +θk includes all primitive recursive functions and has the additional closure property that if T(x) is in G +θk, then any function ofx computable by a Turing machine in T(x) time is also.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果