This chapter surveys set theory, model theory, and computability theory: how they first emerged from the foundations of mathematics, and how they have developed since. There are any amounts of mathematical technicalities in the background, but the chapter highlights those themes that have some philosophical resonance.

There is currently much interest in bringing together the tradition of categorial grammar, and especially the Lambek calculus, with the recent paradigm of linear logic to which it has strong ties. One active research area is designing non-commutative versions of linear logic (Abrusci, 1995; Retoré, 1993) which can be sensitive to word order while retaining the hypothetical reasoning capabilities of standard (commutative) linear logic (Dalrymple et al., 1995). Some connections between the Lambek calculus and computations in groups have long been (...) known (van Benthem, 1986) but no serious attempt has been made to base a theory of linguistic processing solely on group structure. This paper presents such a model, and demonstrates the connection between linguistic processing and the classical algebraic notions of non-commutative free group, conjugacy, and group presentations. A grammar in this model, or G-grammar is a collection of lexical expressions which are products of logical forms, phonological forms, and inverses of those. Phrasal descriptions are obtained by forming products of lexical expressions and by cancelling contiguous elements which are inverses of each other. A G-grammar provides a symmetrical specification of the relation between a logical form and a phonological string that is neutral between parsing and generation modes. We show how the G-grammar can be oriented for each of the modes by reformulating the lexical expressions as rewriting rules adapted to parsing or generation, which then have strong decidability properties (inherent reversibility). We give examples showing the value of conjugacy for handling long-distance movement and quantifier scoping both in parsing and generation. The paper argues that by moving from the free monoid over a vocabulary V (standard in formal language theory) to the free group over V, deep affinities between linguistic phenomena and classical algebra come to the surface, and that the consequences of tapping the mathematical connections thus established can be considerable. (shrink)

Intelligent design advocate William Dembski has introduced a measure of information called “complex specified information”, or CSI. He claims that CSI is a reliable marker of design by intelligent agents. He puts forth a “Law of Conservation of Information” which states that chance and natural laws are incapable of generating CSI. In particular, CSI cannot be generated by evolutionary computation. Dembski asserts that CSI is present in intelligent causes and in the flagellum of Escherichia coli, and concludes that neither (...) have natural explanations. In this paper, we examine Dembski’s claims, point out significant errors in his reasoning, and conclude that there is no reason to accept his assertions. (shrink)

The fundamental ideas concerning computation and recursion naturally find their place at the interface between logic and theoretical computer science. The contributions in this book, by leaders in the field, provide a picture of current ideas and methods in the ongoing investigations into the pure mathematical foundations of computability theory. The topics range over computable functions, enumerable sets, degree structures, complexity, subrecursiveness, domains and inductive inference. A number of the articles contain introductory and background material which it is (...) hoped will make this volume an invaluable resource for specialists and non-specialists alike. (shrink)

Levelt et al. attempt to “model their theory” with WEAVER ++. Modeling theories requires a model theory. The time is ripe for a methodology for building, testing, and evaluating computational models. We propose a tentative, five-step framework for tackling this problem, within which we discuss the potential strengths and weaknesses of Levelt et al.'s modeling approach.

This article argues that the computer game can be a locus of aesthetic form in contemporary culture. The context for understanding this claim is the decline of the artwork as bearer of form in the late 20th century, as this was understood by Adorno. Form is the enigmatic other of instrumental reason that emerges spontaneously in creative works and, in the modern era, is defined as that which makes them captivating and enigmatic yet resistant to analytic understanding. Clarification of the (...) ways in which form is at work in game play is sought from aesthetic theory (Kant), ludology (or theory of games), and the idea of a neo-baroque entertainment culture (Ndalianis). Kant emphasized the role of play in the constitution of imaginary realms associated with aesthetic pleasure. Ludology takes play as an anthropological given differentiated historically by the development of game structures. Neo-baroque theory postulates a labyrinthine, complex and de-centred entertainment culture, largely shaped by computing as a cultural practice. The article synthesizes insights from these perspectives and, drawing on ideas from Adorno and Benjamin, argues that computer games can occupy an oppositional or critical role within contemporary aesthetics and culture. Reflection on the constitutive processes of computer game play discloses a new place for instrumental reason within aesthetic experience, as the dialectic of form and analysis migrates from traditional art materials to digital electronics. (shrink)

