Linearity and iterator types for Gödel’s System

System Open image in new window is a linear λ-calculus with numbers and an iterator, which, although imposing linearity restrictions on terms, has all the computational power of Gödel’s System  Open image in new window . System Open image in new window owes its power to two features: the use of a closed reduction strategy (which permits the construction of an iterator on an open function, but only iterates the function after it becomes closed), and the use of a liberal typing rule for iterators based on iterative types. In this paper, we study these new types, and show how they relate to intersection types. We also give a sound and complete type reconstruction algorithm for System  Open image in new window .     

Complexity-Theoretic Hierarchies Induced by Fragments of Gödel’s T

We introduce two hierarchies of unknown ordinal height. The hierarchies are induced by natural fragments of a calculus based on finite types and Gödel’s T, and all the classes in the hierarchies are uniformly defined without referring to explicit bounds. Deterministic complexity classes like logspace, p, pspace, linspace and exp are captured by the hierarchies. Typical subrecursive classes are also captured, e.g. the small relational Grzegorczyk classes ? _* ⁰ , ? _* ¹ and ? _* ² .     

Chaitin Ω numbers,Solovay machines,and Gödel incompleteness

Computably enumerable (c.e.) reals can be coded by Chaitin machines through their halting probabilities. Tuning Solovay's construction of a Chaitin universal machine for which ZFC (if arithmetically sound) cannot determine any single bit of the binary expansion of its halting probability, we show that every c.e.~random real is the halting probability of a universal Chaitin machine for which ZFC cannot determine more than its initial block of 1 bits—as soon as you get a 0, it is all over. Finally, a constructive version of Chaitin information-theoretic incompleteness theorem is proven.     

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.     

Gdel语言类型系统

Gdel语言是一种说明性逻辑程序设计语言。该语言基于一阶逻辑,引入了一个多态多类的类型系统和多种新的语言成分,支持抽象数据类型和模块化程序设计等技术,语言本身也具有很强的说明性语义。详细介绍了Gdel语言的类型系统及其构造,对在逻辑程序设计语言中引入类型系统的作用进行了一些深入的分析和讨论。     

On equitable colouring of Knödel graphs

The notion of equitable colouring was introduced by Meyer in 1973. In this paper we find the equitable chromatic number χ₌ for the line graph of Knödel graphs L(W_{Δ, n}), central graph of Knödel graphs C(W_{Δ, n}) and corona graph of Knödel graphs W_{Δ, m}° W_{Δ, n}. As a by-product we obtain a new class of graphs that confirm Equitable Colouring Conjecture.     

Computer Proofs in Gödel’s Class Theory with Equational Definitions for Composite and Cross

Some basic theorems about composition and other key constructs of set theory were proved using McCunes computer program OTTER, building on Quaifes modification of Gödels class theory. Our proofs use equational definitions in terms of Gödels flip and rotate functors. A new way to prove the composition of homomorphisms theorem is also presented.     

G觟del语言的说明性语义简述

Godel语言是在Prolog语言基础上发展而来的一种新型逻辑程序设计语言。本文基于类型一阶谓词逻辑的模型论,阐明了Godel语言的说明性语义,为该语言的实现模型奠定了一定的理论基础。     

G(o)del语言类型系统

G(o)del语言是一种说明性逻辑程序设计语言.该语言基于一阶逻辑,引入了一个多态多类的类型系统和多种新的语言成分,支持抽象数据类型和模块化程序设计等技术,语言本身也具有很强的说明性语义.详细介绍了G(o)del语言的类型系统及其构造,对在逻辑程序设计语言中引入类型系统的作用进行了一些深入的分析和讨论.     

修正的n值Gdel逻辑系统的随机化

利用赋值集的随机化方法,在修正的n值Gdel逻辑系统中提出了公式的随机真度和随机距离的概念,建立了随机度量空间。指出当取均匀概率时,随机真度就转化为计量逻辑学中的真度,建立了更一般的随机逻辑度量空间。     

G?del n值命题逻辑系统的真度理论

首先在G?del n值命题逻辑系统中添加了新的连接词Δ,～,给出了G?del n值命题逻辑系统中命题公式间的真度、相似度和伪距离的定义;讨论了在该系统下它们的一些相关性质,并给出了相应的证明。     

Gdel区间值逻辑系统的广义拟重言式

吴洪博博士将王国俊教授在R0逻辑系统中的广义重言式理论推广到Gdel逻辑系统中,通过定义两个同构映射,得到其逻辑系统F(S)的一个分划。将这一理论推广到区间值模糊命题逻辑系统中,定义了两个新的区间同构映射,最终得到区间值逻辑系统F(S)的一个分划。     

