We introduce the computable FS-jump, an analog of the classical Friedman–Stanley jump in the context of equivalence relations on the natural numbers. We prove that the computable FS-jump is proper with respect to computable reducibility. We then study the effect of the computable FS-jump on computably enumerable equivalence relations (ceers).

We examine the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ of equivalence relations on $\omega $ under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and dark (...) degrees are definable in $\operatorname {\mathrm {\mathbf {ER}}}$. We show that every equivalence relation has continuum many self-full strong minimal covers, and that $\mathbf {d}\oplus \mathbf {\operatorname {\mathrm {\mathbf {Id}}}_1}$ needn’t be a strong minimal cover of a self-full degree $\mathbf {d}$. Finally, we show that the theory of the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ as well as the theories of the substructures of light degrees and of dark degrees are each computably isomorphic with second-order arithmetic. (shrink)

We study the degree structure of the ω-c.e., n-c.e., and Π10 equivalence relations under the computable many-one reducibility. In particular, we investigate for each of these classes of degrees the most basic questions about the structure of the partial order. We prove the existence of the greatest element for the ω-c.e. and n-computably enumerable equivalence relations. We provide computable enumerations of the degrees of ω-c.e., n-c.e., and Π10 equivalence relations. We prove that for all the degree classes (...) considered, upward density holds and downward density fails. (shrink)

We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, RQ, Q, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of RQ, Q is undecidable.

Reduced forms such as the pronoun he provide little information about their intended meaning compared to more elaborate descriptions such as the lead singer of Coldplay. Listeners must therefore use contextual information to recover their meaning. Across languages, there appears to be a trade‐off between the informativity of a form and the prominence of its referent. For example, Italian adults generally interpret informationally empty null pronouns as in the sentence Corre (meaning “He/She/It runs”) as referring to the most prominent referent (...) in the discourse, and more informative overt pronouns (e.g., lui in Lui corre, “He runs”) as referring to less prominent referents. Although children acquiring Italian are known to experience difficulties interpreting pronouns, it is unclear how they acquire this division of pragmatic labor between null and overt subject pronouns, and how this relates to the development of their cognitive capacities. Here we show that cognitive development can account for the general interpretation patterns displayed by Italian‐speaking children and adults. Using experimental studies and computational simulations in a framework modeling bounded‐rational behavior, we argue that null pronoun interpretation is influenced by working memory capacity and thus appears to depend on discourse context, whereas overt pronoun interpretation is influenced by processing speed, suggesting that listeners must reason about the speaker's choices. Our results demonstrate that cognitive capacities may constrain the acquisition of linguistic forms and their meanings in various ways. The novel predictions generated by the computational simulations point out several directions for future research. (shrink)

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e‐reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non‐deterministic polynomial time reducibility. We define the polynomial time e‐degrees as the equivalence classes under this reducibility and (...) investigate their structure on the recursive sets, showing in particular that the pe‐degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy. (shrink)

The computer is a threat to the intellectual and moral education of students. It reduces words to their most abstract meaning, thereby objectifying meaning. Moreover, the computer promotes logical thought at the expense of dialectical thinking. The computer is behind the proliferation of random information, all of which is at the disposal of the individual user. This fosters a cynical worldview that information is random and exists to be exploited. Finally, the computer turns us into consumers of information that fragments (...) the personality and makes moral responsibility increasingly difficult. It allows for anonymous discourse and substitutes information for judgment. Teachers should resist the use of the mass media—especially the computer and television—as much as possible. (shrink)

The Friedman–Stanley jump, extensively studied by descriptive set theorists, is a fundamental tool for gauging the complexity of Borel isomorphism relations. This paper focuses on a natural computable analog of this jump operator for equivalence relations on $\omega $, written ${\dotplus }$, recently introduced by Clemens, Coskey, and Krakoff. We offer a thorough analysis of the computable Friedman–Stanley jump and its connections with the hierarchy of countable equivalence relations under the computable reducibility $\leq _c$. In particular, (...) we show that this jump gives benchmark equivalence relations going up the hyperarithmetic hierarchy and we unveil the complicated highness hierarchy that arises from ${\dotplus }$. (shrink)