A study is described in which the effectiveness of a computer program (Hermes) on improving argumentative writing is tested. One group of students was randomly assigned to a control group and the other was assigned to the experimental group where they are asked to use the Hermes program. All students were asked to write essays on controversial topics to an opposed audience. Their essays were content-analysed for dialectical traits. Based on this analysis, it was concluded that the experimental group wrote (...) more dialectically effective essays than the control group, and the amount of difference between the control and experimental groups was related to the students' intellectual developmental level, as assessed by the Measure of Epistemological Reflection (MER). It is concluded that argumentative writing, operationalized here as dialectical writing, can be improved by computer-assisted instruction, but that attempts to teach such forms of thinking and writing need to take into account students' capacity to benefit from such instruction. Such capacity is defined here as intellectual development. (shrink)

Open peer commentary on the article “Info-computational Constructivism and Cognition” by Gordana Dodig-Crnkovic. Upshot: Dodig-Crnkovic’s “info-computational constructivism” (IC), as an essential part of a constructivist approach, needs integration with the logical, mathematical and physical evidence coming from quantum field theory (QFT) as the fundamental physics of the emergence of “complex systems” in all realms of natural sciences.

What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). (...) Dr Cutland begins with a mathematical characterisation of computable functions using a simple idealised computer (a register machine); after some comparison with other characterisations, he develops the mathematical theory, including a full discussion of non-computability and undecidability, and the theory of recursive and recursively enumerable sets. The later chapters provide an introduction to more advanced topics such as Gildel's incompleteness theorem, degrees of unsolvability, the Recursion theorems and the theory of complexity of computation. Computability is thus a branch of mathematics which is of relevance also to computer scientists and philosophers. Mathematics students with no prior knowledge of the subject and computer science students who wish to supplement their practical expertise with some theoretical background will find this book of use and interest. (shrink)

Several papers (e.g. [7, 23, 42]) have recently sought to give general frameworks for online structures and algorithms ([4]), and seeking to connect, if only by analogy, online and computable structure theory. These initiatives build on earlier work on online colouring and other combinatorial algorithms by Bean [10], Kierstead, Trotter et al. [48, 54, 57] and others, as we discuss below. In this paper we will look at such frameworks and illustrate them with examples from the first author’s MSc (...) Thesis ([58]). In this thesis, Askes looks at online, adversarial online and strongly online algorithms and structures. Additionally, we prove some new theorems about online algorithms on graphs of bounded pathwidth as well as some new results on punctually 1-decidable structures. (shrink)

We review some of the history of the computability theory of functionals of higher types, and we will demonstrate how contributions from logic and theoretical computer science have shaped this still active subject.

This book constitutes the refereed proceedings of the 5th Kurt Gödel Colloquium on Computational Logic and Proof Theory, KGC '97, held in Vienna, Austria, in August 1997. The volume presents 20 revised full papers selected from 38 submitted papers. Also included are seven invited contributions by leading experts in the area. The book documents interdisciplinary work done in the area of computer science and mathematical logics by combining research on provability, analysis of proofs, proof search, and complexity.

Computability theory originated with the seminal work of Gödel, Church, Turing, Kleene and Post in the 1930s. This theory includes a wide spectrum of topics, such as the theory of reducibilities and their degree structures, computably enumerable sets and their automorphisms, and subrecursive hierarchy classifications. Recent work in computability theory has focused on Turing definability and promises to have far-reaching mathematical, scientific, and philosophical consequences. Written by a leading researcher, Computability Theory provides a concise, comprehensive, (...) and authoritative introduction to contemporary computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level. The book includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science. Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable and lively way. (shrink)

