It is quite well-known from Kurt G¨odel’s (1931) ground-breaking Incompleteness Theorem that rudimentary relations (i.e., those definable by bounded formulae) are primitive recursive, and that primitive recursive functions are representable in sufficiently strong arithmetical theories. It is also known, though perhaps not as well-known as the former one, that some primitive recursive relations are not rudimentary. We present a simple and elementary proof of this fact in the first part of the paper. In the second part, (...) we review some possible notions of representability of functions studied in the literature, and give a new proof of the equivalence of the weak representability with the (strong) representability of functions in sufficiently strong arithmetical theories. (shrink)

Textbook on Gödel’s incompleteness theorems and computability theory, based on the Open Logic Project. Covers recursive function theory, arithmetization of syntax, the first and second incompleteness theorem, models of arithmetic, second-order logic, and the lambda calculus.

By formalizing some classical facts about provably total functions of intuitionistic primitive recursive arithmetic (iPRA), we prove that the set of decidable formulas of iPRA and of iΣ1+ (intuitionistic Σ1-induction in the language of PRA) coincides with the set of its provably ∆1-formulas and coincides with the set of its provably atomic formulas. By the same methods, we shall give another proof of a theorem of Marković and De Jongh: the decidable formulas of HA are its provably ∆1-formulas.

This paper sums up the fundamental features of intelligence through the common features stated by various definitions of "intelligence": Intelligence is the ability of achieving systematic goals (functions) of brain and nerve system through selecting, and artificial intelligence or machine intelligence is an imitation of life intelligence or a replication of features and functions. Based on the definition mentioned above, this paper discusses and summarizes the development routes of ideas on computable intelligence, including Godel's "universal recursive function", (...) the computation activities of "selection", recursive function and Turing machine, mathematical expression of computable intelligence, core nature of computable intelligence, and computability and strong artificial intelligence. At the end of this paper is the conclusion drawn by the authors. (shrink)

Corcoran’s 27 entries in the 1999 second edition of Robert Audi’s Cambridge Dictionary of Philosophy [Cambridge: Cambridge UP]. -/- ancestral, axiomatic method, borderline case, categoricity, Church (Alonzo), conditional, convention T, converse (outer and inner), corresponding conditional, degenerate case, domain, De Morgan, ellipsis, laws of thought, limiting case, logical form, logical subject, material adequacy, mathematical analysis, omega, proof by recursion, recursive function theory, scheme, scope, Tarski (Alfred), tautology, universe of discourse. -/- The entire work is available online free at more (...) than one website. Paste the whole URL. http://archive.org/stream/RobertiAudi_The.Cambridge.Dictionary.of.Philosophy/Robert.Audi_The.Cambrid ge.Dictionary.of.Philosophy -/- The 2015 third edition will be available soon. Before you think of buying it read some reviews on Amazon and read reviews of its competition: For example, my review of the 2008 Oxford Companion to Philosophy, History and Philosophy of Logic,29:3,291-292. URL: http://dx.doi.org/10.1080/01445340701300429 -/- Some of the entries have already been found to be flawed. For example, Tarski’s expression ‘materially adequate’ was misinterpreted in at least one article and it was misused in another where ‘materially correct’ should have been used. The discussion provides an opportunity to bring more flaws to light. -/- Acknowledgements: Each of these entries was presented at meetings of The Buffalo Logic Dictionary Project sponsored by The Buffalo Logic Colloquium. The members of the colloquium read drafts before the meetings and were generous with corrections, objections, and suggestions. Usually one 90-minute meeting was devoted to one entry although in some cases, for example, “axiomatic method”, took more than one meeting. Moreover, about half of the entries are rewrites of similarly named entries in the 1995 first edition. Besides the help received from people in Buffalo, help from elsewhere was received by email. We gratefully acknowledge the following: José Miguel Sagüillo, John Zeis, Stewart Shapiro, Davis Plache, Joseph Ernst, Richard Hull, Concha Martinez, Laura Arcila, James Gasser, Barry Smith, Randall Dipert, Stanley Ziewacz, Gerald Rising, Leonard Jacuzzo, George Boger, William Demopolous, David Hitchcock, John Dawson, Daniel Halpern, William Lawvere, John Kearns, Ky Herreid, Nicolas Goodman, William Parry, Charles Lambros, Harvey Friedman, George Weaver, Hughes Leblanc, James Munz, Herbert Bohnert, Robert Tragesser, David Levin, Sriram Nambiar, and others. -/- . (shrink)

I here investigate the sense in which diagonalization allows one to construct sentences that are self-referential. Truly self-referential sentences cannot be constructed in the standard language of arithmetic: There is a simple theory of truth that is intuitively inconsistent but is consistent with Peano arithmetic, as standardly formulated. True self-reference is possible only if we expand the language to include function-symbols for all primitive recursive functions. This language is therefore the natural setting for investigations of self-reference.