Using computable reducibility ⩽ on equivalence relations, we investigate weakly precomplete ceers (a “ceer” is a computably enumerable equivalence relation on the natural numbers), and we compare their class with the more restricted class of precomplete ceers. We show that there are infinitely many isomorphism types of universal (in fact uniformly finitely precomplete) weakly precomplete ceers, that are not precomplete; and there are infinitely many isomorphism types of non‐universal weakly precomplete ceers. Whereas the Visser space of a precomplete (...) ceer always contains an infinite effectively discrete subset, there exist weakly precomplete ceers whose Visser spaces do not contain infinite effectively discrete subsets. As a consequence, contrary to precomplete ceers which always yield partitions into effectively inseparable sets, we show that although weakly precomplete ceers always yield partitions into computably inseparable sets, nevertheless there are weakly precomplete ceers for which no equivalence class is creative. Finally, we show that the index set of the precomplete ceers is Σ3‐complete, whereas the index set of the weakly precomplete ceers is Π3‐complete. As a consequence of these results, we also show that the index sets of the uniformly precomplete ceers and of the e‐complete ceers are Σ3‐complete. (shrink)

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)

A problem is a situation in which an agent seeks to attain a given goal without knowing how to achieve it. Human problem solving is typically studied as a search in a problem space composed of states (information about the environment) and operators (to move between states). A problem such as playing a game of chess has possible states, and a traveling salesperson problem with as little as 82 cities already has more than different tours (similar to chess). Biological neurons (...) are slower than the digital switches in computers. An exhaustive search of the problem space exceeds the capacity of current computers for most interesting problems, and it is fairly clear that humans cannot in their lifetime exhaustively search even small fractions of these problem spaces. Yet, humans play chess and solve logistical problems of similar complexity on a daily basis. Even for simple problems humans do not typically engage in exploring even a small fraction of the problem space. This begs the question: How do humans solve problems on a daily basis in a fast and efficient way? Recent work suggests that humans build a problem representation and solve the represented problem—not the problem that is out there. The problem representation that is built and the process used to solve it are constrained by limits of cognitive capacity and a cost–benefit analysis discounting effort and reward. In this article, we argue that better understanding the way humans represent and solve problems using heuristics can help inform how simpler algorithms and representations can be used in artificial intelligence to lower computational complexity, reduce computation time, and facilitate real-time computation in complex problem solving. (shrink)

Different characterizations of classes of shift dynamical systems via labeled digraphs, languages, and sets of forbidden words are investigated. The corresponding naming systems are analyzed according to reducibility and particularly with regard to the computability of the topological entropy relative to the presented naming systems. It turns out that all examined natural representations separate into two equivalence classes and that the topological entropy is not computable in general with respect to the defined natural representations. However, if a specific (...) labeled digraph representation - namely primitive, right-resolving labeled digraphs - of some class of shifts is considered, namely the shifts having the specification property, then the topological entropy gets computable. (shrink)

With the mutual exchange and integration of world football, modern football is in an increasingly comprehensive direction. This research mainly discusses complexity computer simulation in the study of the overall play of campus football. Complexity computer simulation is used to design the background of the simulated football field, and the area is divided according to the size ratio of the actual football field. Then, it uses drawing software to draw the football and player controls. The construction of the knowledge base (...) of this paper is mainly combined with the functional modules of rapid formation and response tactics. In the fast formation function, the required formation can be quickly given through football experience and knowledge rules. In the applied tactics function, for the responsibilities of forwards, midfielders, defenders, and other roles, the tactics implemented are given, including partially coordinated offensive and defensive tactics, personal offensive and defensive tactics, and set-ball tactics. The “holistic play” football tactics studied in this paper use XML files as recording and playback data, which not only greatly reduce the amount of file data but also make the operation of XML files intuitive and simple. XML can not only realize the recording and playback of player and football track but also be used in the function of rapid formation. The coach uses the “holistic play” football tactics simulation to demonstrate the movement route through the image, guide the players in each position to perceive the game scene by observing the movement route, and analyze and judge the tactical coordination of their respective positions. The computer simulation tactical analysis of the precision of the passing and running and the path coefficient of the passing factor is 0.606 and 0.59, respectively. This research helps to provide guidance on the overall playing tactics of football. (shrink)

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity (...) bounded Turing degrees of c.e. sets are not dense [2]), however the problem for the computable Lipschitz degrees is more complex. (shrink)