We build an א₁-categorical but not א₀-categorical theory whose only computably presentable model is the saturated one. As a tool, we introduce a notion related to limitwise monotonic functions.

Psychology endeavors to develop theories of human capacities and behaviors on the basis of a variety of methodologies and dependent measures. We argue that one of the most divisive factors in psychological science is whether researchers choose to use computational modeling of theories (over and above data) during the scientific-inference process. Modeling is undervalued yet holds promise for advancing psychological science. The inherent demands of computational modeling guide us toward better science by forcing us to conceptually analyze, specify, and formalize (...) intuitions that otherwise remain unexamined—what we dub open theory. Constraining our inference process through modeling enables us to build explanatory and predictive theories. Here, we present scientific inference in psychology as a path function in which each step shapes the next. Computational modeling can constrain these steps, thus advancing scientific inference over and above the stewardship of experimental practice (e.g., preregistration). If psychology continues to eschew computational modeling, we predict more replicability crises and persistent failure at coherent theory building. This is because without formal modeling we lack open and transparent theorizing. We also explain how to formalize, specify, and implement a computational model, emphasizing that the advantages of modeling can be achieved by anyone with benefit to all. (shrink)

A central aim of cognitive science is to understand the fundamental mechanisms that enable humans to navigate and make sense of complex environments. In this letter, we argue that computational complexity theory, a foundational framework for evaluating computational resource requirements, holds significant potential in addressing this challenge. As humans possess limited cognitive resources for processing vast amounts of information, understanding how humans perform complex cognitive tasks requires comprehending the underlying factors that drive information processing demands. Computational complexity theory (...) provides a comprehensive theoretical framework to achieve this goal. By adopting this framework, we can gain new insights into how cognitive systems work and develop a more nuanced understanding of the relation between task complexity and human behavior. We provide empirical evidence supporting our argument and identify several open research questions and challenges in applying computational complexity theory to human decision‐making and cognitive science at large. (shrink)

We investigate the connections between computability theory and Nonstandard Analysis. In particular, we investigate the two following topics and show that they are intimately related. A basic property of Cantor space$2^ $ is Heine–Borel compactness: for any open covering of $2^ $, there is a finite subcovering. A natural question is: How hard is it to compute such a finite subcovering? We make this precise by analysing the complexity of so-called fan functionals that given any $G:2^ \to $, output (...) a finite sequence $\langle f_0, \ldots,f_n \rangle $ in $2^ $ such that the neighbourhoods defined from $\overline {f_i } G\left$ for $i \le n$ form a covering of $2^ $. A basic property of Cantor space in Nonstandard Analysis is Abraham Robinson’s nonstandard compactness, i.e., that every binary sequence is “infinitely close” to a standard binary sequence. We analyse the strength of this nonstandard compactness property of Cantor space, compared to the other axioms of Nonstandard Analysis and usual mathematics.Our study of yields exotic objects in computability theory, while leads to surprising results in Reverse Mathematics. We stress that and are highly intertwined, i.e., our study is holistic in nature in that results in computability theory yield results in Nonstandard Analysis and vice versa. (shrink)

Computability theoretic aspects of Polish metric spaces are studied by adapting notions and methods of computable structure theory. In this dissertation, we mainly investigate index sets and classification problems for computably presentable Polish metric spaces. We find the complexity of a number of index sets, isomorphism problems, and embedding problems for computably presentable metric spaces. We also provide several computable structure theory results related to some classical Polish metric spaces such as the Urysohn space $\mathbb {U}$, the Cantor (...) space $2^{\mathbb {N}}$, the Baire space $\mathbb {N}^{\mathbb {N}}$, and spaces of continuous functions.Abstract prepared by Teerawat Thewmorakot.E-mail: teerawat.thew@hotmail.com. (shrink)

