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

Tarski's theory of definability: common themes in descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic

引用

ANNALS OF PURE AND APPLIED LOGIC 2004年第1-3期126卷 77-92页

作者： Addison, JW Univ Calif Berkeley Dept Math Berkeley CA 94720 USA

Although the theory of definability had many important antecedents-such as the descriptive set theory initiated by the French semi-intuitionists in the early 1900s-the main ideas were first laid out in precise mathematical terms by Alfred Tarski beginning in 1929. We review here the basic notions of languages, explicit definability, and grammatical complexity, and emphasize common themes in the theories of definability for four important languages underlying, respectively, descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic. We review the history of previous studies of the similarities and differences in the theories of definability of the first three of these four languages. A seminal role leading toward unification of the theories has been played by the separation principles introduced (and regarded as so 4 ''fundamental") by Nikolai Luzin in 1927. Emphasizing analogies and driving toward further unification embracing finite-universe logic (a setting of special interest in theoretical computer science) we concentrate on a simple example-the first and second separation principles for existential-universal first-order sentences (which are known to fail in descriptive set theory, recursive function theory, and classical pure logic). Using this as a test case for the fundamental problem of how to "finitize" arguments in classical pure logic to the finite-universe case, we are led to the analogous negative solution by using the theory of certain special graphs: a graph is (m, n, p, q)-special for any positive integers m,n, p, q iff it is bipartite with m red points and n blue points and for every p-tuple (q-tuple) of red (blue) points there is a blue (red) point to (with) which they are all connected (disconnected). As an aside we introduce for further study a natural "Ramseyesque" increasing sequence A of positive integers, where A(p) is the least positive integer n for which an (n, n, p, p)-special graph exists. (C) 2003

关键词： theory of definability Alfred Tarski separation principles interpolation principles finite-universe logic prefix hierarchies bipartite graphs Ehrenfeucht-Fraisse games descriptive set theory recursive function theory classical pure logic finite model theory

来源：评论

学校读者我要写书评

暂无评论

Recursion theoretic operators for function complexity classes

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2008年第4期E91D卷 990-995页

作者： Ueno, Kenya Univ Tokyo Grad Sch Informat Sci & Technol Dept Comp Sci Tokyo 1138656 Japan

We characterize the gap between time and space complexity of functions by operators and completeness. First, we introduce a new notion of operators for function complexity classes based on recursive function theory and construct an operator which generates FPS PACE from FP. Then, we introduce new function classes composed of functions whose output lengths are bounded by the input length plus some constant. We characterize FP and FPS PACE by using these classes and operators. Finally, we define a new notion of completeness for FPS PACE and show a FPS PACE-complete function.

关键词： recursive function theory function complexity classes operators for complexity classes

来源：评论

学校读者我要写书评

暂无评论

Recursion-theoretic ranking and compression

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2019年 101卷 31-41页

作者： Hemaspaandra, Lane A. Rubery, Daniel Univ Rochester Dept Comp Sci 601 Elmwood Ave Rochester NY 14627 USA Google Inc 1600 Amphitheatre Pkwy Mountain View CA 94043 USA

For which sets A does there exist a mapping, computed by a total or partial recursive function, such that the mapping, when its domain is restricted to A, is a 1-to-1, onto mapping to Sigma*? For which sets A does there exist such a mapping that respects the lexicographical ordering within A? Both cases are types of perfect, minimal hash functions. The complexity-theoretic versions of these notions are known as compression functions and ranking functions. This paper defines and studies the recursion-theoretic versions of compression and ranking functions, and in particular studies which sets have, or lack, such functions. Thus this is a case where, in contrast to the usual direction of notion transferal, notions from complexity theory are inspiring notions, and an investigation, in computability theory. We show that the rankable and compressible sets broadly populate the 1-truth-table degrees, and we prove that every nonempty coRE cylinder is recursively compressible. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Compression functions Ranking functions Perfect minimal hash functions recursive function theory

来源：评论

学校读者我要写书评

暂无评论

The concept of a universal learning system as a basis for creating a general mathematical theory of learning

引用

MINDS AND MACHINES 2004年第4期14卷 453-484页

作者： Shimansky, YP Arizona State Univ Harrington Dept Bioengn Ctr Neural Interface Design Arizona Biodesign Inst Tempe AZ 85287 USA

The number of studies related to natural and artificial mechanisms of learning rapidly increases. However, there is no general theory of learning that could provide a unifying basis for exploring different directions in this growing field. For a long time the development of such a theory has been hindered by nativists' belief that the development of a biological organism during ontogeny should be viewed as parameterization of an innate, encoded in the genome structure by an innate algorithm, and nothing essentially new is created during this process. Noam Chomsky has claimed, therefore, that the creation of a non-trivial general mathematical theory of learning is not feasible, since any algorithm cannot produce a more complex algorithm. This study refutes the above argumentation by developing a counter-example based on the mathematical theory of algorithms and computable functions. It introduces a novel concept of a Universal Learning System (ULS) capable of learning to control in an optimal way any given constructive system from a certain class. The necessary conditions for the existence of a ULS and its main functional properties are investigated. The impossibility of building an algorithmic ULS for a sufficiently complex class of controlled objects is shown, and a proof of the existence of a nonalgorithmic ULS based on the axioms of classical mathematics is presented. It is argued that a non-algorithmic ULS is a legitimate object of not only mathematics, but also the world of nature. These results indicate that an algorithmic description of the organization and adaptive development of biological systems in general is not sufficient. At the same time, it is possible to create a rigorous non-algorithmic general theory of learning as a theory of ULS. The utilization of this framework for integrating learning-related studies is discussed.

关键词： computability creativity physical constructiveness recursive function theory theory of learning

来源：评论

学校读者我要写书评

暂无评论

Characterizing Programming Systems Allowing Program Self-Reference

引用

theory OF COMPUTING SYSTEMS 2009年第4期45卷 756-772页

作者： Case, John Moelius, Samuel E., III Univ Delaware Dept Comp & Informat Sci Newark DE 19716 USA

The interest is in characterizing insightfully the power of program self-reference in effective programming systems (epses), the computability-theoretic analogs of programming languages (for the partial computable functions). In an eps in which the constructive form of Kleene's Recursion Theorem (KRT) holds, it is possible to construct, algorithmically, from an arbitrary algorithmic task, a self-referential program that, in a sense, creates a self-copy and then performs that task on the self-copy. In an eps in which the not-necessarily-constructive form of Kleene's Recursion Theorem (krt) holds, such self-referential programs exist, but cannot, in general, be found algorithmically. In an earlier effort, Royer proved that there is no collection of recursive denotational control structures whose implementability characterizes the epses in which KRT holds. One main result herein, proven by a finite injury priority argument, is that the epses in which krt holds are, similarly, not characterized by the implementability of some collection of recursive denotational control structures. On the positive side, however, a characterization of such epses of a rather different sort is shown herein. Though, perhaps not the insightful characterization sought after, this surprising result reveals that a hidden and inherent constructivity is always present in krt.

关键词： Computability theory Computable operators Control structures Numberings Programming systems recursive function theory recursive operators Recursion theorem Self-reference

来源：评论

学校读者我要写书评

暂无评论

EASY CONSTRUCTIONS IN COMPLEXITY theory - GAP AND SPEED-UP THEOREMS

引用

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY 1973年第2期37卷 555-563页

作者： YOUNG, P PURDUE UNIV DEPT MATHW LAFAYETTEIN 47907

Abstract: Perhaps the two most basic phenomena discovered by the recent application of recursion theoretic methods to the developing theories of computational complexity have been Blum’s speed-up phenomena, with its extension to operator speed-up by Meyer and Fischer, and the Borodin gap phenomena, with its extension to operator gaps by Constable. In this paper we present a proof of the operator gap theorem which is much simpler than Constable’s proof. We also present an improved proof of the Blum speed-up theorem which has a straightforward generalization to obtain operator speed-ups. The proofs of this paper are new; the results are not. The proofs themselves are entirely elementary: we have eliminated all priority mechanisms and all but the most transparent appeals to the recursion theorem. Even these latter appeals can be eliminated in some “reasonable” complexity measures. Implicit in the proofs is what we believe to be a new method for viewing the construction of “complexity sequences."

关键词： recursive function theory computational complexity speedup theorems gap theorems Blum theory

来源：评论

学校读者我要写书评

暂无评论

POSTS PROGRAM AND INCOMPLETE recursiveLY-ENUMERABLE SETS

引用

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA 1991年第22期88卷 10242-10246页

作者： HARRINGTON, L SOARE, RI UNIV CHICAGO DEPT MATHCHICAGOIL 60637

A set A of nonnegative integers is recursively enumerable (r.e.) if A can be computably listed. It is shown that there is a first-order property, Q(X), definable in E, the lattice of r.e. sets under inclusion, such that (i) if A is any r.e. set satisfying Q(A) then A is nonrecursive and Turing incomplete and (ii) there exist an r.e. set A satisfying Q(A). This resolves a long open question stemming from Post's program of 1944, and it sheds light on the fundamental problem of the relationship between the algebraic structure of an r.e. set A and the (Turing) degree of information that A encodes.

关键词： recursive function theory TURING COMPUTABILITY DEGREES OF UNSOLVABILITY

来源：评论

学校读者我要写书评

暂无评论

Effective Enumeration of Infinitely Many Programs that Evade Formal Malware Analysis 1

引用

5th International Symposium on Cyber Security Cryptography and Machine Learning (CSCML)

作者： Liagkou, Vasiliki Nastou, Panagiotis E. Spirakis, Paul Stamatiou, Yannis C. Univ Patras Campus Comp Technol Inst & Press Diophantus Patras 26504 Greece Univ Liverpool Dept Comp Sci Liverpool England Univ Patras Comp Engn & Informat Dept Patras 26504 Greece Univ Patras Dept Business Adm Patras 26504 Greece Univ Ioannina Dept Informat & Telecommun Koatakioi Arta 47100 Greece Univ Aegean Dept Math Appl Math & Math Modeling Lab Samos Greece

ISBN: (数字)9783030780869

ISBN: (纸本)9783030780869;9783030780852

The formal study of computer malware was initiated in the seminal work of Fred Cohen in the mid 80s who applied elements of the theory of Computation in the investigation of the theoretical limits of using the Turing Machine formal model of computation in detecting viruses. Cohen gave a simple but realistic, formal, definition of the characteristic actions of a computer virus as a Turing Machine that replicates itself and then proved that constructing a Turing Machine that recognizes viruses (i.e. Turing Machines that act like viruses) is impossible, by reducing the Halting Problem, which is undecidable, to the problem of recognizing a computer virus. In this paper we complement Cohen's approach along similar lines, based on Recursion function theory and the theory of Computation. More specifically, after providing a simple generalization of Cohen's definition of a computer virus, we show that the malware/non-malware classification problem is undecidable under this new definition. Moreover, we show that to any formal system, there correspond infinitely many, effectively constructible, programs for which no proof can be produced by the formal system that they are either malware or non-malware programs. In other words, given any formal system, one can provide a procedure that generates, systematically, an infinite number of impossible to classify, within the formal system, programs.

关键词： Malware detection Information systems security Impossibility results recursive function theory theory of computation Turing machines

来源：评论

学校读者我要写书评

暂无评论

ALGEBRAIC ASPECTS OF THE COMPUTABLY ENUMERABLE DEGREES

引用

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA 1995年第2期92卷 617-621页

作者： SLAMAN, TA SOARE, RI Department of Mathematics University of Chicago Chicago IL 60637 USA.

A set A of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. The class of sets B which contain the same information as A under Turing computability (less than or equal to(T)) is the (Turing) degree of A, and a degree is c.e. if it contains a c.e. set. The extension of embedding problem for the c.e. degrees R = (R, <, 0, 0') asks, given finite partially ordered sets P subset of or equal to Q with least and greatest elements, whether every embedding of P into R can be extended to an embedding of Q into R. Many of the most significant theorems giving an algebraic insight into R have asserted either extension or nonextension of embeddings. We extend and unify these results and their proofs to produce complete and complementary criteria and techniques to analyze instances of extension and nonextension. We conclude that the full extension of embedding problem is decidable.

关键词： COMPUTABILITY theory recursive function theory COMPUTABLY ENUMERABLE SETS TURING COMPUTABILITY DEGREES OF UNSOLVABILITY

来源：评论

学校读者我要写书评

暂无评论

TOWARD ABSTRACT NUMERICAL-ANALYSIS

引用

JOURNAL OF THE ACM 1973年第3期20卷 399-408页

作者： MILLER, W IBM CORP THOMAS J WATSON RES CTRYORKTOWN HTSNY 10598

This paper deals with a technique for proving that certain problems of numerical analysis are numerically unsolvable. So that only methods which are natural for dealing with analytic problems may be presented, notions from recursive function theory have been avoided. Instead, the number of necessary function evaluations is taken as the measure of computational complexity. The role of topological concepts in the study of computability is examined. Last, a topological result is used to prove that a simple initial-value problem is numerically unsolvable.

关键词： computability computational complexity continuity numerical method recursive function theory uniform continuity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：