An analysis of Spector Classes associated with quasi-inductive definitions

与准归纳定义相关的 Spector 类的分析

• 批准号: EP/G020841/1
• 负责人: Philip Welch
• 金额: $ 1.6万
• 依托单位: University of Bristol
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2008
• 资助国家: 英国
• 起止时间: 2008 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FG020841%2F1
• 关键词: analysis; Spector; Classes; associated; quasi

Various authors have responded in differing ways to the results of Tarski and Goedel on theundefinability of truth and incompleteness of formal systems, which ruled out the possibility that one can have a formula in a deductive system that defines truth completely. These theories left open the door to the possibility that we can partially define truth by some formula. The two most widely known approaches to this were designed by Kripke in the 70's and Gupta and Belnap in the 80's and 90's. It is also well known that we can give a description of the sets of sentences definably true in a system such as Kripke's by using two person perfect information infinite games. (A strategy for one of the players tells them how to move. A winning strategy ensures they will always win even if there are infinitely many moves on the board.) An 'open game' is one essentially in which one player can win in finitely many stages (although the other player - playing in to the `closed' set - may have to play infinitely often in order to win).These are known to be 'determined' (that is one of the players must have a winning strategy). Kripke's truth sets can be characterised by means of such simple open games.The proposer has looked at how Gupta & Belnap's theory of circular definitions, a form of 'quasi-inductive' definition, can be embedded in a theory involving determinacystatements for games of greater complexity than open/closed in the arithmetic hierarchy. We thus know there is a level of the arithmetic hierarchy whose determinacy allows such circular definitions as those of Gupta-Benap to take place. One mathematical question we should like to address is to give a proper answer as to how much infinity is required for thetheory of quasi-inductive definitions to work . This is made precise through asking for precise games whose determinacy allows such definitions to close-off or reach a stable state ( fixed points in general cannot occur). A second mathematical question asks how we can reverse the first question: assuming Gupta and Belnap's revision theory of circular definitions always stabilizes, then how strong is this in terms of theories of analysis?Both the theory of generalised inductive definitions, and the theories of truth mentionedhas been seen quite recently to be formally equivalent with a transfinite computational model.This is an exciting occurrence of `convergence' between radically different areas, coming as they do from quite different disciplines. Here we imagine a standard Turing machine or computer, being allowed to run over tranfinite lengths of time. What could such a conceptual or 'virtual' machine compute? Just as for ordinary Turing machines, we can delimit their computational power. The analysis of what is computable turns out to be one of a class of sets called Spector Classes .The project will analysis the Spector class of sets of real numbers associated with thesegames, or equivalently these computational models, or again, these philosophical theories of truth.

不同的作者以不同的方式回应了塔斯基和哥德尔关于真理的不可定义性和形式系统的不完备性的结果，这些结果排除了人们可以在演绎系统中完全定义真理的公式的可能性。这些理论为我们可以通过某种公式部分定义真理的可能性打开了大门。最广为人知的两种方法是由Kripke在70年代和Gupta和Belnap在80年代和90年代设计的。众所周知，我们可以用两人完全信息无限对策来描述Kripke系统中的可定义为真的句子集。（其中一个玩家的策略告诉他们如何移动。一个获胜的策略可以确保他们总是赢，即使棋盘上有无限多步棋。）一个“开放游戏”本质上是一个游戏，其中一个玩家可以在许多阶段中获胜（尽管另一个玩家-在“封闭”集合中玩-为了获胜可能必须玩无限次）。这些被称为“确定”（即其中一个玩家必须有获胜策略）。Kripke的真值集可以通过这种简单的开放游戏来表征。提议者已经研究了如何古普塔和贝尔纳普的循环定义理论，一种“准归纳”定义的形式，可以嵌入到一个理论中，该理论涉及比算术层次中的开/闭更复杂的游戏的确定性陈述。因此，我们知道，在算术层次中有一个层次，它的确定性允许古普塔-贝纳普那样的循环定义发生。一个数学问题，我们应该解决的是要给一个适当的答案，有多少无穷大是需要thethetheory的准归纳定义的工作。这是通过要求精确的游戏，其确定性允许这样的定义关闭或达到稳定状态（固定点一般不会发生）。第二个数学问题是，我们如何能够逆转第一个问题：假设古普塔和贝尔纳普的循环定义修正理论总是稳定的，那么这在分析理论方面有多强？无论是广义归纳定义理论，还是所提到的真理论，最近都被认为是与超限计算模型形式上等价的。这是一个令人兴奋的“趋同”现象，发生在完全不同的领域之间，因为它们来自完全不同的学科。在这里，我们想象一个标准的图灵机或计算机，被允许运行超过无限长的时间。这样一个概念上的或“虚拟”的机器能计算什么呢？就像普通的图灵机一样，我们可以定义它们的计算能力。分析什么是可计算的结果是一个所谓的斯佩克特类的集合类。该项目将分析斯佩克特类的集合的真实的数字与这些游戏，或等效这些计算模型，或再次，这些哲学理论的真理。

项目成果

Weak systems of determinacy and arithmetical quasi-inductive definitions

弱确定性系统和算术准归纳定义

• DOI: 10.2178/jsl/1305810756
• 发表时间: 2014
• 期刊: The Journal of Symbolic Logic
• 作者: P. D. Welch

HYPERMACHINES

• DOI: 10.2178/jsl/1305810767
• 发表时间: 2011-06-01
• 期刊: JOURNAL OF SYMBOLIC LOGIC
• 影响因子: 0.6
• 作者: Friedman, Sy-David;Welch, P. D.
• 通讯作者: Welch, P. D.

Unconventional Computation

非常规计算

• DOI: 10.1007/978-3-642-03745-0_11
• 发表时间: 2009
• 作者: Welch P

Games for Truth

真理游戏

• DOI: 10.2178/bsl/1255526080
• 发表时间: 2014
• 期刊: The Bulletin of Symbolic Logic
• 作者: Welch P

Computability in Context - Computation and Logic in the Real World

上下文中的可计算性 - 现实世界中的计算和逻辑

• DOI: 10.1142/9781848162778_0012
• 发表时间: 2011
• 作者: Welch P