Chapin reviewed this 1972 ZEITSCHRIFT paper that proves the completeness theorem for the logic of variable-binding-term operators created by Corcoran and his student John Herring in the 1971 LOGIQUE ET ANALYSE paper in which the theorem was conjectured. This leveraging proof extends completeness of ordinary first-order logic to the extension with vbtos. Newton da Costa independently proved the same theorem about the same time using a Henkin-type proof. This 1972 paper builds on the 1971 “Notes on a Semantic Analysis of (...) Variable Binding Term Operators” (Co-author John Herring), Logique et Analyse 55, 646–57. MR0307874 (46 #6989). A variable binding term operator (vbto) is a non-logical constant, say v, which combines with a variable y and a formula F containing y free to form a term (vy:F) whose free variables are exact ly those of F, excluding y. Kalish-Montague 1964 proposed using vbtos to formalize definite descriptions “the x: x+x=2”, set abstracts {x: F}, minimization in recursive function theory “the least x: x+x>2”, etc. However, they gave no semantics for vbtos. Hatcher 1968 gave a semantics but one that has flaws described in the 1971 paper and admitted by Hatcher. In 1971 we give a correct semantic analysis of vbtos. We also give axioms for using them in deductions. And we conjecture strong completeness for the deductions with respect to the semantics. The conjecture, proved in this paper with Hatcher’s help, was proved independently about the same time by Newton da Costa. (shrink)

We describe a software system for the analysis of defined benefit actuarial plans. The system uses a recursive formulation of the actuarial stochastic processes to implement precise and efficient computations of individual and group cash flows.

It is well known that the following features hold of AR + T under the strong Kleene scheme, regardless of the way the language is Gödel numbered: 1. There exist sentences that are neither paradoxical nor grounded. 2. There are 2ℵ0 fixed points. 3. In the minimal fixed point the weakly definable sets (i.e., sets definable as {n∣ A(n) is true in the minimal fixed point where A(x) is a formula of AR + T) are precisely the Π1 1 sets. (...) 4. In the minimal fixed point the totally defined sets (sets weakly defined by formulae all of whose instances are true or false) are precisely the ▵1 1 sets. 5. The closure ordinal for Kripke's construction of the minimal fixed point is ωCK 1. In contrast, we show that under the weak Kleene scheme, depending on the way the Gödel numbering is chosen: 1. There may or may not exist nonparadoxical, ungrounded sentences. 2. The number of fixed points may be any positive finite number, ℵ0, or 2ℵ0 . 3. In the minimal fixed point, the sets that are weakly definable may range from a subclass of the sets 1-1 reducible to the truth set of AR to the Π1 1 sets, including intermediate cases. 4. Similarly, the totally definable sets in the minimal fixed point range from precisely the arithmetical sets up to precisely the ▵1 1 sets. 5. The closure ordinal for the construction of the minimal fixed point may be ω, ωCK 1, or any successor limit ordinal in between. In addition we suggest how one may supplement AR + T with a function symbol interpreted by a certain primitive recursive function so that, irrespective of the choice of the Godel numbering, the resulting language based on the weak Kleene scheme has the five features noted above for the strong Kleene language. (shrink)

This is a non-technical version of "The Decision Problem for Effective Procedures." The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that reason, the Church–Turing thesis (that the effectively calculable functions on natural numbers are exactly the general recursive functions), cannot be proved. However, it is logically provable from the (...) notion of an effective procedure--without reliance on any (partially) mathematical thesis or conjecture concerning effective procedures, such as the Church–Turing thesis--that the class of effective procedures is undecidable, i.e., that no effective procedure is possible for ascertaining whether a given procedure is effective. The proof does not appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of such a procedure. Though this undecidability result itself is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure is, in fact, a decision procedure, i.e., effective—for example, that it invariably terminates with the correct verdict. (shrink)

Why are natural theories pre-well-ordered by consistency strength? In previous work, an approach to this question was proposed. This approach was inspired by Martin's Conjecture, one of the most prominent conjectures in recursion theory. Fixing a reasonable subsystem $T$ of arithmetic, the goal was to classify the recursive functions that are monotone with respect to the Lindenbaum algebra of $T$. According to an optimistic conjecture, roughly, every such function must be equivalent to an iterate $\mathsf{Con}_T^\alpha$ of the consistency (...) operator ``in the limit'' within the ultrafilter of sentences that are true in the standard model. In previous work the author established the first case of this optimistic conjecture; roughly, every recursive monotone function is either as weak as the identity operator in the limit or as strong as $\mathsf{Con}_T$ in the limit. Yet in this note we prove that this optimistic conjecture fails already at the next step; there are recursive monotone functions that are neither as weak as $\mathsf{Con}_T$ in the limit nor as strong as $\mathsf{Con}_T^2$ in the limit. In fact, for every $\alpha$, we produce a function that is cofinally equivalent to $\mathsf{Con}^\alpha_T$ yet cofinally equivalent to $\mathsf{Con}_T$. (shrink)

Inductively defined structures are ubiquitous in mathematics; their specification is unambiguous and their properties are powerful. All fields of mathematical logic feature these structures prominently: the formula of a language, the set of theorems, the natural numbers, the primitive recursive functions, the constructive number classes and segments of the cumulative hierarchy of sets. -/- This dissertation gives a mathematical characterization of a species of inductively defined structures, called accessible domains, which include all of the above examples except the (...) set of theorems. The concept of an accessible domain comes from Wilfried Sieg's analysis of proof-theoretic practices, starting with his dissertation. In particular, he noticed the special epistemological character of elements of an accessible domain: they can always be uniquely identified with their build-up. Generally, the unique build-up of elements justifies the principles of induction and recursion. -/- I use category theory to give an abstract characterization of accessible domains. I claim that accessible domains are all instances of initial algebras for endofunctors. Grounded in the historical roots of Sieg's discussions, this dissertation shows how the properties of initial algebras for endofunctors and accessible domains coincide in a satisfying and natural way. -/- Filling out this characterization, I show how important examples of accessible domains fit into this broad characterization. I first characterize some accessible domains by relatively simple functors (e.g. finite, polynomial, those that preserve certain colimits) where we can see how iterating the functor can produce the accessible domain. Then I describe accessible domains that result from more involved specifications (e.g. ordinals and segments of the cumulative hierarchies associated with CZF, IZF, and ZF) by relying heavily on algebraic set theory. I end with a discussion of some of the methodological features of category theory in particular that helped characterize accessible domains. (shrink)

Although Kurt Gödel does not figure prominently in the history of computabilty theory, he exerted a significant influence on some of the founders of the field, both through his published work and through personal interaction. In particular, Gödel’s 1931 paper on incompleteness and the methods developed therein were important for the early development of recursive function theory and the lambda calculus at the hands of Church, Kleene, and Rosser. Church and his students studied Gödel 1931, and Gödel taught a (...) seminar at Princeton in 1934. Seen in the historical context, Gödel was an important catalyst for the emergence of computability theory in the mid 1930s. (shrink)

-/- A variable binding term operator (vbto) is a non-logical constant, say v, which combines with a variable y and a formula F containing y free to form a term (vy:F) whose free variables are exact ly those of F, excluding y. -/- Kalish-Montague proposed using vbtos to formalize definite descriptions, set abstracts {x: F}, minimalization in recursive function theory, etc. However, they gave no sematics for vbtos. Hatcher gave a semantics but one that has flaws. We give a (...) correct semantic analysis of vbtos. We also give axioms for using them in deductions. And we conjecture strong completeness for the deductions with respect to the semantics. The conjecture was later proved independently by the authors and by Newton da Costa. -/- The expression (vy:F) is called a variable bound term (vbt). In case F has only y free, (vy:F) has the syntactic propreties of an individual constant; and under a suitable interpretation of the language vy:F) denotes an individual. By a semantic analysis of vbtos we mean a proposal for amending the standard notions of (1) "an interpretation o f a first -order language" and (2) " the denotation of a term under an interpretation and an assignment", such that (1') an interpretation o f a first -order language associates a set-theoretic structure with each vbto and (2') under any interpretation and assignment each vb t denotes an individual. (shrink)

The Turing machine halting problem can be explained by several factors, including arithmetic logic irreversibility and memory erasure, which contribute to computational uncertainty due to information loss during computation. Essentially, this means that an algorithm can only preserve information about an input, rather than generate new information. This uncertainty arises from characteristics such as arithmetic logical irreversibility, Landauer's principle, and memory erasure, which ultimately lead to a loss of information and an increase in entropy. To measure this uncertainty and loss (...) of information, the concept of arithmetic logical entropy can be used. The Turing machine and its equivalent, general recursive functions can be understood through the λ calculus and the Turing/Church thesis. However, there are certain recursive functions that cannot be fully understood or predicted by other algorithms due to the loss of information during logical-arithmetic operations. In other words, the behaviour of these functions cannot be completely determined at every stage of the computation due to a lack of information in their definition. While there are some cases where the behaviour of recursive functions is highly predictable, the lack of information in most cases makes it impossible for algorithms to determine if a program will halt or not. This inability to predict the outcome of the computation is the essence of the halting problem of the Turing machine. Even in cases where more information is available about the program, it is still difficult to determine with certainty if the program will halt or not. This also highlights the importance of the Turing oracle machine, which introduces information from outside the computation to compensate for the lack of information and ultimately decide the result of the computation. (shrink)

Complexity is a relatively new field of study that is still heavily influenced by philosophy. However, with the advent of modern computing, it has become easier to conduct thorough investigations of complex systems using computational simulations. Despite significant progress, there remain certain characteristics of complex systems that are difficult to comprehend. To better understand these features, information can be applied using simple models of complex systems. The concepts of Shannon's information theory, Kolgomorov complexity, and logical depth are helpful in this (...) regard. Computational mathematical models based on recursive processes, recursive functions, and information in functions offer new insights into complexity by exploring its connection with irreversibility and the loss of information. Through these models, it is possible to see complexity as a transformation of input information through algorithmic computation, with time, logical depth, and information loss serving as key factors in understanding the process. (shrink)

‎A universal schema for diagonalization was popularized by N. S‎. ‎Yanofsky (2003)‎, ‎based on a pioneering work of F.W‎. ‎Lawvere (1969)‎, ‎in which the existence of a (diagonolized-out and contradictory) object implies the existence of a fixed-point for a certain function‎. ‎It was shown that many self-referential paradoxes and diagonally proved theorems can fit in that schema‎. ‎Here‎, ‎we fit more theorems in the universal‎ ‎schema of diagonalization‎, ‎such as Euclid's proof for the infinitude of the primes and new proofs (...) of G. Boolos (1997) for Cantor's theorem on the non-equinumerosity of a set with its powerset‎. ‎Then‎, ‎in Linear Temporal Logic‎, ‎we show the non-existence of a fixed-point in this logic whose proof resembles the argument of Yablo's paradox (1985‎, ‎1993)‎. ‎Thus‎, ‎Yablo's paradox turns for the first time into a genuine mathematico-logical theorem in the framework of Linear Temporal Logic‎. ‎Again the diagonal schema of the paper is used in this proof; and it is also shown that G. Priest's inclosure schema (1997) can fit in our universal diagonal / fixed-point schema‎. ‎We also show the existence of dominating (Ackermann-like) functions (which dominate a given countable set of functions‎, ‎such as primitive recursive functions) in the schema. (shrink)

In Zettel, Wittgenstein considered a modified version of Cantor’s diagonal argument. According to Wittgenstein, Cantor’s number, different with other numbers, is defined based on a countable set. If Cantor’s number belongs to the countable set, the definition of Cantor’s number become incomplete. Therefore, Cantor’s number is not a number at all in this context. We can see some examples in the form of recursive functions. The definition "f(a)=f(a)" can not decide anything about the value of f(a). The definiton (...) is incomplete. The definition of "f(a)=1+f(a)" can not decide anything about the value of f(a) too. The definiton is incomplete.<br><br>According to Wittgenstein, the contradiction, in Cantor's proof, originates from the hidden presumption that the definition of Cantor’s number is complete. The contradiction shows that the definition of Cantor’s number is incomplete. <br><br>According to Wittgenstein’s analysis, Cantor’s diagonal argument is invalid. But different with Intuitionistic analysis, Wittgenstein did not reject other parts of classical mathematics. Wittgenstein did not reject definitions using self-reference, but showed that this kind of definitions is incomplete.<br><br>Based on Thomson’s diagonal lemma, there is a close relation between a majority of paradoxes and Cantor’s diagonal argument. Therefore, Wittgenstein’s analysis on Cantor’s diagonal argument can be applied to provide a unified solution to paradoxes. (shrink)

We model infinite regress structures -not arguments- by means of ungrounded recursively defined functions in order to show that no such structure can perform the task of providing determination to the items composing it, that is, that no determination process containing an infinite regress structure is successful.

The abstract basis of modern computation is the formal description of a finite state machine, the Universal Turing Machine, based on manipulation of integers and logic symbols. In this contribution to the discourse on the computer-brain analogy, we discuss the extent to which analog computing, as performed by the mammalian brain, is like and unlike the digital computing of Universal Turing Machines. We begin with ordinary reality being a permanent dialog between continuous and discontinuous worlds. So it is with computing, (...) which can be analog or digital, and is often mixed. The theory behind computers is essentially digital, but efficient simulations of phenomena can be performed by analog devices; indeed, any physical calculation requires implementation in the physical world and is therefore analog to some extent, despite being based on abstract logic and arithmetic. The mammalian brain, comprised of neuronal networks, functions as an analog device and has given rise to artificial neural networks that are implemented as digital algorithms but function as analog models would. Analog constructs compute with the implementation of a variety of feedback and feedforward loops. In contrast, digital algorithms allow the implementation of recursive processes that enable them to generate unparalleled emergent properties. We briefly illustrate how the cortical organization of neurons can integrate signals and make predictions analogically. While we conclude that brains are not digital computers, we speculate on the recent implementation of human writing in the brain as a possible digital path that slowly evolves the brain into a genuine (slow) Turing machine. (shrink)

There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, (...) in: R.S. Cohen et al. (Eds.), Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies fo Abner Shimony, Vol. 2, Kluwer Academic Publishers, Great Britain, 1997, pp. 177–190]. Unlike some others in the literature, these notions apply not only to certain nice sets, but to general sets in Rn and other appropriate spaces. We consider some motivations for these concepts and the logical relations between them. It has been argued that d.m.z. is especially appropriate for physical applications, and on Rn with the standard measure, it is strictly stronger than r.a. [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382]. Here we show that this is the only implication that holds among our three decidabilities in that setting. Under arbitrary measures, even this implication fails. Yet for intervals of non-zero length, and more generally, convex sets of non-zero measure, the three concepts are equivalent. (shrink)

