检索结果-内蒙古大学图书馆

Tracking computability of GPAC-generable functions

JOURNAL OF LOGIC AND COMPUTATION 2021年第1期31卷 326-346页

作者： Pocas, Diogo Zucker, Jeffery Univ Lisbon Fac Ciencias Dept Informat LASIGE P-1749016 Lisbon Portugal McMaster Univ Dept Comp & Software Hamilton ON L8S 4K1 Canada

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.

关键词： generalized computability generalized recursion theory computation on the reals analog computation Shannon GPAC tracking computability

来源：评论

学校读者我要写书评

暂无评论

Models of computation for partial functions on the reals

引用

JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING 2015年第2期84卷 218-237页

作者： Fu, Ming Quan Zucker, Jeffery McMaster Univ Dept Comp & Software Hamilton ON L8S 4K1 Canada

We compare models of computation for partial functions f :R -> R. We consider four models: two concrete (Grzegorczyk-Lacombe and tracking computability), one abstract (approximability by a While program with "countable choice") and a new hybrid model: multipolynomial approximability. We show that these four models are equivalent, under the two assumptions: (1) the domain of f is the union of an effective exhaustion, i.e. a sequence of "stages", each of which is a finite union of disjoint rational open intervals, and (2) f is effectively locally uniformly continuous w.r.t. this exhaustion. These assumptions seem to hold for all unary elementary functions of real analysis, many of which are, of course, partial. We make a conjecture with regard to this. (C) 2014 Elsevier Inc. All rights reserved.

关键词： generalized computability computability on topological algebra computability on the reals Grzegorczyk-Lacombe computability

来源：评论

学校读者我要写书评

暂无评论

Primitive recursive selection functions for existential assertions over abstract algebras

引用

JOURNAL OF LOGIC AND ALGEBRAIC PROGRAMMING 2008年第2期76卷 175-197页

作者： Strahm, Thomas Zucker, Jeffery Univ Bern Inst Informat & Angew Math CH-3012 Bern Switzerland McMaster Univ Dept Comp & Software Hamilton ON L8S 4K1 Canada

We generalize to abstract many-sorted algebras the classical proof-theoretic result due to Parsons, Mints and Takeuti that an assertion for all x there exists y P(x, y) (where P is Sigma(0)(1)), provable in Peano arithmetic with Sigma(0)(1) induction, has a primitive recursive selection function. This involves a corresponding generalization to Such algebras of the notion of primitive recursiveness. The main difficulty encounered in carrying Out this generalization turns Out to he the fact that equality over these algebras may]lot be computable. and hence atomic formulas in their Signatures May not he decidable. The solution given here is to develop an appropriate concept of realizability of existential assertions over Such algebras, generalized to realizability of sequents of existential assertions. In this way, the results can be seen to hold for classical proof systems. This investigation may give some insight into the relationship between specifiability and computability for data types such as the reals, where the atomic formulas, i.e.. equations between terms of type real, are not computable. (C) 2008 Elsevier Inc. All rights reserved.

关键词： generalized computability realizabililty selection function

来源：评论

学校读者我要写书评

暂无评论

Computational complexity in algebraic systems

引用

SIBERIAN MATHEMATICAL JOURNAL 2004年第6期45卷 1113-1123页

作者： Rybalov, AN Omsk State University USA

computability and computational complexity were first considered over the fields of real and complex numbers and generalized to arbitrary algebraic systems. This article approaches the theory of computational complexity over an arbitrary algebraic system by taking computability over the list extension for a computational model of it. We study the resultant polynomial complexity classes and mention some NP-complete problems.

关键词： generalized computability computational complexity

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL RESULTS ON RECOGNIZABILITY FOR INFINITE TIME REGISTER MACHINES

引用

JOURNAL OF SYMBOLIC LOGIC 2015年第4期80卷 1116-1130页

作者： Carl, Merlin Univ Konstanz Fachbereich Math & Stat D-78457 Constance Germany

Exploring further the properties of ITRM-recognizable reals started in [1], we provide a detailed analysis of recognizable reals and their distribution in Godels constructible universe L. In particular, we show that new unrecognizable reals are generated at every index gamma >= omega(CK)(omega). We give a machine-independent characterization of recognizability by proving that a real r is recognizable if and only if it is Sigma(1)-definable over L-omega omega CK,L-r and that r is an element of L-omega omega CK,L-r for every recognizable real r and show that either every or no r with r is an element of L-omega omega CK,L-r generated over an index stage L-gamma is recognizable. Finally, the techniques developed along the way allow us to prove that the halting number for ITRMs is recognizable and that the set of ITRM-computable reals is not ITRM-decidable.

