Probability densities for conditional statistics in the cubic sensor problem

This paper applies the techniques of Malliavin’s stochastic calculus of variations to Zakai’s equation for the one-dimensional cubic sensor problem in order to study the existence of densities of conditional statistics. Let {X _t} be a Brownian motion observed by a cubic sensor corrupted by white noise, and let denote the unnormalized conditional estimate of φ(X _i ). If φ₁,...,φ _n are linearly independent, and if , it is shown that the probability distribution of admits a density with respect to Lebesgue measure for anyn. This implies that, at any fixed time, the unnormalized conditional density cannot be characterized by a finite set of sufficient statistics. Research supported in part by NSF Grant No. MCS-8301880 and by the Institute for Mathematics and It Applications, Minneapolis, Minnesota.     

Extended IF逻辑的命题演算系统

Extended IF 逻辑是一阶逻辑的扩张,其主要特点是可表达量词间的相互依赖和独立关系,但其命题部分至今没有得到公理化.基于Cirquent 演算方法,给出了一个关于Cirquent 语义(命题水平)可靠完备的形式系统.该系统能够很好地解释和表达命题联结词间的相互依赖和独立关系,从而使Extended IF 逻辑在命题水平得到了真正意义上的公理化.     

Consistency,Turing Computability and Gödel’s First Incompleteness Theorem

It is well understood and appreciated that Gödel’s Incompleteness Theorems apply to sufficiently strong, formal deductive systems. In particular, the theorems apply to systems which are adequate for conventional number theory. Less well known is that there exist algorithms which can be applied to such a system to generate a gödel-sentence for that system. Although the generation of a sentence is not equivalent to proving its truth, the present paper argues that the existence of these algorithms, when conjoined with Gödel’s results and accepted theorems of recursion theory, does provide the basis for an apparent paradox. The difficulty arises when such an algorithm is embedded within a computer program of sufficient arithmetic power. The required computer program (an AI system) is described herein, and the paradox is derived. A solution to the paradox is proposed, which, it is argued, illuminates the truth status of axioms in formal models of programs and Turing machines.     

Primitive recursive selection functions for existential assertions over abstract algebras

We generalize to abstract many-sorted algebras the classical proof-theoretic result due to Parsons, Mints and Takeuti that an assertion (where P is ), provable in Peano arithmetic with induction, has a primitive recursive selection function. This involves a corresponding generalization to such algebras of the notion of primitive recursiveness. The main difficulty encountered in carrying out this generalization turns out to be the fact that equality over these algebras may not be computable, and hence atomic formulas in their signatures may not be 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.     

On mind &; Turing’s machines

Turing’s notion of human computability is exactly right not only for obtaining a negative solution of Hilbert’s Entscheidungsproblem that is conclusive, but also for achieving a precise characterization of formal systems that is needed for the general formulation of the incompleteness theorems. The broad intellectual context reaches back to Leibniz and requires a focus on mechanical procedures; these procedures are to be carried out by human computers without invoking higher cognitive capacities. The question whether there are strictly broader notions of effectiveness has of course been asked for both cognitive and physical processes. I address this question not in any general way, but rather by focusing on aspects of mathematical reasoning that transcend mechanical procedures.Section 1 discusses Gödel’s perspective on mechanical computability as articulated in his [193?], where he drew a dramatic conclusion from the undecidability of certain Diophantine propositions, namely, that mathematicians cannot be replaced by machines. That theme is taken up in the Gibbs Lecture of 1951; Gödel argues there in greater detail that the human mind infinitely surpasses the powers of any finite machine. An analysis of the argument is presented in Section 2 under the heading Beyond calculation. Section 3 is entitled Beyond discipline and gives Turing’s view of intelligent machinery; it is devoted to the seemingly sharp conflict between Gödel’s and Turing’s views on mind. Their deeper disagreement really concerns the nature of machines, and I’ll end with some brief remarks on (supra-) mechanical devices in Section 4.     

