可计算性逻辑中CoL2系统的可判定性分析

可计算性(Computability)即算法有解性,是数学和计算机科学领域中重要的概念之一。可计算性逻辑(Computability Logic,CoL)是关于可计算性的形式理论,是一种交互的资源逻辑。其中,CoL2系统采用博弈的语义,是对经典命题逻辑的扩展,在经典命题逻辑的基础上添加了选择运算和一般原子,比经典命题逻辑更富有表达力,具有更广阔的应用前景,并且有较高的证明效率。分析了CoL2系统的可判定性,即通过提出一个算法来判断任意一个CoL2公式是否是可证明的,并且证明了该算法是多项式空间内运行的。     

Local Realizability Toposes and a Modal Logic for Computability: (Extended Abstract)

This work is a step toward developing a logic for types and computation that includes both the usual spaces of mathematics and constructions and spaces from logic and domain theory. Using realizability, we investigate a configuration of three toposes, which we regard as describing a notion of relative computability. Attention is focussed on a certain local map of toposes, which we study first axiomatically, and then by deriving a modal calculus as its internal logic. The resulting framework is intended as a setting for the logical and categorical study of relative computability.     

Transcending Turing Computability

It has been argued that neural networks and other forms of analog computation may transcend the limits of Turing-machine computation; proofs have been offered on both sides, subject to differing assumptions. In this article I argue that the important comparisons between the two models of computation are not so much mathematical as epistemological. The Turing-machine model makes assumptions about information representation and processing that are badly matched to the realities of natural computation (information representation and processing in or inspired by natural systems). This points to the need for new models of computation addressing issues orthogonal to those that have occupied the traditional theory of computation.     

Computability in Specification

In reference (Foundation of specification. Journal of Logicand Computation, 15, 951–974, 2005), the author introducesa core specification theory (CST) in order to provide a logicalframework for the design and exploration of specification languages.In this article, we formulate two highly expressive extensionsof CST. The first (CST_U) is CST + a universe of types and thesecond (CST_US) permits specifications themselves to be dataitems. Finally, we shall explore their metamathematical propertiesand, in particular, provide an interpretation into first-orderarithmetic.     

On the Complexity of Polynomial Recurrence Sequences

We consider recurrence sequences over the set of integers with generating functions being arbitrary superpositions of polynomial functions and the sg function, called polynomial recurrence sequences. We define polynomial-register (PR) machines, close to random-access machines. We prove that computations on PR machines can be modeled by polynomial recurrence sequences. On the other hand, computation of elements of a polynomial recurrence sequence can be implemented using a suitable PR machine.     

Tensor Products and Computability

We consider the problem of computability in tensor products of modules over a ring. We exhibit a finite local ring A and a pair of A-modules, given explicitly by generators and relations, with the following property. The operations in each module are computable in polynomial time, but equality in their tensor product is undecideable. The construction is of interest because it directly embeds Turing machine-like computations into the tensor product. We also present sufficient conditions for equality in tensor products to be decideable.     

Kailar逻辑缺陷的进一步讨论

责任性是电子商务安全性的基本要求之一,它要求交易各方对自己的行为负责。Kailar逻辑是专门针对电子商务责任性进行分析的逻辑。然而Kailar逻辑也存在不足。该文讨论了Kailar逻辑的一种缺陷——发生重放攻击时,Kailar逻辑不能正确分析各方的责任性,并分析了出现这种缺陷的原因,提出了改进方案。     

Computability of Digital Input Output Models

Using Church’s thesis on recursiveness of m-ary relations of integer numbers and methods for existence of solutions for Diophantine equations, the conditions on the computability of some important digital input output models are demonstrated.     

Computability versus exact computability of martingales

This note gives a simple example of a polynomial-time computable martingale that has rational values but is not exactly computable.     

Computability concepts for programming language semantics

This paper is about mathematical problems in programming language semantics and their influence on recursive function theory. We define a notion of computability on continuous higher types (for all types) and show its equivalence to effective operators. This resuit shows that our computable operators can model mathematically (i.e. extensionally) everything that can be done in an operational semantics. These new recursion theoretic concepts which are appropriate to semantics also allow us to construct Scott models for the λ-calculus which contain all and only computably elements. Depending on the choice of the initial cpo, our general theory yields a theory for either strictly determinate or else arbitrary non-deterministic objects (parallelism). The formal theory is developed in Part II of this paper. Part I gives motivation and comparison with related work.     

On Reversible Combinatory Logic

The λ-calculus is destructive: its main computational mechanism – beta reduction – destroys the redex and makes it thus impossible to replay the computational steps. Recently, reversible computational models have been studied mainly in the context of quantum computation, as (without measurements) quantum physics is inherently reversible. However, reversibility also changes fundamentally the semantical framework in which classical computation has to be investigated. We describe an implementation of classical combinatory logic into a reversible calculus for which we present an algebraic model based on a generalisation of the notion of group.     

Computability of Countable Subshifts in One Dimension

We investigate the computability of countable subshifts in one dimension, and their members. Subshifts of Cantor?CBendixson rank two contain only eventually periodic elements. Any rank two subshift in 2^? is decidable. Subshifts of rank three may contain members of arbitrary Turing degree. In contrast, effectively closed ( $\Pi^{0}_{1}$ ) subshifts of rank three contain only computable elements, but $\Pi^{0}_{1}$ subshifts of rank four may contain members of arbitrary $\Delta^{0}_{2}$ degree. There is no subshift of rank ??+1.     

Beta-Shifts,Their Languages,and Computability

For every real number β>1, the β-shift is a dynamical system describing iterations of the map x ↦ β x mod 1 and is studied intensively in number theory. Each β-shift has an associated language of finite strings of characters; properties of this language are studied for the additional insight they give into the dynamics of the underlying system.