Of three types of evidence available to evolution theorists – comparative, continuity, and computational – the first is largely productive rather than predictive. Although comparison between extant species or languages is possible and can be suggestive of evolutionary processes, leading to theory development, comparison with extinct species and languages seems necessary for validation. Continuity and computational evidence provide the best opportunities for supporting predictions.

The familiar theories of physics have the feature that the application of the theory to make predictions in specific circumstances can be done by means of an algorithm. We propose a more precise formulation of this feature—one based on the issue of whether or not the physically measurable numbers predicted by the theory are computable in the mathematical sense. Applying this formulation to one approach to a quantum theory of gravity, there are found indications that there may (...) exist no such algorithms in this case. Finally, we discuss the issue of whether the existence of an algorithm to implement a theory should be adopted as a criterion for acceptable physical theories.“Can it then be that there is... something of use for unraveling the universe to be learned from the philosophy of computer design?” —J. A. Wheeler(1). (shrink)

We study randomness beyond${\rm{\Pi }}_1^1$-randomness and its Martin-Löf type variant, which was introduced in [16] and further studied in [3]. Here we focus on a class strictly between${\rm{\Pi }}_1^1$and${\rm{\Sigma }}_2^1$that is given by the infinite time Turing machines introduced by Hamkins and Kidder. The main results show that the randomness notions associated with this class have several desirable properties, which resemble those of classical random notions such as Martin-Löf randomness and randomness notions defined via effective descriptive set theory such (...) as${\rm{\Pi }}_1^1$-randomness. For instance, mutual randoms do not share information and a version of van Lambalgen’s theorem holds.Towards these results, we prove the following analogue to a theorem of Sacks. If a real is infinite time Turing computable relative to all reals in some given set of reals with positive Lebesgue measure, then it is already infinite time Turing computable. As a technical tool towards this result, we prove facts of independent interest about random forcing over increasing unions of admissible sets, which allow efficient proofs of some classical results about hyperarithmetic sets. (shrink)

We provide some examples showing how game-theoretic arguments can be used in computability theory and algorithmic information theory: unique numbering theorem (Friedberg), the gap between conditional complexity and total conditional complexity, Epstein–Levin theorem and some (yet unpublished) result of Muchnik and Vyugin.

This book describes computability theory and provides an extensive treatment of data structures and program correctness. It makes accessible some of the author's work on generalized recursion theory, particularly the material on the logic programming language PROLOG, which is currently of great interest. Fitting considers the relation of PROLOG logic programming to the LISP type of language.

Let M be a smooth, compact manifold of dimension n ≥ 5 and sectional curvature | K | ≤ 1. Let Met (M) = Riem(M)/Diff(M) be the space of Riemannian metrics on M modulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met (M) such as the diameter. They showed that for every Turing machine T e , e ∈ ω, there is a sequence (uniformly effective in e) of homology (...) n-spheres {P k e } k ∈ ω which are also hypersurfaces, such that P k e is diffeomorphic to the standard n-sphere S n (denoted P k e ≈ diff S n ) iff T e halts on input k, and in this case the connected sum N k e =M ♯ P k e ≈ diff M , so N k e ∈ Met(M), and N k e is associated with a local minimum of the diameter function on Met(M) whose depth is roughly equal to the settling time σ e (k) of T e on inputs y i } ∈ ω of c.e. sets so that for all i the settling time of the associated Turing machine for A i dominates that for A i + 1 , even when the latter is composed with an arbitrary computable function. From this, Nabutovsky and Weinberger showed that the basins exhibit a "fractal" like behavior with extremely big basins, and very much smaller basins coming off them, and so on. This reveals what Nabutovsky and Weinberger describe in their paper on fractals as "the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization." From the point of view of logic and computability, the Nabutovsky-Weinberger results are especially interesting because: (1) they use c.e. sets to prove structural complexity of the geometry and topology, not merely undecidability results as in the word problem for groups, Hilbert's Tenth Problem, or most other applications; (2) they use nontrivial information about c.e. sets, the Soare sequence {A i } i ∈ ω above, not merely G öodel's c.e. noncomputable set K of the 1930's; and (3) without using computability theory there is no known proof that local minima exist even for simple manifolds like the torus T 5 (see §). (shrink)

