An analysis of Spector Classes associated with quasi-inductive definitions

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

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.