Gdel语言编译时类型处理技术研究

Gdel是一种发展中的逻辑程序设计语言,目前还没有开发出编译器。Gdel语言的类型系统独特于通常的逻辑程序设计语言,语义上已初步形成了相应的描述方法,建立了严格的理论基础。按照传统的方法,逻辑程序的运行机制和Gdel语言的多态性决定了一些变量的类型和语义只能在运行时才能确定,把这类变量的类型检查放到程序运行中处理,势必增加许多额外的计算。提出了一种处理Gdel语言类型系统的编译技术。针对语言的类型,对其相关语法进行适当修改,通过类型推断,把变量类型的检查工作提前到编译阶段完成,可以较好地处理其变量类型的语义问题,同时减少了运行时类型检查工作,从而提高程序的运行效率。     

Gdel语言对现代软件工程方法的支持

文章以一种新型的逻辑程序设计语言——G+del语言为例,对逻辑程序设计语言与现代软件工程主要思想和方法的结合情况进行了初步探讨。G,del语言通过引入模块系统、类型系统和延迟计算机制等不同于以往逻辑程序的新机制,能够支持现代软件设计的一些主流方法。模块系统提供了组织大规模程序的方法,并通过结合类型系统实现了对抽象数据类型程序设计的支持,从而能够支持面向对象程序设计;延迟计算则使利用该语言所编制的软件在可重用性方面获得提升。     

G(o)del语言的说明性语义简述

Godel语言是在Prolog语言基础上发展而来的一种新型逻辑程序设计语言。本文基于类型一阶谓词逻辑的模型论,阐明了Godel语言的说明性语义,为该语言的实现模型奠定了一定的理论基础。     

Non-determinism in Gödel’s System <Emphasis Type="Italic">T</Emphasis>

The calculus T^? is a successor-free version of Gödel’s T. It is well known that a number of important complexity classes, like e.g. the classes logspace, \(\textsc{p}\), \(\textsc{linspace}\), \(\textsc{etime}\) and \(\textsc{pspace}\), are captured by natural fragments of T^? and related calculi. We introduce the calculus T^∽, which is a non-deterministic variant of T^?, and compare the computational power of T^∽ and T^?. First, we provide a denotational semantics for T^∽ and prove this semantics to be adequate. Furthermore, we prove that \(\textsc{linspace}\subseteq \mathcal {G}^{\backsim }_{0} \subseteq \textsc{linspace}\) and \(\textsc{etime}\subseteq \mathcal {G}^{\backsim }_{1} \subseteq \textsc{pspace}\) where \(\mathcal {G}^{\backsim }_{0}\) and \(\mathcal {G}^{\backsim }_{1}\) are classes of problems decidable by certain fragments of T^∽. (It is proved elsewhere that the corresponding fragments of T^? equal respectively \(\textsc{linspace}\) and \(\textsc{etime}\).) Finally, we show a way to interpret T^∽ in T^?.     

Einige Kommentare zu einer bin-packing Aufgabe von W. Knödel

W. Knödel has considered a bin-packing problem which can be seen within the context of random walks. The height of a random walk is a well studied parameter which can also be defined in Knödels model. Its average is computed and shown to be of order \(\sqrt n \) . The methods include singularity analysis of generating functions as well as Mellin transforms.     

控制系统的鲁棒性与Gӧdel不完备定理*

“鲁棒性”是Kalman体系中依靠（A,B,C）模型的理论与控制工程实际之间矛盾的产物.本文试图用G?del“不完备定理”来说明,解决“鲁棒性”问题必须摆脱（A,B,C）束缚和线性束缚.本文利用简单的非线性特性提出了独立于（A,B,C）的信号处理及控制的办法.为了适应新的控制系统：“设计理论”,需要对现行控制理论中有效概念予以重新考虑.本文尝试给出新的“适应性”、“鲁棒性”概念和系统描述方法.     

A note on pathria’s model of the universe as a black hole

Pathria has shown that, for the certain values of the cosmological constant, a pressureless closed Friedmann-Robertson-Walker universe can be the interior of a Schwarzschild black hole. We examine Pathria’s model from the point of view of matching of two different spacetimes through a null hypersurface. We first regard the event horizon of the black hole, which in Pathria’s model is identified with the radius of the universe at the point of its maximum expansion, as a null hypersurface separating the FRW interior from the vacuum Schwarzschild exterior, and then use the null shell formalism for it. It turns out that matching is not smooth, and in fact, the null hypersurface is the history of a null shell admitting a surface pressure.