The problem of computational complexity of semantics for some natural language constructions – considered in [M. Mostowski, D. Wojtyniak 2004] – motivates an interest in complexity of Ramsey quantifiers in finite models. In general a sentence with a Ramsey quantifier R of the following form Rx, yH(x, y) is interpreted as ∃A(A is big relatively to the universe ∧A2 ⊆ H). In the paper cited the problem of the complexity of the Hintikka sentence is reduced to the problem of computational (...) complexity of the Ramsey quantifier for which the phrase “A is big relatively to the universe” is interpreted as containing at least one representative of each equivalence class, for some given equvalence relation. In this work we consider quantifiers Rf, for which “A is big relatively to the universe” means “card(A) > f (n), where n is the size of the universe”. Following [Blass, Gurevich 1986] we call R mighty if Rx, yH(x, y) defines N P – complete class of finite models. Similarly we say that Rf is N P –hard if the corresponding class is N P –hard. We prove the following theorems. (shrink)

We present a computational evaluation of three hypotheses about sources of deficit in sentence comprehension in aphasia: slowed processing, intermittent deficiency, and resource reduction. The ACT-R based Lewis and Vasishth model is used to implement these three proposals. Slowed processing is implemented as slowed execution time of parse steps; intermittent deficiency as increased random noise in activation of elements in memory; and resource reduction as reduced spreading activation. As data, we considered subject vs. object relative sentences, presented in a self-paced (...) listening modality to 56 individuals with aphasia and 46 matched controls. The participants heard the sentences and carried out a picture verification task to decide on an interpretation of the sentence. These response accuracies are used to identify the best parameters that correspond to the three hypotheses mentioned above. We show that controls have more tightly clustered parameter values than IWA; specifically, compared to controls, among IWA there are more individuals with slow parsing times, high noise, and low spreading activation. We find that individual IWA show differential amounts of deficit along the three dimensions of slowed processing, intermittent deficiency, and resource reduction, overall, there is evidence for all three sources of deficit playing a role, and IWA have a more variable range of parameter values than controls. An important implication is that it may be meaningless to talk about sources of deficit with respect to an abstract verage IWA; the focus should be on the individual's differential degrees of deficit along different dimensions, and on understanding the causes of variability in deficit between participants. (shrink)

This article concerns the curriculum of computer literacy (CL). A strong sense of technical necessity informs the design of the CL curriculum, and as a result, instruction is inadequate at best and dehumanizing at worst. CL curriculum and instruction are informed by a sense of technical determinism and a particular form of masculinity. This article draws mainly from the sociology of education, supplemented by personal observation. The article has two implications. First, to reduce the failure and frustration that many feel (...) as they attempt to become computer literate, greater attention ought to be given in CL curriculum design to the concept of learning as enculturation and to cognitive context. Second, to counter the sense of necessity that leads designers and others to ignore culture and context, the formal CL curriculum must give serious attention to the social construction of educational technology/technique, especially the in fluence of gender. (shrink)

Continuous reducibilities are a proven tool in Computable Analysis, and have applications in other fields such as Constructive Mathematics or Reverse Mathematics. We study the order-theoretic properties of several variants of the two most important definitions, and especially introduce suprema for them. The suprema are shown to commutate with several characteristic numbers.

The investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single-valued as well as for multi-valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for functions and corresponding (...) complete functions. We use this classification and an effective version of a Selection Theorem of Bhattacharya-Srivastava in order to prove a generalization of the Representation Theorem of Kreitz-Weihrauch for Borel measurable functions on computable metric spaces: such functions are Borel measurable on a certain finite level, if and only if they admit a realizer on Baire space of the same quality. This Representation Theorem enables us to introduce a realizer reducibility for functions on metric spaces and we can extend the completeness result to this reducibility. Besides being very useful by itself, this reducibility leads to a new and effective proof of the Banach-Hausdorff-Lebesgue Theorem which connects Borel measurable functions with the Baire functions. Hence, for certain metric spaces the class of Borel computable functions on a certain level is exactly the class of functions which can be expressed as a limit of a pointwise convergent and computable sequence of functions of the next lower level. (shrink)