I show that there are good arguments and evidence to boot that support the language as an instrument of thought hypothesis. The underlying mechanisms of language, comprising of expressions structured hierarchically and recursively, provide a perspective (in the form of a conceptual structure) on the world, for it is only via language that certain perspectives are avail- able to us and to our thought processes. These mechanisms provide us with a uniquely human way of thinking and talking about the world (...) that is different to the sort of thinking we share with other animals. If the primary function of language were communication then one would expect that the underlying mechanisms of language will be structured in a way that favours successful communication. I show that not only is this not the case, but that the underlying mechanisms of language are in fact structured in a way to maximise computational efficiency, even if it means causing communicative problems. Moreover, I discuss evidence from comparative, neuropatho- logical, developmental, and neuroscientific evidence that supports the claim that language is an instrument of thought. (shrink)

Yuri Matiyasevich's theorem states that the set of all Diophantine equations which have a solution in non-negative integers is not recursive. Craig Smoryński's theorem states that the set of all Diophantine equations which have at most finitely many solutions in non-negative integers is not recursively enumerable. Let R be a subring of Q with or without 1. By H_{10}(R), we denote the problem of whether there exists an algorithm which for any given Diophantine equation with integer coefficients, can decide (...) whether or not the equation has a solution in R. We prove that a positive solution to H_{10}(R) implies that the set of all Diophantine equations with a finite number of solutions in R is recursively enumerable. We show the converse implication for every infinite set R \subseteq Q such that there exist computable functions \tau_1,\tau_2:N \to Z which satisfy (\forall n \in N \tau_2(n) \neq 0) \wedge ({\frac{\tau_1(n)}{\tau_2(n)}: n \in N}=R). This implication for R=N guarantees that Smoryński's theorem follows from Matiyasevich's theorem. Harvey Friedman conjectures that the set of all polynomials of several variables with integer coefficients that have a rational solution is not recursive. Harvey Friedman conjectures that the set of all polynomials of several variables with integer coefficients that have only finitely many rational solutions is not recursively enumerable. These conjectures are equivalent by our results for R=Q. (shrink)