关键词： Infinite Time computability generalized computability Infinite Time Register Machines Recognizable Reals

来源：评论

学校读者我要写书评

暂无评论

About the admissible predicates on admissible sets

引用

SIBERIAN MATHEMATICAL JOURNAL 2005年第4期46卷 668-674页

作者： Morozov, AS Sobolev Institute of Mathematics Novosibirsk Russia

We study the admissible predicates, i.e., the predicates having the property that their addition to the signature of an admissible set preserves the property "to be an admissible set." We show that the family of these predicates is much wider than the family of Delta-predicates. We also construct a family of admissible predicates of cardinality 2(omega) such that the addition of an arbitrary pair of predicates of this family to the signature of an admissible set violates the admissibility of the latter as well as other examples of families of admissible predicates.

关键词： admissible set admissible predicate generalized computability

来源：评论

学校读者我要写书评

暂无评论

Properties of sI£-Reducibility

引用

ALGEBRA AND LOGIC 2014年第5期53卷 405-417页

作者： Stukachev, A. I. Sobolev Inst Math Novosibirsk 630090 Russia Novosibirsk State Univ Novosibirsk 630090 Russia

We couch the definition of sI -reducibility pound on structures, describe some properties of sI -reducibility pound, and also exemplify explicitly how to use it. In particular, we consider natural expansions of structures such as Morleyization and Skolemization. Previously, a class of quasiregular structures was defined to be a class of fixed points of Morleyization with respect to sI -reducibility pound, extending the class of models of regular theories and the class of effectively model-complete structures. It was proved that an HF-superstructure over a quasiregular structure is quasiresolvent and, consequently, has a universal I - pound function and possesses the reduction property. Here we show that an HF-superstructure over a quasiregular structure has the I -uniformization pound property iff with respect to sI -reducibility pound this structure is a fixed point for some of its Skolemizations with an extra property, that of well-definededness. In this case an HF-superstructure and a Moschovakis superstructure over a given structure are I -equivalent pound.

关键词： generalized computability model theory model completeness decidability uniformization property

来源：评论

学校读者我要写书评

暂无评论

ITBM-Constructive Completions of Algebras

引用

SIBERIAN MATHEMATICAL JOURNAL 2024年第3期65卷 589-598页

作者： Morozov, A. S. Sobolev Inst Math Novosibirsk Russia Novosibirsk State Univ Novosibirsk Russia

We introduce the notion of ITBM-constructive algebra, which is a generalization of the notion of constructive algebra, and study completions of such algebras. We obtain some criterion for the existence of completions for metrized algebras and prove that each ITBM-constructive metrized algebra which has completion can be naturally extended to the ITBM-constructive completion. Using these results, we establish the existence of ITBM-constructive presentations for some particular algebras.

关键词： Blum-Shub-Smale machine ITBM-constructive algebra generalized computability computability over the reals metrized algebra completion 510.5

来源：评论

学校读者我要写书评

暂无评论

A generalized Feiner hierarchy

引用

SIBERIAN MATHEMATICAL JOURNAL 2008年第2期49卷 191-201页

作者： Alaev, P. E. Sobolev Inst Math Novosibirsk Russia

We study some properties of a generalization of the Feiner hierarchy of Delta(0)(omega)-computable functions and consider various conditions for the inclusion of one class of this hierarchy into another.

关键词： Feiner hierarchy computable function generalized computability

来源：评论

学校读者我要写书评

暂无评论

A jump inversion theorem for the semilattices of sigma-degrees

引用

Siberian Advances in Mathematics 2010年第1期20卷 68-74页

作者： Stukachev, A.I. Sobolev Institute of Mathematics Novosibirsk 630090 Russian Federation Novosibirsk State University Novosibirsk 630090 Russian Federation

We prove an analogue of the jump inversion theorem for the semilattices of Σ-degrees of structures. As a corollary, we get a similar result for the semilattices of degrees of presentability of countable structures. &... 详细信息

关键词： Admissible sets Computable structures Effective model theory generalized computability

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：