Machine generated contents note: 1. The Computability Concept;2. General Recursive Functions;3. Programs and Machines;4. Recursive Enumerability;5. Connections to Logic;6. Degrees of Unsolvability;7. Polynomial-Time Computability;Appendix: Mathspeak;Appendix: Countability;Appendix: Decadic Notation;.

This study is concerned with processes for discovering new theories in science. It considers a computational approach to scientific discovery, as applied to the discovery of theories in cognitive science. The approach combines two ideas. First, a process-based scientific theory can be represented as a computer program. Second, an evolutionary computational method, genetic programming, allows computer programs to be improved through a process of computational trialand-error. Putting these two ideas together leads to a system that can automatically generate and (...) improve scientific theories. The application of this method to the discovery of theories in cognitive science is examined. Theories are built up from primitive operators. These are contained in a theory language that defines the space of possible theories. An example of a theory generated by this method is described. These results support the idea that scientific discovery can be achieved through a heuristic search process, even for theories involving a sequence of steps. However, this computational approach to scientific discovery does not eliminate the need for human input. Human judgment is needed to make reasonable prior assumptions about the characteristics of operators used in the theory generation process, and to interpret and provide context for the computationally generated theories. (shrink)

The size and variation in both meaning-making and populations that characterize much contemporary text data demand research processes that support both discovery, interpretation and measurement. We assess one dominant strategy within the social sciences that takes a computer-led approach to text analysis. The approach is coined computational grounded theory. This strategy, we argue, relies on a set of unwarranted assumptions, namely, that unsupervised models return natural clusters of meaning, that the researcher can understand text with limited immersion and that (...) indirect validation is sufficient for ensuring unbiased and precise measurement. In response to this criticism, we develop a framework that is computer assisted. We argue that our reformulation of computational grounded theory better aligns with the principles within grounded theory, anthropological theory generation and ethnography. (shrink)

Computational learning theory explores the limits of learnability. Studying language acquisition from this perspective involves identifying classes of languages that are learnable from the available data, within the limits of time and computational resources available to the learner. Different models of learning can yield radically different learnability results, where these depend on the assumptions of the model about the nature of the learning process, and the data, time, and resources that learners have access to. To the extent that such (...) assumptions accurately reflect human language learning, a model that invokes them can offer important insights into the formal properties of natural languages, and the way in which their representations might be efficiently acquired. In this chapter we consider several computational learning models that have been applied to the language learning task. Some of these have yielded results that suggest that the class of natural languages cannot be efficiently learned from the primary linguistic data (PLD) available to children, through.. (shrink)

This dissertation is an investigation into the degree to which the mathematics used in physical theories can be constructivized. The techniques of recursive function theory and classical logic are used to separate out the algorithmic content of mathematical theories rather than attempting to reformulate them in terms of "intuitionistic" logic. The guiding question is: are there experimentally testable predictions in physics which are not computable from the data? ;The nature of Church's thesis, that the class of effectively calculable functions (...) on the natural numbers is identical to the class of general recursive functions, is discussed. It is argued that this thesis is an example of an explication of the very notion of an effectively calculable function. This is contrary to a view of the thesis as a hypothesis about the limitations of the human mind. ;The extension to functions of a real variable of the notion of effective calculability is discussed, and it is argued that a function of a real variable must be continuous in order to be considered effectively calculable . The relation between continuity and computability is significant for the problem at hand. The results of a well-designed experiment do not depend critically upon the precise values of the relevant parameters. Accordingly, if the solution to a problem in mathematical physics depends discontinuously upon the data, it cannot be regarded as an experimentally testable prediction of the theory. The principle that the testable predictions of a physical theory cannot be singular is known as the principle of regularity. This principle is significant, because discontinuities generate non-computability, but they also disqualify a prediction from being experimentally testable. ;A mathematical framework is set up for discussing computability in physical theories. This framework is then applied to the case of quantum mechanics. It is found that, due to the use of unbounded operators in the theory, noncomputable objects appear, but predictions which satisfy the principle of regularity are nevertheless computable functions of the data. (shrink)