Frames, i.e., recursive attribute-value structures, are a general format for the decomposition of lexical concepts. Attributes assign unique values to objects and thus describe functional relations. Concepts can be classified into four groups: sortal, individual, relational and functional concepts. The classification is reflected by different grammatical roles of the corresponding nouns. The paper aims at a cognitively adequate decomposition, particularly, of sortal concepts by means of frames. Using typed feature structures, an explicit formalism for the characterization of cognitive frames (...) is developed. The frame model can be extended to account for typicality effects. Applying the paradigm of object-related neural synchronization, furthermore, a biologically motivated model for the cortical implementation of frames is developed. Cortically distributed synchronization patterns may be regarded as the fingerprints of concepts. (shrink)

A number of philosophers and logicians have argued for the conclusion that maps are logically tractable modes of representation by analyzing them in propositional terms. But in doing so, they have often left what they mean by "propositional" undefined or unjustified. I argue that propositions are characterized by a structure that is digital, universal, asymmetrical, and recursive. There is little positive evidence that maps exhibit these features. Instead, we can better explain their functional structure by taking seriously the observation (...) that maps arrange their constituent elements in a non-hierarchical, holistic structure. This is compatible with the more basic claim advanced by defenders of a propositional analysis: that (many) maps do have formal semantics and logic. (shrink)

This paper contends that Stoic logic (i.e. Stoic analysis) deserves more attention from contemporary logicians. It sets out how, compared with contemporary propositional calculi, Stoic analysis is closest to methods of backward proof search for Gentzen-inspired substructural sequent logics, as they have been developed in logic programming and structural proof theory, and produces its proof search calculus in tree form. It shows how multiple similarities to Gentzen sequent systems combine with intriguing dissimilarities that may enrich contemporary discussion. Much of Stoic (...) logic appears surprisingly modern: a recursively formulated syntax with some truth-functional propositional operators; analogues to cut rules, axiom schemata and Gentzen’s negation-introduction rules; an implicit variable-sharing principle and deliberate rejection of Thinning and avoidance of paradoxes of implication. These latter features mark the system out as a relevance logic, where the absence of duals for its left and right introduction rules puts it in the vicinity of McCall’s connexive logic. Methodologically, the choice of meticulously formulated meta-logical rules in lieu of axiom and inference schemata absorbs some structural rules and results in an economical, precise and elegant system that values decidability over completeness. (shrink)