Regarding the continuous development of high-speed trains and the increase of running speeds, the aerodynamic design of high-speed trains has become significantly important, while reduction of drag and noise comprises a significant challenge in order to optimize aerodynamic design of high-speed trains. The design form factor of a high-speed train is highly influenced by aerodynamic aspects including aerodynamic drag, lift force, and noise. With the high-speed train as the object, the paper aims to take bionic concept as the entry point, (...) selecting the hummingbird as the bionic prototype and extracting bionic elements to establish a bionic train model. Then, the finite volume method was used for numerical simulation and analysis of the aerodynamic performance and aerodynamic noise of the bionic high-speed train. Computational results prove that drag and noise of the bionic head type were lower than those of the original train; drag of the head train of the bionic model was reduced by 2.21% in comparison with the original model, while the whole-train drag was reduced by 3.53%, indicating that drag reduction effects are available and implying that the bionic head type could reduce drag and noise. Noise sources of the bionic train are mainly located at positions with easy airflow separation and violent turbulence motion. Large turbulence energy is in bogie areas and mainly exists at the leeward side of the bogie area. Obviously, the bogie area is the major noise source of the train. Aerodynamic noise of the bionic train in far-field comprises a wide-frequency range. Noises were concentrated within 613 Hz~3150 Hz. When the bionic high-speed train ran at 350 km/h, through comparative analysis of total noise levels at observed points of the high-speed train, it is found that this position with the maximum noise level was 25 m away from the head train nose tip, with the maximum value of 88.4 dB. When the bionic train ran at 600 km/h, the maximum sound pressure level at the longitudinal point was 99.7 dB and the average noise level was 96.6 dB. When the running speed increased from 350 km/h to 600 km/h, the maximum noise level increased by 11.3 dB and the average noise level increased by 11.6 dB. Computation results of aerodynamic noise at the point which is 7.5 m away from the rail center show that the maximum aerodynamic noise level existed at the first-end bogie of the head train, while the noise level was larger at the position closer to the ground. (shrink)

The extended reduced Kies distribution, which is an asymmetric flexible extension of the reduced Kies distribution, is the subject of this research. Some of its most basic mathematical properties are deduced from its formal definitions. We computed the ExRKD parameters using eight well-known methods. A full simulation analysis was done that allows the study of these estimators’ asymptotic behavior. The efficiency and applicability of the ExRKD are investigated via the modeling of COVID-19 and milk data sets, which demonstrates that the (...) ExRKD delivers a better match to the data sets when compared to competing models. (shrink)

We introduce agreement reducibility and highlight its major features. Given subsets A and B of, we write if there is a total computable function satisfying for all,.We shall discuss the central role plays in this reducibility and its connection to strong‐hyper‐hyper‐immunity. We shall also compare agreement reducibility to other well‐known reducibilities, in particular s1‐ and s‐reducibility. We came upon this reducibility while studying the computable reducibility of a class of equivalence relations on (...) based on set‐agreement. We end by describing the origin of agreement reducibility and presenting some results in that context. (shrink)

Polynomial clone reducibilities are generalizations of the truth-table reducibilities. A polynomial clone is a set of functions over a finite set X that is closed under composition and contains all the constant and projection functions. For a fixed polynomial clone ${\fancyscript{C}}$ , a sequence ${B\in X^{\omega}}$ is ${\fancyscript{C}}$ -reducible to ${A \in {X}^{\omega}}$ if there is an algorithm that computes B from A using only effectively selected functions from ${\fancyscript{C}}$ . We show that if A is Kurtz random and ${\fancyscript{C}_{1} (...) \nsubseteq \fancyscript{C}_{2}}$ are polynomial clones, then there is a B that is ${\fancyscript{C}_{1}}$ -reducible to A but not ${\fancyscript{C}_{2}}$ -reducible to A. This implies a generalization of a result first proved by Lachlan (Z Math Logik Grundlagen Math 11:17–44, 1965) for the case |X| = 2. We also show that the same result holds if Kurtz random is replaced by Kolmogorov–Loveland stochastic. (shrink)

If r is a reducibility between sets of numbers, a natural question to ask about the structure ? r of the r-degrees containing computably enumerable sets is whether every element not equal to the greatest one is branching (i.e., the meet of two elements strictly above it). For the commonly studied reducibilities, the answer to this question is known except for the case of truth-table (tt) reducibility. In this paper, we answer the question in the tt case by (...) showing that every tt-incomplete computably enumerable truth-table degree a is branching in ? tt . The fact that every Turing-incomplete computably enumerable truth-table degree is branching has been known for some time. This fact can be shown using a technique of Ambos-Spies and, as noticed by Nies, also follows from a relativization of a result of Degtev. We give a proof here using the Ambos-Spies technique because it has not yet appeared in the literature. The proof uses an infinite injury argument. Our main result is the proof when a is Turing-complete but tt-incomplete. Here we are able to exploit the Turing-completeness of a in a novel way to give a finite injury proof. (shrink)