Formalizing commonsense knowledge for reasoning about time has long been a central issue in AI. It has been recognized that the existing formalisms do not provide satisfactory solutions to some fundamental problems, viz. the frame problem. Moreover, it has turned out that the inferences drawn do not always coincide with those one had intended when one wrote the axioms. These issues call for a well-defined formalism and useful computational utilities for reasoning about time and change. Yoav Shoham of Stanford University (...) introduced in his 1986 Yale doctoral thesis an appealing temporal nonmonotonic logic and identified a class of theories, causal theories, which have computationally simple model-theoretic properties. This paper is a study towards building upon Shoham's work on causal theories. We concentrate on improving computational aspects of causal theories while preserving their model-theoretic properties. (shrink)

The paper discusses the question whether T-theories explain how it is possible to understand new sentences, or learn an infinite language, as Davidson claimed. I argue against some commentators that for explanatory power we need not require that T-theories are implicitly known or mirror cognitive structures. I note contra Davidson that the recursive nature of T-theories is not sufficient for explanatory power, since humans can work out only what is computationally tractable, and recursiveness by itself allows for intractable computational complexity. (...) I finally consider the complexity of T-theories, transformed into term rewriting systems, and find that the complexity of such systems is indeed tractable. Therefore Davidson's claim stands, even though a further condition had to be met. (shrink)

Recently, Horsman et al. have proposed a new framework, Abstraction/Representation theory, for understanding and evaluating claims about unconventional or non-standard computation. Among its attractive features, the theory in particular implies a novel account of what is means to be a computer. After expounding on this account, I compare it with other accounts of concrete computation, finding that it does not quite fit in the standard categorization: while it is most similar to some semantic accounts, it is (...) not itself a semantic account. Then I evaluate it according to the six desiderata for accounts of concrete computation proposed by Piccinini. Finding that it does not clearly satisfy some of them, I propose a modification, which I call Agential AR theory, that does, yielding an account that could be a serious competitor to other leading account of concrete computation. (shrink)

Here we prove that if T and T′ are strongly minimal theories, where T′ satisfies a certain property related to triviality and T does not, and T′ is model complete, then there is no computable embedding of Mod(T) into Mod(T′). Using this, we answer a question from [4], showing that there is no computable embedding of VS into ZS, where VS is the class of infinite vector spaces over Q, and ZS is the class of models of Th(Z, S). Similarly, (...) we show that there is no computable embedding of ACF into ZS, where ACF is the class of algebraically closed fields of characteristic 0. (shrink)

This study explores the dynamic feature of organizational citizenship behaviors under the condition of challenge stressors, as this has not been addressed by previous research. Combining the cybernetic theory of stress and social exchange theory, this study builds a dynamic computational model regarding the circular causality between challenge stressors and organizational citizenship behaviors. By conducting a series of simulation experiments, we validated and demonstrated important questions regarding organizational citizenship behaviors. Specifically, when both the initial value of challenge stressors (...) and the importance of challenge appraisal are higher, organizational citizenship behaviors tend to show a sharped inverted U shape at the early stage. When both the equilibrium level of job satisfaction and the initial value of challenge stressors are higher, organizational citizenship behaviors will show an inverted N shape over time. The number and frequency of assigned challenge tasks have an interactive effect on the accumulation of organizational citizenship behaviors within a period. Our theory contributes to identifying the dynamic relationship between challenge stressors and organizational citizenship behaviors. Findings from dynamic computational theory can offer suggestions for managers to encourage employees’ engagement in organizational citizenship behaviors. (shrink)