Complexity and computability of solutions to linear programming systems

Through key examples and constructs, exact and approximate, complexity, computability, and solution of linear programming systems are reexamined in the light of Khachian's new notion of (approximate) solution. Algorithms, basic theorems, and alternate representations are reviewed. It is shown that the Klee-Minty example hasnever been exponential for (exact) adjacent extreme point algorithms and that the Balinski-Gomory (exact) algorithm continues to be polynomial in cases where (approximate) ellipsoidal centered-cutoff algorithms (Levin, Shor, Khachian, Gacs-Lovasz) are exponential. By model approximation, both the Klee-Minty and the new J. Clausen examples are shown to be trivial (explicitly solvable) interval programming problems. A new notion of computable (approximate) solution is proposed together with ana priori regularization for linear programming systems. New polyhedral constraint contraction algorithms are proposed for approximate solution and the relevance of interval programming for good starts or exact solution is brought forth. It is concluded from all this that the imposed problem ignorance of past complexity research is deleterious to research progress on computability or efficiency of computation.This research was partly supported by Project NR047-071, ONR Contract N00014-80-C-0242, and Project NR047-021, ONR Contract N00014-75-C-0569, with the Center for Cybernetic Studies, The University of Texas at Austin.     

Computing Machines Can't Be Intelligent (...and Turing Said So)

According to the conventional wisdom, Turing (1950) said that computing machines can be intelligent. I don't believe it. I think that what Turing really said was that computing machines –- computers limited to computing –- can only fake intelligence. If we want computers to become genuinelyintelligent, we will have to give them enough initiative (Turing, 1948, p. 21) to do more than compute. In this paper, I want to try to develop this idea. I want to explain how giving computers more ``initiative' can allow them to do more than compute. And I want to say why I believe (and believe that Turing believed) that they will have to go beyond computation before they can become genuinely intelligent.     

About P systems with symport/antiport

It is proved that four membranes suffice to a variant of P systems with symport/antiport with maximal parallelism to generate all recursively enumerable sets of numbers. P systems with symport/antiport without maximal parallelism are also studied, considering two termination criteria.     

P Systems with Mobile Membranes

P systems with active membranes are among the central ones in membrane computing, and they were shown to be both computationally universal (able to simulate Turing machines) and computationally efficient (able to solve hard problems in polynomial time). However, in all cases, these results were obtained by making use of several powerful features, such as membrane polarization, label changing, division of non-elementary membranes, priorities, or cooperative rules. This paper contributes to the research effort of introducing a class of P systems with active membranes having none of the features mentioned above, but still preserving the power and the efficiency. The additional feature we consider instead are the operations of endocytosis and exocytosis: moving a membrane inside a neighboring membrane, or outside the membrane where it is placed. We investigate the power and the efficiency of these systems (also using membrane division) by first proving that they can simulate (with a linear slowdown and without introducing non-determinism) rewriting P systems with 2-replication, for which the universality and the possibility of solving NP-complete problems in polynomial time are known. In this way, the universality and efficiency are also obtained for our systems. We also give a direct and simple proof for the universality result – without using division rules (the proof uses nine membranes, but we do not know whether this number can be decreased).     

气液两相流界面多尺度问题可计算性研究进展

气液两相流复杂多变的界面结构在瞬态时间上具有宽广的空间尺度范围.界面多尺度问题涉及化工领域、核安全领域以及其他多个领域,其可计算性是当前国内外气液两相流领域的研究焦点之一.分析了欧拉体系下处理气液两相流相界面不连续性的两种基本模型以及湍流模拟方法对界面结构的影响.针对离散流界面尺度分布性和混合流界面跨尺度性两类多尺度问题,分析了可计算性研究面临的困境,将其归因于网格尺度的约束、几何及物理边界的缺失.重点归纳了混合流界面跨尺度性问题的计算方法以及典型应用.最后对气液两相流界面多尺度问题提出了应对策略及研究趋势,为此类问题研究提供有益的参考.