There are many social psychological theories regarding the nature of prejudice, but only one major theory of prejudice reduction: under the right circumstances, prejudice between groups will be reduced with increased contact. On the one hand, the contact hypothesis has a range of empirical support and has been a major force in social change. On the other hand, there are practical and ethical obstacles to any large-scale controlled test of the hypothesis in which relevant variables can be manipulated. Here we (...) construct a spatialized model that tests the core hypothesis in a large array of game-theoretic agents. Robust results offer a new kind of support for the contact hypothesis: results in simulation do accord with a hypothesis of reduced prejudice with increased contact. The spatialized game-theoretic model also suggests a deeper explanation for at least some of the social psychological phenomena at issue. (shrink)

Detractors of Searle’s Chinese Room Argument have arrived at a virtual consensus that the mental properties of the Man performing the computations stipulated by the argument are irrelevant to whether computational cognitive science is true. This paper challenges this virtual consensus to argue for the first of the two main theses of the persons reply, namely, that the mental properties of the Man are what matter. It does this by challenging many of the arguments and conceptions put forth by the (...) systems and logical replies to the Chinese Room, either reducing them to absurdity or showing how they lead, on the contrary, to conclusions the persons reply endorses. The paper bases its position on the Chinese Room Argument on additional philosophical considerations, the foundations of the theory of computation, and theoretical and experimental psychology. The paper purports to show how all these dimensions tend to support the proposed thesis of the persons reply. (shrink)

The authors investigated the ontological argument computationally. The premises and conclusion of the argument are represented in the syntax understood by the automated reasoning engine PROVER9. Using the logic of definite descriptions, the authors developed a valid representation of the argument that required three non-logical premises. PROVER9, however, discovered a simpler valid argument for God's existence from a single non-logical premise. Reducing the argument to one non-logical premise brings the investigation of the soundness of the argument into better focus. Also, (...) the simpler representation of the argument brings out clearly how the ontological argument constitutes an early example of a ‘diagonal argument’ and, moreover, one used to establish a positive conclusion rather than a paradox. (shrink)

We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers.

We show that the number-theoretic functions definable in the atomic polymorphic system are exactly the extended polynomials. Two proofs of the above result are presented: one, reducing the functions’ definability problem in ${\mathbf{F}}_{\mathbf{at}}$ to definability in the simply typed lambda calculus and the other, directly adapting Helmut Schwichtenberg’s strategy for definability in $\lambda ^{\rightarrow }$ to the atomic polymorphic setting. The uniformity granted in the polymorphic system, when compared with the simply typed lambda calculus, is emphasized.

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

All epistemic agents physically consist of parts that must somehow comprise an integrated cognitive self. Biological individuals consist of subunits (organs, cells, molecular networks) that are themselves complex and competent in their own context. How do coherent biological Individuals result from the activity of smaller sub-agents? To understand the evolution and function of metazoan bodies and minds, it is essential to conceptually explore the origin of multicellularity and the scaling of the basal cognition of individual cells into a coherent larger (...) organism. In this paper I synthesize ideas in cognitive science, evolutionary biology, and developmental physiology toward a hypothesis about the origin of Individuality: “Scale-Free Cognition”. I propose a fundamental definition of an Individual based on the ability to pursue goals at an appropriate level of scale and organization, and suggest a formalism for defining and comparing the cognitive capacities of highly diverse types of agents. Any Self is demarcated by a computational surface – the spatio-temporal boundary of events that it can measure, model, and try to affect. This surface sets a functional boundary - a cognitive “light cone” which defines the scale and limits of its cognition. I hypothesize that higher-level goal-directed activity and agency, resulting in larger cognitive boundaries, evolve from the primal homeostatic drive of living things to reduce stress – the difference between current conditions and life-optimal conditions. The mechanisms of developmental bioelectricity - the ability of all cells to form electrical networks that process information - suggests a plausible set of gradual evolutionary steps that naturally lead from physiological homeostasis in single cells to memory, prediction, and ultimately complex cognitive agents, via scale-up of the drive of infotaxis. Recent data on the molecular mechanisms of pre-neural bioelectricity suggest a model of how increasingly sophisticated cognitive functions emerge smoothly from cell-cell communication used to guide embryogenesis and regeneration. This set of hypotheses provides a novel perspective on numerous phenomena, such as cancer, and makes several unique, testable predictions for interdisciplinary research that have implications not only for evolutionary developmental biology but also for biomedicine and perhaps artificial intelligence and exobiology. (shrink)