criticism defend the idea that an individual reader's understanding of a text can be a factor in determining the meaning of what is written in that text, and hence must play a part in determining the very identity conditions of works of literary art. We examine some accounts that have been given of the type of readerly ‘competence’ that a reader must have in order for her responses to a text to play this sort of constitutive role. We argue that (...) the analogy drawn by Stanley Fish and Jonathan Culler between literary and linguistic competence is philosophically flawed and explanatorily unfruitful, and that a better way of understanding the notion of literary competence can be constructed by appeal to some limitation results in formal logic and computability theory. (shrink)

A computer simulation runs a model generating a phenomenon under investigation. For the simulation to be explanatory, the model has to be explanatory. The model must be isomorphic to the natural system that realizes the phenomenon. This paper elaborates the method of assessing a simulation's explanatory power. Then it illustrates the method by applying it to two simulations in game theory. The first is Brian Skyrms's (1990) simulation of interactive deliberations. It is intended to explain the emergence of a (...) Nash equilibrium in a noncooperative game. The second is Skyrms's (2004) simulation of the evolution of cooperation. It is intended to explain cooperation in assurance games. The final section suggests ways of enhancing the explanatory power of these simulations. (shrink)

Computability theory is the mathematical theory of algorithms, which explores the power and limitations of computation. Classical computability theory formalized the intuitive notion of an algorithm and provided a theoretical basis for digital computers. It also demonstrated the limitations of algorithms and showed that most sets of natural numbers and the problems they encode are not decidable (Turing computable). Important results of modern computability theory include the classification of the computational difficulty of sets and problems. (...) Arithmetical and hyperarithmetical hierarchies and the Turing degrees provide important measures of the level of such difficulty. There are uncountably many Turing degrees and they are partially ordered. These classifications are used in contemporary research to investigate the complexity of problems in modern computable mathematics, for example, regarding structures and their properties. (shrink)

According to Marr, a computational-level theory consists of two elements, the what and the why . This article highlights the distinct role of the Why element in the computational analysis of vision. Three theses are advanced: ( a ) that the Why element plays an explanatory role in computational-level theories, ( b ) that its goal is to explain why the computed function (specified by the What element) is appropriate for a given visual task, and ( c ) that (...) the explanation consists in showing that the functional relations between the representing cells are similar to the “external” mathematical relations between the entities that these cells represent. *Received September 2009; revised January 2010. †To contact the author, please write to: Departments of Philosophy and Cognitive Science, The Hebrew University, Jerusalem 91905, Israel; e-mail: shagrir@cc.huji.ac.il. (shrink)

Economies are complicated systems encompassing micro behaviors, interaction patterns, and global regularities. Whether partial or general in scope, studies of economic systems must consider how to handle difficult real-world aspects such as asymmetric information, imperfect competition, strategic interaction, collective learning, and the possibility of multiple equilibria. Recent advances in analytical and computational tools are permitting new approaches to the quantitative study of these aspects. One such approach is Agent-based Computational Economics (ACE), the computational study of economic processes modeled as dynamic (...) systems of interacting agents. This chapter explores the potential advantages and disadvantages of ACE for the study of economic systems. General points are concretely illustrated using an ACE model of a two-sector decentralized market economy. Six issues are highlighted: Constructive understanding of production, pricing, and trade processes; the essential primacy of survival; strategic rivalry and market power; behavioral uncertainty and learning; the role of conventions and organizations; and the complex interactions among structural attributes, institutional arrangements, and behavioral dispositions. (shrink)

There are quantum solutions for computational problems that make use of interference at some stage in the algorithm. These stages can be mapped into the physical setting of a single particle travelling through a many-armed interferometer. There has been recent foundational interest in theories beyond quantum theory. Here, we present a generalized formulation of computation in the context of a many-armed interferometer, and explore how theories can differ from quantum theory and still perform distributed calculations in this (...) set-up. We shall see that quaternionic quantum theory proves a suitable candidate, whereas box-world does not. We also find that a classical hidden variable model first presented by Spekkens : 32100, 2007) can also be used for this type of computation due to the epistemic restriction placed on the hidden variable. (shrink)