Many of the moral and political disputes that loom large today involve claims (1) in the register of respect and offense that are (2) linked to membership in a subordinated social group and (3) occasioned by symbolic or expressive items or acts. This essay seeks to clarify the nature, stakes, and characteristic challenges of these recurring, but often disorienting, conflicts. Drawing on a body of philosophical work elaborating the moral function of etiquette, I first argue that the claims at issue (...) implicate a communicative apparatus of the same basic kind—a system that I term the “etiquette of equality.” That regime, I suggest, can serve a kindred function of facilitating the expression of morally appropriate attitudes. I also argue, however, that the etiquette of equality exhibits three problematic features that counsel ambivalence about its mounting significance: (1) the costly overdetermination of relevant signals; (2) a recursive tendency toward inflation in respect’s demands; and (3) a related set of incentives for testing, and then affirming, a group’s status through the assertion and symbolic remediation of dignitary harm. The upshot is a better understanding of the trade-offs and predicaments we face in a vital area of public life. (shrink)

In this article, I show why it is necessary to abolish the use of predictive algorithms in the US criminal justice system at sentencing. After presenting the functioning of these algorithms in their context of emergence, I offer three arguments to demonstrate why their abolition is imperative. First, I show that sentencing based on predictive algorithms induces a process of rewriting the temporality of the judged individual, flattening their life into a present inescapably doomed by its past. Second, I demonstrate (...) that recursive processes, comprising predictive algorithms and the decisions based on their predictions, systematically suppress outliers and progressively transform reality to match predictions. In my third and final argument, I show that decisions made on the basis of predictive algorithms actively perform a biopolitical understanding of justice as management and modulation of risks. In such a framework, justice becomes a means to maintain a perverse social homeostasis that systematically exposes disenfranchised Black and Brown populations to risk. (shrink)

This paper outlines a formal recursive wager resolution calculus (WRC) that provides a novel conceptual framework for sentential logic via bridge rules that link wager resolution with truth values. When paired with a traditional truth-centric criterion of logical soundness WRC generates a sentential logic that is broadly truth-conditional but not truth-functional, supports the rules of proof employed in standard mathematics, and is immune to the most vexing features of their traditional implementation. WRC also supports a novel probabilistic criterion of (...) logical soundness, the fair betting probability criterion (FBP). It guarantees that the conclusion of an FBP-valid argument is at least as credible as a conjunction of premises, and also that the conclusion is true if the premises are. In addition, WRC provides a platform for a novel non-probabilistic, computationally simpler criterion of logical soundness – the criterion of Super-validity - that issues the same logical appraisals as FBP, and hence the same guarantees. (shrink)

This essay aims to vindicate the thesis that cognitive computational properties are abstract objects implemented in physical systems. I avail of Voevodsky's Univalence Axiom and function type equivalence in Homotopy Type Theory, in order to specify an abstraction principle for epistemic (hyper-)intensions. The homotopic abstraction principle for epistemic (hyper-)intensions provides an epistemic conduit for our knowledge of (hyper-)intensions as abstract objects. Higher observational type theory might be one way to make first-order abstraction principles defined via inference rules, although not higher-order (...) abstraction principles, computable. The truth of my first-order abstraction principle for hyperintensions is grounded in its being possibly recursively enumerable i.e. Turing computable and the Turing machine being physically implementable. Epistemic modality and hyperintensionality can thus be shown to be both a compelling and a materially adequate candidate for the fundamental structure of mental representational states, comprising a fragment of the language of thought. (shrink)

I argue that the two-dimensional hyperintensions of epistemic topic-sensitive two-dimensional truthmaker semantics provide a compelling solution to the access problem. -/- I countenance an abstraction principle for epistemic hyperintensions based on Voevodsky's Univalence Axiom and function type equivalence in Homotopy Type Theory. The truth of my first-order abstraction principle for hyperintensions is grounded in its being possibly recursively enumerable i.e. Turing computable and the Turing machine being physically implementable. I apply, further, modal rationalism in modal epistemology to solve the access (...) problem. Epistemic possibility and hyperintensionality, i.e. conceivability, can be a guide to metaphysical possibility and hyperintensionality, when (i) epistemic worlds or epistemic hyperintensional states are interpreted as being centered metaphysical worlds or hyperintensional states, i.e. indexed to an agent, when (ii) the epistemic (hyper-)intensions and metaphysical (hyper-)intensions for a sentence coincide, i.e. the hyperintension has the same value irrespective of whether the worlds in the argument of the functions are considered as epistemic or metaphysical, and when (iii) sentences are said to consist in super-rigid expressions, i.e. rigid expressions in all epistemic worlds or states and in all metaphysical worlds or states. I argue that (i) and (ii) obtain in the case of the access problem. (shrink)