Computers may help us to better understand (not just verify) arguments. In this article we defend this claim by showcasing the application of a new, computer-assisted interpretive method to an exemplary natural-language ar- gument with strong ties to metaphysics and religion: E. J. Lowe’s modern variant of St. Anselm’s ontological argument for the existence of God. Our new method, which we call computational hermeneutics, has been particularly conceived for use in interactive-automated proof assistants. It aims at shedding light on the (...) meanings of words and sentences by framing their inferential role in a given argument. By employing automated theorem reasoning technology within interactive proof assistants, we are able to drastically reduce (by several orders of magnitude) the time needed to test the logical validity of an argu- ment’s formalization. As a result, a new approach to logical analysis, inspired by Donald Davidson’s account of radical interpretation, has been enabled. In computational hermeneutics, the utilization of automated reasoning tools ef- fectively boosts our capacity to expose the assumptions we indirectly commit ourselves to every time we engage in rational argumentation and it fosters the explicitation and revision of our concepts and commitments. (shrink)

Degtev, A.N., On p-reducibility of numerations, Annals of Pure and Applied Logic 63 57–60. If α and β are two numerations of a set S, then αpβ if there exists a total recursive function f such that [s ε S][α-1=[x:[y ε Df][Dyβ-1]]], where Dn is a finite set with canonical number n. It is proved that if α and β are two computable numerations of some family of recursively enumerable sets A and αpβ, then there is a (...) class='Hi'>computable numeration, γ, of S such that αpγ and βshrink)

Sieg has proposed axioms for computability whose models can be reduced to Turing machines. This lecture will investigate to what extent these axioms hold for reasoning. In particular we focus on the requirement that the configurations that a computing agent (whether human or machine) operates on must be ’immediately recognisable’. If one thinks of reasoning as derivation in a calculus, this requirement is satisfied; but even in contexts which are only slightly less formal, the requirement cannot be met. Our main (...) example will be the Wason selection task, a propositional reasoning task in which in a typical (undergraduate) subject group only around 5% arrive at the answer dictated by classical logic. The instructions for this task (as well as other standard tasks in the psychology of reasoning, such as syllogisms) do not contain any ’immediately recognisable’ configurations. The subject must try to find an interpretation of the task by making the various elements in the instructions cohere, in effect solving a difficult constraint satisfaction problem, which has no unique solution. The subject has given a complete interpretation of the task if she can formulate the problem posed in the task as a theorem to be proved. The complexity of such theorems can be quite high; e.g. for the propositional Wason selection task the theorem can be in Σ1 3 . This sounds implausible, but we’ll present experimental data confirming this point. (shrink)

Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth-table Schnorr randomness and truth-table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth-table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van (...) Lambalgen's Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth-table Schnorr randomness. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

We study a strong enumeration reducibility, called bounded enumeration reducibility and denoted by ≤be, which is a natural extension of s-reducibility ≤s. We show that ≤s, ≤be, and enumeration reducibility do not coincide on the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} –sets, and the structure \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{\mathcal{D}_{\rm be}}}$$\end{document} of the be-degrees is not elementarily equivalent to the structure of the s-degrees. We show also that (...) the first order theory of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{\mathcal{D}_{\rm be}}}$$\end{document} is computably isomorphic to true second order arithmetic: this answers an open question raised by Cooper (Z Math Logik Grundlag Math 33:537–560, 1987). (shrink)

The introduction of computer-based information systems to be used by farmers, as in many other fields, is preceded mostly by great expectations. Some persons even tend to think that eventually the computer might take over farm management. This article tries to make an assessment of the validity of such expectations. Based upon a study among Swedish farmers, it examines the nature of farmers' decision-making. The latter is based upon an adaptive rationality, as opposed to the normative models of formal rationality (...) used by scientists. Essential to this rationality are coordination skills: the ability of farmers to arrange the many interacting factors important to the totality of a farm in a satisfactory way. What the farmer needs in this complex situation is personal communication and tacit knowledge, knowledge that cannot be reduced to facts and rules. Consequently computer-based information systems can be useful tools only in some aspects of farm management, but they will never replace farmer's decision-making. To understand the possibilities of the computer as a tool in farm management, a distinction between interpretation skills and application skills is necessary. (shrink)