We sketch a broadening of the Gupta-Belnap notion of a circular or revision theoretic definition into that of a more generalized form incorporating ideas of Kleene’s generalized or higher type recursion. This thereby connects the philosophically motivated, and derived, notion of a circular definition with an older form of definition by recursion using functionals, that is functions of functions, as oracles. We note that Gupta and Belnap’s notion of ‘categorical in L’ can be formulated in at least one of these (...) schemes. (shrink)

We refine the definition of II-computability of [12] so that oracles have a “consistent”, but natural, behaviour. We prove a Kleene Normal Form Theorem and closure of semi-recursive relations under ∃1. We also show that in this more inclusive computation theory Post's theorem in the arithmetical hierarchy still holds.

How do ordinals measure the strength and computational power of formal theories? This paper is concerned with the connection between ordinal representation systems and theories established in ordinal analyses. It focusses on results which explain the nature of this connection in terms of semantical and computational notions from model theory, set theory, and generalized recursion theory.

We prove two of the inequalities needed to obtain the following result on the ordinal values of ptykes of type 2, which are definable in Gödel'sT. LetG be a dilator satisfyingG(0)=ω, ∀x:G(x)≧x, and ∀η<Ω:G(η)<Ω, and letg be the ordinal function induced byG. Then sup{A(G)∣A ptyx of type 2 definable in Gödel'sT} = sup{x∣x is∑ 1 g -definable without parameters provably in KP(G)} =J (2 +Id) g (ω) (0) = the “Bachmann-Howard ordinal relative tog”. KP(G) is obtained from Kripke-Platek set theory (...) without urelements KP by adjoining a two-place relation symbolG and axioms expressing thatG is the graph of a total function from ordinals to ordinals.J D g is an iteration hierarchy defined relative tog by primitive recursion on dilators. (2 +Id)(ω) is the dilator $$\mathop {\sup }\limits_{n< \omega } (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{2} + Id)_{(n)} $$ with (2 +Id)(0)≔1 and $$(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{2} + Id)_{(n + 1)} : = (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{2} + Id)^{(2 + Id)_{(n)} } $$ . The “Bachmann-Howard ordinal relative tog” is the closure ordinal of a Bachmann hierarchy of lengthε Ω + 1, which is built on an iteration ofg as initial function.For the caseG=(1+Id)·ω, KP(G) is equivalent to Jäger's theory KPu, and the “Bachmann-Howard ordinal relative tog” is the usual “Bachmann-Howard ordinal”. For the caseG=Ξ1 KP(G) can be replaced by Jäger's theory KPi, andg can be replaced by the functionλx. x +.x + is the successor admissible ofx, andΞ 1 is the sum of all recursive dilators in an arbitrary enumeration. (shrink)

This article provides a survey of key papers that characterise computable functions, but also provides some novel insights as follows. It is argued that the power of algorithms is at least as strong as functions that can be proved to be totally computable in type-theoretic translations of subsystems of second-order Zermelo Fraenkel set theory. Moreover, it is claimed that typed systems of the lambda calculus give rise naturally to a functional interpretation of rich systems of types and to a hierarchy (...) of ordinal recursive functionals of arbitrary type that can be reduced by substitution to natural number functions. (shrink)

Truth predicates are widely believed to be capable of serving a certain logical or quasi-logical function. There is little consensus, however, on the exact nature of this function. We offer a series of formal results in support of the thesis that disquotational truth is a device to simulate higher-order resources in a first-order setting. More specifically, we show that any theory formulated in a higher-order language can be naturally and conservatively interpreted in a first-order theory with a disquotational truth or (...) truth-of predicate. In the first part of the paper we focus on the relation between truth and full impredicative sentential quantification. The second part is devoted to the relation between truth-of and full impredicative predicate quantification. (shrink)

The emperor's new mind (hereafter Emperor) is an attempt to put forward a scientific alternative to the viewpoint of according to which mental activity is merely the acting out of some algorithmic procedure. John Searle and other thinkers have likewise argued that mere calculation does not, of itself, evoke conscious mental attributes, such as understanding or intentionality, but they are still prepared to accept the action the brain, like that of any other physical object, could in principle be simulated by (...) a computer. In Emperor I go further than this and suggest that the outward manifestations ofconscious mental activity cannot even be properly simulated by calculation. To support this view, I use various arguments to show that the results of mathematical insight, in particular, do not seem to be obtained algorithmically. The main thrust ofthis work, however, is to present an overview ofthe present state of physical understanding and to show that an important gap exists at the point where, quantum and classical physics meet, as well as to speculate on how the conscious brain might be taking advantage ofwhatever new physics is needed to fill this gap to achieve its nonalgorithmic effects. (shrink)