Until the late 19th century scientists almost always assumed that the world could be described as a rule-based and hence deterministic system or as a set of such systems. The assumption is maintained in many 20th century theories although it has also been doubted because of the breakthrough of statistical theories in thermodynamics (Boltzmann and Gibbs) and other fields, unsolved questions in quantum mechanics as well as several theories forwarded within the social sciences. Until recently it has furthermore been assumed (...) that a rule-based and deterministic system was also predictable if only the rules were known, but this assumption has now been undermined by modern chaos-theory describing rule-based and deterministic, but unpredictable systems, while catastrophe-theory delivers a set of types describing various kinds of instability and conditions for the stability of a given system. Hence the main trait in the theoretical development in the 20th-century science can be described as a basic modification and limitation of some of the fundamental and strong assumptions forwarded in the previous epochs of modern science. Ironically, the very same process has been a process in which the human capacity to intervene in nature has expanded dramatically and mainly with the help of the very same theories, and not least because they allow nature to be described and made manipulable on a lower level and a more fine-grained scale. While the overall theoretical consistency between the various theories has gone, the reach of human intervention in nature has increased based on quite new dimensions whether in the area of physics (e.g.: energy technologies, chemical technologies, nanotechnologies etc.) or biology (ge¬netic manipulation) or in the area of psychology, sociology and culture (artificial simulations of mental processes, new means of communication, implying changes in the social infrastructure and cultural behaviour etc.). While some of these changes and new conditions can be reflected from within the conceptual framework of rule-based systems, albeit more complex than formerly recognized, others seem to give rise to the question of whether there are »systems« and relations between different systems in the world which are not rule-based? For instance, it seems to be obvious that the notion of instability represents a major conceptual break with former theories of rule-based systems, as the stability of the latter is an axiomatically given property implied in the very notion of rule-based systems, while instability can only be the result of external influence which should be explained as the result of another rule-based sy¬stem. While there are no difficulties implied concerning the stability of rule-based systems, the notion of unstable states of a system raises the question of how there can be a system at all if there are no invariant stabilising principles? This is the first question which I will address. And I shall do so by taking two examples of such systems as my point of departure. The first example will be the computer and the second will be ordinary language. In both cases I will argue that the stability of these systems (which are both defined by the existence/presence of human intentions) are provided by the help of - differently organised - redundancy functions which both allow the maintenance of systems in unstable macro-states, suspension of previous rules, underdetermination and overdetermination and generation/emergence/creation of new rules more or less independent of previous rules by the help of optional recursions to the permanently accessible underlying levels as for instance the level of binary representation in computers. Since the notion of redundancy is both controversial as such and often avoided, the concept is discussed (as defined in Claude Shannon's mathematical theory of information and in the semiotic framework of J. J. Greimas) and leading to a more general definition in which the redundancy functions serve to overcome noisy conditions, but at the cost of rule-based stability, determination, and predictability. A second question will be how the notion of rule-generating systems relates to the notion of anticipatory systems and it will be argued that rule-generating systems share some features with an¬ticipatory systems and that the former from a certain viewpoint can be seen as a subclass of the latter, although anticipative features are not necessarily a part of the definition of rule-generating systems. On the other hand, it will be discussed whether anticipatory systems which are not rule-generating systems can exist and it will be argued that the capacity to anticipate is strongly limited if it is not part of a rule-generating system. Therefore, it is concluded that the most powerful anticipatory systems need to be rule-generating systems. (shrink)

Proceedings of the papers presented at the Symposium on "Revisiting Turing and his Test: Comprehensiveness, Qualia, and the Real World" at the 2012 AISB and IACAP Symposium that was held in the Turing year 2012, 2–6 July at the University of Birmingham, UK. Ten papers. - http://www.pt-ai.org/turing-test --- Daniel Devatman Hromada: From Taxonomy of Turing Test-Consistent Scenarios Towards Attribution of Legal Status to Meta-modular Artificial Autonomous Agents - Michael Zillich: My Robot is Smarter than Your Robot: On the Need for (...) a Total Turing Test for Robots - Adam Linson, Chris Dobbyn and Robin Laney: Interactive Intelligence: Behaviour-based AI, Musical HCI and the Turing Test - Javier Insa, Jose Hernandez-Orallo, Sergio España - David Dowe and M.Victoria Hernandez-Lloreda: The anYnt Project Intelligence Test (Demo) - Jose Hernandez-Orallo, Javier Insa, David Dowe and Bill Hibbard: Turing Machines and Recursive Turing Tests — Francesco Bianchini and Domenica Bruni: What Language for Turing Test in the Age of Qualia? - Paul Schweizer: Could there be a Turing Test for Qualia? - Antonio Chella and Riccardo Manzotti: Jazz and Machine Consciousness: Towards a New Turing Test - William York and Jerry Swan: Taking Turing Seriously (But Not Literally) - Hajo Greif: Laws of Form and the Force of Function: Variations on the Turing Test. (shrink)

Abstract Introduction Logically valid deductive arguments are clear examples of abstract recursive computational proce‐ dures on propositions or on probabilities. However, it is not known if the cortical time‐consuming inferential pro‐ cesses in which logical arguments are eventually realized in the brain are in fact physically different from other kinds of inferential processes. Methods In order to determine whether an electrical EEG discernible pattern of logical deduction exists or not, a new experimental paradigm is proposed contrasting logically valid and (...) invalid inferences with exactly the same content (same premises and same relational variables) and distinct logical complexity (propositional truth‐functional operators). Electroencephalographic signals from 19 subjects (24.2 ± 3.3 years) were acquired in a two‐condition para‐ digm (100 trials for each condition). After the initial general analysis, a trial‐by‐trial approach in beta‐2 band allowed to uncover not only evoked but also phase asynchronous activity between trials. Results showed that (i) deductive inferences with the same content evoked the same response pattern in logically valid and invalid conditions, (ii) mean response time in logically valid inferences is 61.54% higher, (iii) logically valid inferences are subjected to an early (400 ms) and a late reprocessing (600 ms) verified by two distinct beta‐2 activa‐ tions (p‐value < 0,01, Wilcoxon signed rank test). Conclusion We found evidence of a subtle but measurable electrical trait of logical validity. Results put forward the hypothesis that some logically valid deductions are recursive or computational cortical events. Keywords Beta‐2 band, Evoked potentials, Induced potentials, Deductive inference, Logical validity, Cortical bases of logical reasoning. (shrink)

The novel concept of a simulating halt decider enables halt decider H to to correctly determine the halt status of the conventional “impossible” input D that does the opposite of whatever H decides. This works equally well for Turing machines and “C” functions. The algorithm is demonstrated using “C” functions because all of the details can be shown at this high level of abstraction. ---------------------------------------------------------------------------------------------------- ---- Simulating halt decider H correctly determines that D correctly simulated by H would remain (...) stuck in recursive simulation never reaching its own final state. D cannot do the opposite of the return value from H because this return value is unreachable by every correctly simulated D. This same result is shown to be derived in the Peter Linz Turing machine based proof. (shrink)

Intermediate phenomena of reality present particular characteristics of systemic self-organization, multilevel interrelations, recursivity, emergence of new «objects» with properties different from those of the elements that form them, and evolutionary dynamics, that probably need the formulation of new theoretical concepts and different paradigm principles. The sciences or perspectives of complexity, or the «complex» thinking, try to respond adequately to this complexity of reality. This approach adopts a multidimensional, integrated and dynamic view of reality: the world is made up of overlapping (...) levels of different elements which produce new properties or new organizations at higher levels. If we conceive what we call languages as simple and decontextualized objects, we can understand some of the more mechanical aspects but we will ignore their conditions of existence, functionality, maintenance, variation, change and extinction. (shrink)

This paper initiates the reverse mathematics of social choice theory, studying Arrow's impossibility theorem and related results including Fishburn's possibility theorem and the Kirman–Sondermann theorem within the framework of reverse mathematics. We formalise fundamental notions of social choice theory in second-order arithmetic, yielding a definition of countable society which is tractable in RCA0. We then show that the Kirman–Sondermann analysis of social welfare functions can be carried out in RCA0. This approach yields a proof of Arrow's theorem in RCA0, (...) and thus in PRA, since Arrow's theorem can be formalised as a Π01 sentence. Finally we show that Fishburn's possibility theorem for countable societies is equivalent to ACA0 over RCA0. (shrink)

We develop a simple framework called ‘natural topology’, which can serve as a theoretical and applicable basis for dealing with real-world phenomena.Natural topology is tailored to make pointwise and pointfree notions go together naturally. As a constructive theory in BISH, it gives a classical mathematician a faithful idea of important concepts and results in intuitionism. -/- Natural topology is well-suited for practical and computational purposes. We give several examples relevant for applied mathematics, such as the decision-support system Hawk-Eye, and various (...) real-number representations. -/- We compare classical mathematics (CLASS), intuitionistic mathematics (INT), recursive mathematics (RUSS), Bishop-style mathematics (BISH) and formal topology, aiming to reduce the mutual differences to their essence. To do so, our mathematical foundation must be precise and simple. There are links with physics, regarding the topological character of our physical universe. -/- Any natural space is isomorphic to a quotient space of Baire space, which therefore is universal. We develop an elegant and concise ‘genetic induction’ scheme, and prove its equivalence on natural spaces to a formal-topological induction style. The inductive Heine-Borel property holds for ‘compact’ or ‘fanlike’ natural subspaces, including the real interval [g, h]. Inductive morphisms respect this Heine-Borel property, inversely. This partly solves the continuous-function problem for BISH, yet pointwise problems persist in the absence of Brouwer’s Thesis. -/- By inductivizing the definitions, a direct correspondence with INT is obtained which allows for a translation of many intuitionistic results into BISH. We thus prove a constructive star-finitary metrization theorem which parallels the classical metrization theorem for strongly paracompact spaces. We also obtain non-metrizable Silva spaces, in infinite-dimensional topology. Natural topology gives a solid basis, we think, for further constructive study of topological lattice theory, algebraic topology and infinite-dimensional topology. The final section reconsiders the question of which mathematics to choose for physics. Compactness issues also play a role here, since the question ‘can Nature produce a non-recursive sequence?’ finds a negative answer in CTphys . CTphys , if true, would seem at first glance to point to RUSS as the mathematics of choice for physics. To discuss this issue, we wax more philosophical. We also present a simple model of INT in RUSS, in the two-players game LIfE. (shrink)

Classical interpretations of Goedels formal reasoning, and of his conclusions, implicitly imply that mathematical languages are essentially incomplete, in the sense that the truth of some arithmetical propositions of any formal mathematical language, under any interpretation, is, both, non-algorithmic, and essentially unverifiable. However, a language of general, scientific, discourse, which intends to mathematically express, and unambiguously communicate, intuitive concepts that correspond to scientific investigations, cannot allow its mathematical propositions to be interpreted ambiguously. Such a language must, therefore, define mathematical truth (...) verifiably. We consider a constructive interpretation of classical, Tarskian, truth, and of Goedel's reasoning, under which any formal system of Peano Arithmetic---classically accepted as the foundation of all our mathematical Languages---is verifiably complete in the above sense. We show how some paradoxical concepts of Quantum mechanics can, then, be expressed, and interpreted, naturally under a constructive definition of mathematical truth. (shrink)

Natural recursion in syntax is recursion by linguistic value, which is not syntactic in nature but semantic. Syntax-specific recursion is not recursion by name as the term is understood in theoretical computer science. Recursion by name is probably not natural because of its infinite typeability. Natural recursion, or recursion by value, is not species-specific. Human recursion is not syntax-specific. The values on which it operates are most likely domain-specific, including those for syntax. Syntax seems to require no more (and no (...) less) than the resource management mechanisms of an embedded push-down automaton (EPDA). We can conceive EPDA as a common automata-theoretic substrate for syntax, collaborative planning, i-intentions, and we-intentions. They manifest the same kind of dependencies. Therefore, syntactic uniqueness arguments for human behavior can be better explained if we conceive automata-constrained recursion as the most unique human capacity for cognitive processes. (shrink)

We give a new and elementary construction of primitive positive decomposition of higher arity relations into binary relations on finite domains. Such decompositions come up in applications to constraint satisfaction problems, clone theory and relational databases. The construction exploits functional completeness of 2-input functions in many-valued logic by interpreting relations as graphs of partially defined multivalued ‘functions’. The ‘functions’ are then composed from ordinary functions in the usual sense. The construction is computationally effective and relies on (...) well-developed methods of functional decomposition, but reduces relations only to ternary relations. An additional construction then decomposes ternary into binary relations, also effectively, by converting certain disjunctions into existential quantifications. The result gives a uniform proof of Peirce’s reduction thesis on finite domains, and shows that the graph of any Sheffer function composes all relations there. (shrink)

In this paper, I identify a central problem for conceptual engineering: the problem of showing concept-users why they should recognise the authority of the concepts advocated by engineers. I argue that this authority problem cannot generally be solved by appealing to the increased precision, consistency, or other theoretical virtues of engineered concepts. Outside contexts in which we anyway already aim to realise theoretical virtues, solving the authority problem requires engineering to take a functional turn and attend to the functions (...) of concepts. But this then presents us with the problem of how to specify a concept’s function. I argue that extant solutions to this function specification problem are unsatisfactory for engineering purposes, because the functions they identify fail to reliably bestow authority on concepts, and hence fail to solve the authority problem. What is required is an authoritative notion of conceptual function: an account of the functions of concepts which simultaneously shows why concepts fulfilling such functions should be recognised as having authority. I offer an account that meets this combination of demands by specifying the functions of concepts in terms of how they tie in with our present concerns. (shrink)

Functional reductionism concerning mental properties has recently been advocated by Jaegwon Kim in order to solve the problem of the 'causal exclusion' of the mental. Adopting a reductionist strategy first proposed by David Lewis, he regards psychological properties as being 'higher-order' properties functionally defined over 'lower-order' properties, which are causally efficacious. Though functional reductionism is compatible with the multiple realizability of psychological properties, it is blocked if psychological properties are subdivided or crosscut by neurophysiological properties. I argue that there is (...) recent evidence from cognitive neuroscience that shows that this is the case for the psychological property of fear. Though this may suggest that some psychological properties should be revised in order to conform to those of neurophysiology, the history of science demonstrates that this is not always the outcome, particularly with properties that play an important role in our folk theories and are central to human concerns. (shrink)

Different cognitive functions recruit a number of different, often overlapping, areas of the brain. Theories in cognitive and computational neuroscience are beginning to take this kind of functional integration into account. The contributions to this special issue consider what functional integration tells us about various aspects of the mind such as perception, language, volition, agency, and reward. Here, I consider how and why functional integration may matter for the mind; I discuss a general theoretical framework, based on generative models, (...) that may unify many of the debates surrounding functional integration and the mind; and I briefly introduce each of the contributions. (shrink)

Function talk is a constant across different life sciences. From macro-evolution to genetics, functions are mentioned everywhere. For example, a limb’s function is to allow movement and RNA polymerases’ function is to transcribe DNA. Biochemistry is not immune from such a characterization; the biochemical world seems to be a chemical world embedded within biological processes. Specifically, biochemists commonly ascribe functions to biomolecules and classify them accordingly. This has been noticed in the recent philosophical literature on biochemical kinds. But (...) while a lot has been written on biological and psychological functions, little has been said explicitly about biochemical fuctions. Here, I explore functional attribution to biochemical molecules. I argue that if we accept this attribution, then biochemical functions are constituted by chemical dispositional properties that causally contribute to selected biological processes. In section 2, I discuss the controversy concerning the characterization of biochemical functions. In section 3, I consider whether a biological or a chemical under- standing of function can be applied to biochemical functions, illustrating the account with the example of vitamin B12. The result is that none of the theories on their own provides an adequate characterization. In section 4, I present an account of biochemical functions. In section 5, I assess this account taking into consideration common requirements for a theory of functions and an objection. (shrink)

The recursive aspect of process reliabilism has rarely been examined. The regress puzzle, which illustrates infinite regress arising from the combination of the recursive structure and the no-defeater condition incorporated into it, is a valuable exception. However, this puzzle can be dealt with in the framework of process reliabilism by reconsidering the relationship between the recursion and the no-defeater condition based on the distinction between prima facie and ultima facie justification. Thus, the regress puzzle is not a basis (...) for abandoning process reliabilism. A genuinely intractable problem for recursive reliabilism lies in the gap between the reliability of the entire path to a belief and that of its parts. Confronted with this puzzle, reliabilists can orient themselves toward ‘reliable-as-a-whole reliabilism’ instead of ‘reliable-in-every-part reliabilism’, including recursive reliabilism, which is found to be not well-motivated. (shrink)

What is the function of morality? On this question, something approaching a consensus has recently emerged. Impressed by developments in evolutionary theory, many philosophers now tell us that the function of morality is to reduce social tensions, and to thereby enable a society to efficiently promote the well-being of its members. In this paper, I subject this consensus to rigorous scrutiny, arguing that the functional hypothesis in question is not well supported. In particular, I attack the supposed evidential relation between (...) an evolutionary genealogy of morals and the functional hypothesis itself. I show that there are a great many functionally relevant discontinuities between our own culture and the culture within which morality allegedly emerged, and I argue that this seriously weakens the inference from morality’s evolutionary history to its present-day function. (shrink)

The functional approach to scientific progress has been mainly developed by Kuhn, Lakatos, Popper, Laudan, and more recently by Shan. The basic idea is that science progresses if key functions of science are fulfilled in a better way. This chapter defends the function approach. It begins with an overview of the two old versions of the functional approach by examining the work of Kuhn, Laudan, Popper, and Lakatos. It then argues for Shan’s new functional approach, in which scientific progress (...) is defined as an increase of usefulness of exemplary practices. (shrink)

Recently, Piccinini and Craver have stated three theses concerning the relations between functional analysis and mechanistic explanation in cognitive sciences: No Distinctness: functional analysis and mechanistic explanation are explanations of the same kind; Integration: functional analysis is a kind of mechanistic explanation; and Subordination: functional analyses are unsatisfactory sketches of mechanisms. In this paper, I argue, first, that functional analysis and mechanistic explanations are sub-kinds of explanation by scientific (idealized) models. From that point of view, we must take into account (...) the tradeoff between the representational/explanatory goals of generality and precision that govern the practice of model-building. In some modeling scenarios, it is rational to maximize explanatory generality at the expense of mechanistic precision. This tradeoff allows me to put forward a problem for the mechanist position. If mechanistic modeling endorses generality as a valuable goal, then Subordination should be rejected. If mechanists reject generality as a goal, then Integration is false. I suggest that mechanists should accept that functional analysis can offer acceptable explanations of cognitive phenomena. (shrink)