In this work we show that every structure [MATHEMATICAL SCRIPT CAPITAL A] can be expanded to a partial structure [MATHEMATICAL SCRIPT CAPITAL A]* with universal functions for the class of polynomials on [MATHEMATICAL SCRIPT CAPITAL A]*. We can embed [MATHEMATICAL SCRIPT CAPITAL A]* monomorphically in a total structure [MATHEMATICAL SCRIPT CAPITAL A]º that preserves universal functions of [MATHEMATICAL SCRIPT CAPITAL A]* and that is universal among such structures, i.e. [MATHEMATICAL SCRIPT CAPITAL A]º can be homomorphically embedded in every total structure (...) that preserves universal functions of [MATHEMATICAL SCRIPT CAPITAL A]*. Universal functions are the starting point for developing recursion theoretic tools in an [MATHEMATICAL SCRIPT CAPITAL A]* that satisfies some simple additional conditions. (shrink)

I propose that empirical procedures, like computational procedures, are justified in terms of truth-finding efficiency. I contrast the idea with more standard philosophies of science and illustrate it by deriving Ockham's razor from the aim of minimizing dramatic changes of opinion en route to the truth.

We survey the theory of Mucnik and Medvedev degrees of subsets of $^{\omega}{\omega}$with particular attention to the degrees of $\Pi_{1}^{0}$ subsets of $^{\omega}2$. Sections 1-6 present the major definitions and results in a uniform notation. Sections 7-6 present proofs, some more complete than others, of the major results of the subject together with much of the required background material.

If □ is conceived as an operator, i.e., an expression that gives applied to a formula another formula, the expressive power of the language is severely restricted when compared to a language where □ is conceived as a predicate, i.e., an expression that yields a formula if it is applied to a term. This consideration favours the predicate approach. The predicate view, however, is threatened mainly by two problems: Some obvious predicate systems are inconsistent, and possible-worlds semantics for predicates of (...) sentences has not been developed very far. By introducing possible-worlds semantics for the language of arithmetic plus the unary predicate □, we tackle both problems. Given a frame (W, R) consisting of a set W of worlds and a binary relation R on W, we investigate whether we can interpret □ at every world in such a way that □ $\ulcorner A \ulcorner$ holds at a world ᵆ ∊ W if and only if A holds at every world $\upsilon$ ∊ W such that ᵆR $\upsilon$ . The arithmetical vocabulary is interpreted by the standard model at every world. Several 'paradoxes' (like Montague's Theorem, Gödel's Second Incompleteness Theorem, McGee's Theorem on the ω-inconsistency of certain truth theories, etc.) show that many frames, e.g., reflexive frames, do not allow for such an interpretation. We present sufficient and necessary conditions for the existence of a suitable interpretation of □ at any world. Sound and complete semi-formal systems, corresponding to the modal systems K and K4, for the class of all possible-worlds models for predicates and all transitive possible-worlds models are presented. We apply our account also to nonstandard models of arithmetic and other languages than the language of arithmetic. (shrink)

This paper investigates the conditions under which diagonal sentences can be taken to constitute paradigmatic cases of self-reference. We put forward well-motivated constraints on the diagonal operator and the coding apparatus which separate paradigmatic self-referential sentences, for instance obtained via Gödel’s diagonalization method, from accidental diagonal sentences. In particular, we show that these constraints successfully exclude refutable Henkin sentences, as constructed by Kreisel.

This paper presents an approach to truth and the Liar paradox which combines elements of context dependence and hierarchy. This approach is developed formally, using the techniques of model theory in admissible sets. Special attention is paid to showing how starting with some ideas about context drawn from linguistics and philosophy of language, we can see the Liar sentence to be context dependent. Once this context dependence is properly understood, it is argued, a hierarchical structure emerges which is neither ad (...) hoc nor unnatural. (shrink)