arbitrary flowchart programs by introducing a new recursive function for each tag point. In the above example, one obtains: int(x) = int1(x,0), p(n,¤| ,... .ur. ¢(¤.vH(¤.¤,.~¤,) ..... 1 h(n.c¤| ..... ¤r)), w(n.y2l(n.¤l ,.... ul,) ...., y2r(n,a|,_,,¤l_))_..
Humans grasp discrete infinities within several cognitive domains, such as in language, thought, social cognition and tool-making. It is sometimes suggested that any such generative ability is based on a computational system processing hierarchical and recursive mental representations. One view concerning such generativity has been that each of the mind’s modules defining a cognitive domain implements its own recursive computational system. In this paper recent evidence to the contrary is reviewed and it is proposed that there is only (...) one supramodal computational system with recursion in the human mind. A recursion thesis is defined, according to which the hominin cognitive evolution is constituted by a recent punctuated genetic mutation that installed the general, supramodal capacity for recursion into the human nervous system on top of the existing, evolutionarily older cognitive structures, and it is argued on the basis of empirical evidence and theoretical considerations that the recursion thesis constitutes a plausible research program for cognitive science. (shrink)
Taken at face value, a programming language is defined by a formal grammar. But, clearly, there is more to it. By themselves, the naked strings of the language do not determine when a program is correct relative to some specification. For this, the constructs of the language must be given some semantic content. Moreover, to be employed to generate physical computations, a programming language must have a physical implementation. How are we to conceptualize this complex package? Ontologically, what (...) kind of thing is it? In this paper, we shall argue that an appropriate conceptualization is furnished by the notion of a technical artifact. (shrink)
In this paper we continue, from [2], the development of provably recursive analysis, that is, the study of real numbers defined by programs which can be proven to be correct in some fixed axiom system S. In particular we develop the provable analogue of an effective operator on the set C of recursive real numbers, namely, a provably correct operator on the set P of provably recursive real numbers. In Theorems 1 and 2 we exhibit a provably (...) correct operator on P which is discontinuous at 0; we thus disprove the analogue of the Ceitin-Moschovakis theorem of recursive analysis, which states that every effective operator on C is (effectively) continuous. Our final theorems show, however, that no provably correct operator on P can be proven (in S) to be discontinuous. (shrink)
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.
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)
This graduate-level_text by a master in the field builds a function theory of the rational field that combines aspects of classical and intuitionist analysis. Topics include recursive convergence, recursive and relative continuity, recursive and relative differentiability, the relative integral, elementary functions, and transfinite ordinals. 1961 edition.
At the phenomenal level, consciousness arises in a consistently coherent fashion as a singular, unified field of recursive self-awareness (subjectivity) with explicitly orientational characteristics—that of a subject located both spatially and temporally in an egocentrically-extended domain. Understanding these twin elements of consciousness begins with the recognition that ultimately (and most primitively), cognitive systems serve the biological self-regulatory regime in which they subsist. The psychological structures supporting self-located subjectivity involve an evolutionary elaboration of the two basic elements necessary for extending (...) self-regulation into behavioral interaction with the environment: an orientative reference frame which consistently structures ongoing interaction in terms of controllable spatiotemporal parameters, and processing architecture that relates behavior to homeostatic needs via feedback. Over time, constant evolutionary pressures for energy efficiency have encouraged the emergence of anticipative feedforward processing mechanisms, and the elaboration, at the apex of the sensorimotor processing hierarchy, of self-activating, highly attenuated recursively-feedforward circuitry processing the basic orientational schema independent of external action output. As the primary reference frame of active waking cognition, this recursive self-locational schema processing generates a zone of subjective self-awareness in terms of which it feels like something to be oneself here and now. This is consciousness-as-subjectivity. (shrink)
Taking Chomsky’s Syntactic Structures as a starting point, this paper explores the use of recursive techniques in contemporary linguistic theory. Specifically, it is shown that there were profound ambiguities surrounding the notion of recursion in the 1950s, and that this was partly due to the fact that influential texts such as Syntactic Structures neglected to define what exactly constituted a recursive device. As a result, uncertainties concerning the role of recursion in linguistic theory have prevailed until the present (...) day, and some of the most common misunderstandings that have appeared in recent discussions are examined at some length. This article shows that debates about such topics are frequently undermined by fundamental misunderstandings concerning core terminology, and the full extent of the prevailing haziness is revealed. An attempt is made, for instance, to distinguish between such things as iterative constructional devices and self-similar syntactic embedding, despite the fact that these are usually both unhelpfully classified as examples of recursion. Consequently, this article effectively constitutes a plea for much greater accuracy and clarity when such important issues are addressed from a linguistic perspective. (shrink)
of type theory has been used successfully to formalize large parts of constructive mathematics, such as the theory of generalized recursive definitions [NPS90, ML79]. Moreover, it is also employed extensively as a framework for the development of high-level programming languages, in virtue of its combination of expressive strength and desirable proof-theoretic properties [NPS90, Str91]. In addition to simple types A, B, . . . and their terms x : A b(x) : B, the theory also has dependent types (...) x : A B(x), which are regarded as indexed families of types. There are simple type forming operations A × B and A → B, as well as operations on dependent types, including in particular the sum x:A B(x) and product x:A B(x) types (see the appendix for details). The Curry-Howard interpretation of the operations A × B and A → B is as propositional conjunction and.. (shrink)
1. Logic programming did not seize the attention of most programmers until the Japanese announced that they had chosen Prolog for their ambitious Fifth Generation Computer Systems project. While that project appeàrs now to be hampered by bureaucratic difficulties, the interest it aroused in Prolog lives on. Part of the attraction of Prolog stems from the fact that the beginner will very quickly be able to write toy programs, even spectacular ones. Difficulties in creating larger programs, however, seem to (...) bring back Prolog to the level of other programming languages. Such difficulties arise from numerous defects of Prolog, some of which are purely logicai in nature. Among the latter at least two should be mentioned: (a) the peculiar meaning of negation; (b) the fact that reduction to clausal form is not part of the language. As to (a), strictly speaking Prolog has no negation. Its notion ot.negation- as-failure - by which -i <p is inferred from fatture to infer y - is a tricky one. For instance, suppose that the goal likes (John, X ) succeeds with X instantiated to mary. Then not (likes (John, X )) fails, so X becomes uninstantiated and hence has no value. However not (not (likes (John, X ))) succeeds with X instantiated to mary. This makes the meaning of negation almost incomprehensible. As to (b), for efficiency Prolog uses the programmer, as it were, as a preprocessor for reduction to clausal form: with the gain in efficiency that one can very well imagine. Of course reduction to clausal form can be implemented in Prolog and bùilt up within every Prolog program together with a suitable user interface, but this is very much like designing a new programming language. (shrink)
A realizability notion that employs only primitive recursive functions is defined, and, relative to it, the soundness of the fragment of Heyting Arithmetic (HA) in which induction is restricted to Σ 0 1 formulae is proved. A dual concept of falsifiability is proposed and an analogous soundness result is established for a further restricted fragment of HA.
An emerging standard for polymorphically typed, lazy, purely functional programming is Haskell, a language named after Haskell Curry. Haskell is based on (polymorphically typed) lambda calculus, which makes it an excellent tool for computational semantics.
The first part of the paper introduces the varieties of modern constructive mathematics, concentrating on Bishop's constructive mathematics (BISH). it gives a sketch of both Myhill's axiomatic system for BISH and a constructive axiomatic development of the real line R. The second part of the paper focusses on the relation between constructive mathematics and programming, with emphasis on Martin-L6f 's theory of types as a formal system for BISH.
The “DNA is a program” metaphor is still widely used in Molecular Biology and its popularization. There are good historical reasons for the use of such a metaphor or theoretical model. Yet we argue that both the metaphor and the model are essentially inadequate also from the point of view of Physics and Computer Science. Relevant work has already been done, in Biology, criticizing the programming paradigm. We will refer to empirical evidence and theoretical writings in Biology, although our (...) arguments will be mostly based on a comparison with the use of differential methods (in Molecular Biology: a mutation or alike is observed or induced and its phenotypic consequences are observed) as applied in Computer Science and in Physics, where this fundamental tool for empirical investigation originated and acquired a well-justified status. In particular, as we will argue, the programming paradigm is not theoretically sound as a causal(as in Physics) or deductive(as in Programming) framework for relating the genome to the phenotype, in contrast to the physicalist and computational grounds that this paradigm claims to propose. (shrink)
At the phenomenal level, consciousness can be described as a singular, unified field of recursive self-awareness, consistently coherent in a particualr way; that of a subject located both spatially and temporally in an egocentrically-extended domain, such that conscious self-awareness is explicitly characterized by I-ness, now-ness and here-ness. The psychological mechanism underwriting this spatiotemporal self-locatedness and its recursive processing style involves an evolutionary elaboration of the basic orientative reference frame which consistently structures ongoing spatiotemporal self-location computations as i-here-now. Cognition (...) computes action-output in the midst of ongoing movement, and consequently requires a constant self-locating spatiotemporal reference frame as basis for these computations. Over time, constant evolutionary pressures for energy efficiency have encouraged both the proliferation of anticipative feedforward processing mechansims, and the elaboration, at the apex of the sensorimotor processing hierarchy, of self-activating, highly attenuated recursively-feedforward circuitry processing the basic orientational schema independent of external action output. As the primary reference frame of active waking cognition, this recursive i-here-now processing generates a zone of subjective self-awareness in terms of which it feels like something to be oneself here and now. This is consciousness. (shrink)
We show that it is possible to base fuzzy control on fuzzy logic programming. Indeed, we observe that the class of fuzzy Herbrand interpretations gives a semantics for fuzzy programs and we show that the fuzzy function associated with a fuzzy system of IF-THEN rules is the fuzzy Herbrand interpretation associated with a suitable fuzzy program.
Combinatory logic and lambda-conversion were originally devised in the 1920s for investigating the foundations of mathematics using the basic concept of 'operation' instead of 'set'. They have now developed into linguistic tools, useful in several branches of logic and computer science, especially in the study of programming languages. These notes form a simple introduction to the two topics, suitable for a reader who has no previous knowledge of combinatory logic, but has taken an undergraduate course in predicate calculus and (...)recursive functions. The key ideas and basic results are presented, as well as a number of more specialised topics, and man), exercises are included to provide manipulative practice. (shrink)
The Recursive Bayesian Net (RBN) formalism was originally developed for modelling nested causal relationships. In this paper we argue that the formalism can also be applied to modelling the hierarchical structure of mechanisms. The resulting network contains quantitative information about probabilities, as well as qualitative information about mechanistic structure and causal relations. Since information about probabilities, mechanisms and causal relations is vital for prediction, explanation and control respectively, an RBN can be applied to all these tasks. We show in (...) particular how a simple two-level RBN can be used to model a mechanism in cancer science. The higher level of our model contains variables at the clinical level, while the lower level maps the structure of the cell’s mechanism for apoptosis. (shrink)
Cognitive neuroscience is the branch of neuroscience that studies the neural mechanisms underpinning cognition and develops theories explaining them. Within cognitive neuroscience, computational neuroscience focuses on modeling behavior, using theories expressed as computer programs. Up to now, computational theories have been formulated by neuroscientists. In this paper, we present a new approach to theory development in neuroscience: the automatic generation and testing of cognitive theories using genetic programming (GP). Our approach evolves from experimental data cognitive theories that explain “the (...) mental program” that subjects use to solve a specific task. As an example, we have focused on a typical neuroscience experiment, the delayed-match-to-sample (DMTS) task. The main goal of our approach is to develop a tool that neuroscientists can use to develop better cognitive theories. (shrink)
this paper we argue that the formalism can also be applied to modelling the hierarchical structure of physical mechanisms. The resulting network contains quantitative information about probabilities, as well as qualitative information about mechanistic structure and causal relations. Since information about probabilities, mechanisms and causal relations are vital for prediction, explanation and control respectively, a recursive Bayesian net can be applied to all these tasks. We show how a Recursive Bayesian Net can be used to model mechanisms in (...) cancer science. The highest level of the proposed model will contain variables at the clinical level, while a middle level will map the structure of the DNA damage response mechanism and the lowest level will contain information about gene expression. (shrink)
We study the monoid of primitive recursive functions and investigate a onestep construction of a kind of exact completion, which resembles that of the familiar category of modest sets, except that the partial equivalence relations which serve as objects are recursively enumerable. As usual, these constructions involve the splitting of symmetric idempotents.
Elephant 2000 is a proposed programming language good for writing and verifying programs that interact with people (eg. transaction processing) or interact with programs belonging to other organizations (eg. electronic data interchange) 1. Communication inputs and outputs are in an I-O language whose sentences are meaningful speech acts identified in the language as questions, answers, offers, acceptances, declinations, requests, permissions and promises. 2. The correctness of programs is partly defined in terms of proper performance of the speech acts. Answers (...) should be truthful and responsive, and promises should be kept. Sentences of logic expressing these forms of correctness can be generated automatically from the form of the program. 3. Elephant aource programs may not need data structures, because they can refer directly to the past. Thus a program can say that an airline passenger has a reservation if he has made one and hasn't cancelled it. 4. Elephant programs themselves can be represented as sentences of logic. Their extensional properties follow from this representation without an intervening theory of programming or anything like Hoare axioms. 5. Elephant programs that interact non-trivially with the outside world can have both input-output specification, relating the programs inputs and outputs, and accomplishment specifications concerning what the program accomplishes in the world. These concepts are respectively generalizations of the philosophers' illocutionary and perlocutionary speech acts. 6. Programs that engage in commercial transactions assume obligations on behalf of their owners in exchange for obligations assumed by other entities. It may be part of the specification of an Elephant 2000 program that these obligations are exchanged as intended, and this too can be expressed by a logical sentence. 7. Human speech acts involve intelligence. Elephant 2000 is on the borderline of AI, but the article emphasizes the Elephant usages that do not require AI. (shrink)
One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. (...) J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Ω-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Lof test. (shrink)
Answer-set programming (ASP) has emerged as a declarative programming paradigm where problems are encoded as logic programs, such that the so-called answer sets of theses programs represent the solutions of the encoded problem. The efficiency of the latest ASP solvers reached a state that makes them applicable for problems of practical importance. Consequently, problems from many different areas, including diagnosis, data integration, and graph theory, have been successfully tackled via ASP. In this work, we present such ASP-encodings for (...) problems associated to abstract argumentation frameworks (AFs) and generalisations thereof. Our encodings are formulated as fixed queries, such that the input is the only part depending on the actual AF to process. We illustrate the functioning of this approach, which is underlying a new argumentation system called ASPARTIX in detail and show its adequacy in terms of computational complexity. (shrink)
Recently, there have been some attempts towards developing programming languages based on situation theory. These languages employ situation-theoretic constructs with varying degrees of divergence from the ontology of the theory. In this paper, we review three of these programming languages.
A free logic is one in which a singular term can fail to refer to an existent object, for example, `Vulcan' or `5/0'. This essay demonstrates the fruitfulness of a version of this non-classical logic of terms (negative free logic) by showing (1) how it can be used not only to repair a looming inconsistency in Quine's theory of predication, the most influential semantical theory in contemporary philosophical logic, but also (2) how Beeson, Farmer and Feferman, among others, use it (...) to provide a natural foundation for partial functions in programming languages. Vis à vis (2), the question is raised whether the Beeson-Farmer-Feferman approach is adequate to the treatment of partial functions in all programming languages. Gumb and the author say No, and suggest a way of handling the refractory cases by means of positive free logic. Finally, Antonelli's solution of a problem associated with the Gumb-Lambert proposal is mentioned. (shrink)
Many believe that the grammatical sentences of a natural language are a recursive set. In this paper I argue that the commonly adduced grounds for this belief are inconclusive, if not simply unsound. Neither the native speaker's ability to classify sentences nor his ability to comprehend them requires it. Nor is there at present any reason to think that decidability has any bearing on first-language acquisition. I conclude that there are at present no compelling theoretical grounds for requiring that (...) transformational grammars enumerate only recursive sets. Hence, the fact that proposed transformational grammars do not satisfy this requirement does not, as some have claimed, represent a shortcoming in current theory. (shrink)
Web legal information retrieval systems need the capability to reason with the knowledge modeled by legal ontologies. Using this knowledge it is possible to represent and to make inferences about the semantic content of legal documents. In this paper a methodology for applying NLP techniques to automatically create a legal ontology is proposed. The ontology is defined in the OWL semantic web language and it is used in a logic programming framework, EVOLP+ISCO, to allow users to query the semantic (...) content of the documents. ISCO allows an easy and efficient integration of declarative, object-oriented and constraint-based programming techniques with the capability to create connections with external databases. EVOLP is a dynamic logic programming framework allowing the definition of rules for actions and events. An application of the proposed methodology to the legal web information retrieval system of the Portuguese Attorney General’s Office is described. (shrink)
Recent advances in genetic engineering nowallow the design of programmable biologicalartifacts. Such programming may include usageconstraints that will alter the balance ofownership and control for biotechnologyproducts. Similar changes have been analyzedin the context of digital content managementsystems, and while this previous work is usefulin analyzing issues related to biologicalprogramming, the latter technology presents new conceptual problems that require morecomprehensive evaluation of the interplaybetween law and technologically embeddedvalues. In particular, the ability to embedcontractual terms in technological artifactsnow requires a re-examination (...) of disclosure andconsent in transactions involving such artifacts. (shrink)
We propose the notion of partial recursiveness and strong partial recursiveness for fuzzy maps. We prove that a fuzzy map f is partial recursive if and only if it is computable by a Turing fuzzy machine and that f is strongly partial recursive and deterministic if and only if it is computable via a deterministic Turing fuzzy machine. This gives a simple and manageable tool to investigate about the properties of the fuzzy machines.
Given an admissible indexing φ of the countable atomless Boolean algebra B, an automorphism F of B is said to be recursively presented (relative to φ) if there exists a recursive function $p \in \operatorname{Sym}(\omega)$ such that F ⚬ φ = φ ⚬ p. Our key result on recursiveness: Both the subset of $\operatorname{Aut}(\mathscr{B})$ consisting of all those automorphisms which are recursively presented relative to some indexing, and its complement, the set of all "totally nonrecursive" automorphisms, are uncountable. This (...) arises as a consequence of the following combinatorial investigations: (1) A comparison of the cycle structures of f and f̄, where f is a permutation of some free basis of B and f̄ is the automorphism of B induced by f. (2) An explicit description of the permutations of ω whose conjugacy classes in $\operatorname{Sym}(\omega)$ are (a) uncountable, (b) countably infinite, and (c) finite. (shrink)
Abstract Pragmatism has played only a small role in the half century and more of the science-and-religion dialogue, in part because pragmatism was at a low ebb in the 1950s. Even though Jamesean pragmatism in particular is experiencing a resurgence, owing partly to the work of Rorty and Putnam, it remains inconspicuous in the dialogue. Excepting artificial intelligence and artificial life, computer science also has not played a large role in the dialogue. Recent research into the foundations of object-oriented (...) class='Hi'>programming, however, shows this increasingly pervasive practice possesses an implicit pragmatist epistemology. Although science will have to become more computational, it will have to come to terms with both object-oriented computing and its implicit pragmatism, which in turn supports the conclusion that we have fresh warrant for recasting the science-and-religion dialogue in Jamesean pragmatist terms. Some preliminary consequences of such a recasting of the dialogue are explored. (shrink)
Bilattices, due to M. Ginsberg, are a family of truth value spaces that allow elegantly for missing or conflicting information. The simplest example is Belnap’s four-valued logic, based on classical two-valued logic. Among other examples are those based on finite many-valued logics, and on probabilistic valued logic. A fixed point semantics is developed for logic programming, allowing any bilattice as the space of truth values. The mathematics is little more complex than in the classical two-valued setting, but the result (...) provides a natural semantics for distributed logic programs, including those involving confidence factors. The classical two-valued and the Kripke/Kleene three-valued semantics become special cases, since the logics involved are natural sublogics of Belnap’s logic, the logic given by the simplest bilattice. (shrink)
The classical propositional logic is known to be sound and complete with respect to the set semantics that interprets connectives as set operations. The paper extends propositional language by a new binary modality that corresponds to partial recursive function type constructor under the above interpretation. The cases of deterministic and non-deterministic functions are considered and for both of them semantically complete modal logics are described and decidability of these logics is established.
In this paper, we prove the correspondence between complete extensions in abstract argumentation and 3-valued stable models in logic programming. This result is in line with earlier work of [6] that identified the correspondence between the grounded extension in abstract argumentation and the well-founded model in logic programming, as well as between the stable extensions in abstract argumentation and the stable models in logic programming.
The variety of semantical approaches that have been invented for logic programs is quite broad, drawing on classical and many-valued logic, lattice theory, game theory, and topology. One source of this richness is the inherent non-monotonicity of its negation, something that does not have close parallels with the machinery of other programming paradigms. Nonetheless, much of the work on logic programming semantics seems to exist side by side with similar work done for imperative and functional programming, with (...) relatively minimal contact between communities. In this paper we summarize one variety of approaches to the semantics of logic programs: that based on fixpoint theory. We do not attempt to cover much beyond this single area, which is already remarkably fruitful. We hope readers will see parallels with, and the divergences from the better known fixpoint treatments developed for other programming methodologies. (shrink)
We study logical systems for reasoning about equations involving recursive definitions. In particular, we are interested in "propositional" fragments of the functional language of recursion FLR [18, 17], i.e., without the value passing or abstraction allowed in FLR. The "pure," propositional fragment FLR 0 turns out to coincide with the iteration theories of [1]. Our main focus here concerns the sharp contrast between the simple class of valid identities and the very complex consequence relation over several natural classes of (...) models. (shrink)
Mathematical models are an important tool in the development ofsoftware technology, including programming languages and algorithms.During the last few years, a new class of such models has beendeveloped based on the notion of a mathematical game that isespecially well-suited to address the interactions between thecomponents of a system. This paper gives an introduction to thesegame-semantical models of programming languages, concentrating onmotivating the basic intuitions and putting them into context.
Answer set programming (ASP) is a form of declarative programming oriented towards difficult search problems. As an outgrowth of research on the use of nonmonotonic reasoning in knowledge representation, it is particularly useful in knowledge-intensive applications. ASP programs consist of rules that look like Prolog rules, but the computational mechanisms used in ASP are different: they are based on the ideas that have led to the creation of fast satisfiability solvers for propositional logic.
We prove results about nonstandard formulas in models of Peano arithmetic which complement those of Kotlarski, Krajewski, and Lachlan in [KKL] and [L]. This enables us to characterize both recursive saturation and resplendency in terms of statements about nonstandard sentences. Specifically, a model M of PA is recursively saturated iff M is nonstandard and M-logic is consistent.M is resplendent iff M is nonstandard, M-logic is consistent, and every sentence φ which is consistent in M-logic is contained in a full (...) satisfaction class for M. Thus, for models of PA, recursive saturation can be expressed by a (standard) Σ 1 1 -sentence and resplendency by a ▵ 1 2 -sentence. (shrink)
How to write a program in Haskell, and how to use the Haskell testing tools . . . QuickCheck is a tool written in the functional programming language Haskell that allows testing of specifications by means of randomly generated tests. QuickCheck is part of the standard Haskell library. Re-implementations of QuickCheck exist for many languages, including Ruby and Scheme. SmallCheck is a similar tool, different from QuickCheck in that it tests properties for all finitely many values of a datatype (...) up to some given depth, with progressive increase of depth. Haskell is a research language: many of the testing tools that were first developed for Haskell later find their way to other languages. These slides discuss QuickCheck (two versions), SmallCheck, and some work in progress. We end with some examples of Alloy specifications. (shrink)
Answer Set Programming is a new paradigm based on logic programming. The main component of answer set programming is a system that finds the answer sets of logic programs. During the computation of an answer set, systems are faced with choice points where they have to select a literal and assign it a truth value. Generally, systems utilize some heuristics to choose new literals at the choice points. The heuristic used is one of the key factors for (...) the performance of the system. A new heuristic for answer set programming has been developed. This heuristic is inspired by hierarchical planning. The notion of criticality, which was introduced for generating abstraction hierarchies in hierarchical planning, is used in this heuristic. The resulting system (CSMOD- ELS) uses this new heuristic in a static way. CSMODELS is based on the system SMODELS. The experimental results show that this new heuristic is promising for answer set programming. A comparison of search times with SMODELS demonstrate CSMODELS’ usefulness. (shrink)
The general conditions of epistemic defeat are naturally represented through the interplay of two distinct kinds of entailment, deductive and defeasible. Many of the current approaches to modeling defeasible reasoning seek to define defeasible entailment via model-theoretic notions like truth and satisfiability, which, I argue, fails to capture this fundamental distinction between truthpreserving and justification-preserving entailments. I present an alternative account of defeasible entailment and show how logic programming offers a paradigm in which the distinction can be captured, (...) allowing for the modeling of a larger range of types of defeat. This is possible through a natural extension of the declarative and procedural semantics of Horn clauses. (shrink)
There has been considerable discussion in the past about the assumptions and basis of different ethical rules. For instance, it is commonplace to say that ethical rules are defaults rules, which means that they tolerate exceptions. Some authors argue that morality can only be grounded in particular cases while others defend the existence of general principles related to ethical rules. Our purpose here is not to justify either position, but to try to model general ethical rules with artificial intelligence formalisms (...) and to compute logical consequences of different ethical theories. More precisely, this is an attempt to show that progress in non-monotonic logics, which simulates default reasoning, could provide a way to formalize different ethical conceptions. From a technical point of view, the model developed in this paper makes use of the Answer Set Programming (ASP) formalism. It is applied comparatively to different ethical systems with respect to their attitude towards lying. The advantages of such formalization are two-fold: firstly, to clarify ideas and assumptions, and, secondly, to use solvers to derive consequences of different ethical conceptions automatically, which can help in a rigorous comparison of ethical theories. (shrink)
A critical concern for firms pursuing international expansion strategies involves identifying countries that offer a good fit with the firm's overall ethical orientation. Unfortunately, little has been written to aid firms in identifying countries that offer this type of fit. This paper presents a model that combines the concepts of strategic management, cross-cultural management, business ethics, and the management science technique of goal programming. The purpose of the model is to aid managers in identifying countries for international expansion that (...) offer the best fit with the firm's ethical orientation. The paper also extends the existing literature on cross-cultural management and business ethics by applying a computer optimization model to evaluate potential countries for international expansion in a way that has not been done before. (shrink)
Loveland and Meyer have studied necessary and sufficient conditions for an infinite binary string x to be recursive in terms of the programsize complexity relative to n of its n-bit prefixes xn. Meyer has shown that x is recursive iff ∃c, ∀n, K(xn/n) ≤ c, and Loveland has shown that this is false if one merely stipulates that K(xn/n) ≤ c for infinitely..
We show that to every recursive total continuous functional Φ there is a PCF-definable representative Ψ of Φ in the hierarchy of partial continuous functionals, where PCF is Plotkin's programming language for computable functionals. PCF-definable is equivalent to Kleene's S1-S9-computable over the partial continuous functionals.
The complexity of aII 4 set of natural numbers is encoded into a linear order to show that the finite condensation of a recursive linear order can beII 2–II 1. A priority argument establishes the same result, and is extended to a complete classification of finite condensations iterated finitely many times.
The properties of antisymmetry and linearity are easily seen to be sufficient for a recursively enumerable binary relation to be recursively isomorphic to a recursive relation. Removing either condition allows for the existence of a structure where no recursive isomorph exists, and natural examples of such structures are surveyed.
New success criteria of inductive inference in computational learning theory are introduced which model learning total (not necessarily recursive) functions with (possibly everywhere) imprecise theories from (possibly always) inaccurate data. It is proved that for any level of error allowable by the new success criteria, there exists a class of recursive functions such that not all f are identifiable via the criterion at that level of error. Also, necessary and sufficient conditions on the error level are given for (...) when more classes of functions may be identified. (shrink)
The first example of a simultaneous inductive-recursive definition in intuitionistic type theory is Martin-Löf's universe á la Tarski. A set U 0 of codes for small sets is generated inductively at the same time as a function T 0 , which maps a code to the corresponding small set, is defined by recursion on the way the elements of U 0 are generated. In this paper we argue that there is an underlying general notion of simultaneous inductive-recursive definition (...) which is implicit in Martin-Löf's intuitionistic type theory. We extend previously given schematic formulations of inductive definitions in type theory to encompass a general notion of simultaneous induction-recursion. This enables us to give a unified treatment of several interesting constructions including various universe constructions by Palmgren, Griffor, Rathjen, and Setzer and a constructive version of Aczel's Frege structures. Consistency of a restricted version of the extension is shown by constructing a realisability model in the style of Allen. (shrink)
Bilattices, introduced by M. Ginsberg, constitute an elegant family of multiple-valued logics. Those meeting certain natural conditions have provided the basis for the semantics of a family of logic programming languages. Now we consider further restrictions on bilattices, to narrow things down to logic programming languages that can, at least in principle, be implemented. Appropriate bilattice background information is presented, so the paper is relatively self-contained.
We present a logic programming language, which we call Proflog, with an operational semantics based on tableaus, and a denotational semantics based on supervaluations. We show the two agree. Negation is well-behaved, and semantic non-computability issues do not arise. This is accomplished essentially by dropping a domain closure requirement. The cost is that intuitions developed through the use of classical logic may need modification, though the system is still classical at a level once removed. Implementation problems are discussed very (...) briefly — the thrust of the paper is primarily theoretical. (shrink)
. We discuss resource-bounded measures on the class of recursive structures and prove that with respect to such measures a random recursive structure is almost surely isomorphic to the unique countable model of the extension axioms.
In several recent experiments we have found that the eyes are often captured by the appearance of a sudden onset in a display, even though subjects intend to move their eyes elsewhere. Very brief fixations are made on the abrupt onset before the eyes complete their intended movement to the previously defined target. These results indicate concurrent programming of a voluntary saccade to the defined saccade target and an involuntary saccade to the sudden onset. This is inconsistent with the (...) idea that a single salience map determines the location of a saccade in a winner-take-all fashion. Other results indicate that subjects attend to more than one location in a display during saccade preparation, contrary to the claim that covert attentional scanning plays no role in saccade generation. (shrink)
In a recent paper, Ferraris, Lee and Lifschitz conjectured that the concept of a stable model of a first-order formula can be used to treat some answer set programming expressions as abbreviations. We follow up on that suggestion and introduce an answer set programming language that defines the mean- ing of counting and choice by reducing these constructs to first-order formulas. For the new language, the concept of a safe program is defined, and its semantic role is investigated. (...) We compare the new language with the concept of a disjunc- tive program with aggregates introduced by Faber, Leone and Pfeifer, and discuss the possibility of implementing a frag- ment of the language by translating it into the input language of the answer set solver DLV. The language is also compared with cardinality constraint programs defined by Syrjänen. (shrink)
affects the collection of answer sets. In particular, it is useful to be able to describe the effects of adding definitions to a program with nested expressions, in view of the relation of this class of programs to the input language of the answer set programming system sMonELs. In this..
The concept of a temporal phylogenetic network is a mathematical model of evolution of a family of natural languages. It takes into account the fact that languages can trade their characteristics with each other when linguistic communities are in contact, and also that a contact is only possible when the languages are spoken at the same time. We show how computational methods of answer set programming and constraint logic programming can be used to generate plausible conjectures about contacts (...) between prehistoric linguistic communities, and illustrate our approach by applying it to the evolutionary history of Indo-European languages. (shrink)
Telephone survey of 293 TV viewers in Minneapolis-St. Paul investigated how viewers evaluate ethical issues and problematic content in TV news and entertainment programs, and attitudes toward methods of controlling TV content. In rating eight hypothetical news and entertainment scenarios, viewers appeared more willing to accept ethical breaches in entertainment than in news programs. In evaluating the severity of general problems in TV programming, most viewers considered violence, adult themes, and a lack of family values to be big problems. (...) Different methods of controlling potentially problematic content were evaluated, with viewers overwhelmingly endorsing a system of ratings or warnings, as well as restricting content to certain times or channels. Governmental regulation as a form of controlling TV content was strongly rejected. This article demonstrates the usefulness and appropriateness of empirical research in involving the audience in an active role in the study of media ethics. (shrink)
The progress in artificial intelligence enables us to conceive adaptive systems whose characteristics are nearer and nearer to those of living beings. These characteristics though depend on ingenious choices by the designer of these systems: Initial conditions, parameters, optimisation functions, gradient and measure of fitness within the environment. Nevertheless, in living systems which are non-finalist, there are no programmers or designers to conceive of such ingenious choices. Our paper “Self-Programming Machines (I)” presents a non-finalist model since initial states and (...) functions are randomly chosen at the beginning and once and for all. In spite of the fact that they are non-finalist, these machines always stabilise at fixed points when they are connected to an external process. (shrink)
Extended algorithmic logic (EAL) as introduced in [18] is a modified version of extended +-valued algorithmic logic. Only two-valued predicates and two-valued propositional variables occur in EAL. The role of the +-valued logic is restricted to construct control systems (stacks) of pushdown algorithms whereas their actions are described by means of the two-valued logic. Thus EAL formalizes a programming theory with recursive procedures but without the instruction CASE.The aim of this paper is to discuss EAL and prove the (...) completeness theorem. A complete formalization of EAL was announced in [20] but no proof of the completeness theorem was given. (shrink)
Let KP- be the theory resulting from Kripke-Platek set theory by restricting Foundation to Set Foundation. Let G: V → V (V:= universe of sets) be a ▵0-definable set function, i.e. there is a ▵0-formula φ(x, y) such that φ(x, G(x)) is true for all sets x, and $V \models \forall x \exists!y\varphi (x, y)$ . In this paper we shall verify (by elementary proof-theoretic methods) that the collection of set functions primitive recursive in G coincides with the collection (...) of those functions which are Σ1-definable in KP- + Σ1-Foundation + ∀ x ∃!yφ (x, y). Moreover, we show that this is still true if one adds Π1-Foundation or a weak version of ▵0-Dependent Choices to the latter theory. (shrink)
The Uniformly Reflexive Structure was introduced by E. G. Wagner who showed that the theory of such structures generalized much of recursive function theory. In this paper Uniformly Reflexive Structures are constructed as factor algebras of Free nonassociative algebras. Wagner's question about the existence of a model with no computable splinter ("successor set") is answered in the affirmative by the construction of a model whose only computable sets are the finite sets and their complements. Finally, for each countable Boolean (...) algebra R of subsets of a countable set which contains the finite subsets, a model is constructed with R as its family of computable sets. (shrink)
The class of all recursive functions fails to possess a natural hierarchical structure, generated predicatively from "within". On the other hand, many (proof-theoretically significant) sub-recursive classes do. This paper attempts to measure the limit of predicative generation in this context, by classifying and characterizing those (predictably terminating) recursive functions which can be successively defined according to an autonomy condition of the form: allow recursions only over well-orderings which have already been "coded" at previous levels. The question is: (...) how can a recursion code a well-ordering? The answer lies in Girard's theory of dilators, but is reworked here in a quite different and simplified framework specific to our purpose. The "accessible" recursive functions thus generated turn out to be those provably recursive in $(\prod_{1}^{1}-CA)_{0}$. (shrink)
Two linear orderings are equimorphic if each can be embedded into the other. We prove that every hyperarithmetic linear ordering is equimorphic to a recursive one. On the way to our main result we prove that a linear ordering has Hausdorff rank less than $\omega _{1}^{\mathit{CK}}$ if and only if it is equimorphic to a recursive one. As a corollary of our proof we prove that, given a recursive ordinal α, the partial ordering of equimorphism types of (...) linear orderings of Hausdorff rank at most α ordered by embeddablity is recursively presentable. (shrink)
We re-express a previous general result in a way which seems easier to remember, using the terminology of infinite games. We show how this can be applied to construct recursive linear orderings, showing, for example, that if there is a ▵ 0 2β + 1 linear ordering of type τ, then there is a recursive ordering of type ω β · τ.
Models of normal open induction are those normal discretely ordered rings whose nonnegative part satisfy Peano's axioms for open formulas in the language of ordered semirings. (Where normal means integrally closed in its fraction field.) In 1964 Shepherdson gave a recursive nonstandard model of open induction. His model is not normal and does not have any infinite prime elements. In this paper we present a recursive nonstandard model of normal open induction with an unbounded set of infinite prime (...) elements. (shrink)
We recall some of the early occurrences of the notions of interactivity and symmetry in the operational and denotational semantics of programming languages. We suggest some connections with ludics.
For the sake of simplicity, we adopt the same logical frame as Tarski's in his Wahrheitsbegriff (Wb). There, Tarski is mainly interested in the possibility of explicitely defining truth for an object-language, he does not pay much attention to recursive definitions of truth. We say why. However, recursive definitions have advantages of their own. In particular, we prove the positive theorem: if L is of finite order ≥ 4, then a recursive definition is possible for L in (...) a metalanguage of the same order as L. We indicate how this result could be used for a solution of a generalized version of Frege's paradox. (shrink)
Genetic Programming (GP) is a technique which permits automatic search for complex solutions using a computer. It goes beyond previous techniques in that it discovers the structure of those solutions. Previously, if one were trying to find an equation to fit a set of data, one would have had to provide the form of the equation (for example a fourth degree polynomial) and the computer could then find the appropriate parameters. By contrast, GP can experiment with a whole range (...) of different functional forms , building equations from a menu of functions, symbols and arithmetic operations. Thus GP can be seen as an essentially creative technique. It is good at finding novel solutions where not much is known about the form of the solution.. (shrink)
EI objetivo de este artículo es presentar los principios de la programación lógica borrosa y de sus principales variantes, ilustrándolas a través de un conjunto de aproximaciones que, a nuestro entender, son representativas de los avances en esta área. También incluimos la descripción de otros sistemas de programación lógica que se sustentan en lógicas de la incertidumbre diferentes de la lógica borrosa. En esta presentación presuponemos que la mayoría de los lectores no son expertos en programación lógica; para seguirla sólo (...) se requiere un conocimiento básico de la lógica de predicados.The purpose of this paper is to present the principles of the fuzzy logic programming, exemplifying them by a couple of proposals that we think are representatives of the advances in this field. We include also the description of another systems of logic programming with uncertain information that are based on other logics of uncertainty which are different from fuzzy logic. This article only presuppose anelementary knowledge of the classical first-order logic. (shrink)
This commentary analyses the quantitative parameters of Reichle et al.'s model, using estimates when explicit information is not provided. The analysis highlights certain features that appear to be necessary to make the model work and ends by noting a possible problem concerning the variability associated with oculomotor programming.
Harmonic Grammar (HG) is a model of linguistic constraint interaction in which well-formedness is calculated as the sum of weighted constraint violations. We show how linear programming algorithms can be used to determine whether there is a weighting for a set of constraints that fits a set of linguistic data. The associated software package OT-Help provides a practical tool for studying large and complex linguistic systems in the HG framework and comparing the results with those of OT. We describe (...) the translation from Harmonic Grammars to systems solvable by linear programming, and we illustrate the usefulness of OT-Help with a set of studies of the predictions HG makes for phonological typology. (shrink)
E-Z Reader achieves an impressive fit of empirical eye movement data by simulating core processes of reading in a computational approach that includes serial word processing, shifts of attention, and temporal overlap in the programming of saccades. However, when common assumptions for the time requirements of these processes are taken into account, severe constraints on the time line within which these elements can be combined become obvious. We argue that it appears difficult to accommodate these processes within a largely (...) sequential modeling framework such as E-Z Reader. (shrink)
There is a comeager set C contained in the set of 1-generic reals and a first order structure M such that for any real number X, there is an element of C which is recursive in X if and only if there is a presentation of M which is recursive in X.
EI objetivo de este artículo es presentar los principios de la programación lógica borrosa y de sus principales variantes, ilustrándolas a través de un conjunto de aproximaciones que, a nuestro entender, son representativas de los avances en esta área. También incluimos la descripción de otros sistemas de programación lógica que se sustentan en lógicas de la incertidumbre diferentes de la lógica borrosa. En esta presentación presuponemos que la mayoría de los lectores no son expertos en programación lógica; para seguirla sólo (...) se requiere un conocimiento básico de la lógica de predicados.The purpose of this paper is to present the principles of the fuzzy logic programming, exemplifying them by a couple of proposals that we think are representatives of the advances in this field. We include also the description of another systems of logic programming with uncertain information that are based on other logics of uncertainty which are different from fuzzy logic. This article only presuppose anelementary knowledge of the classical first-order logic. (shrink)
The construction of complex simulation models and the application of new computer hardware to ecological problems has resulted in the need for many ecologists to rely on computer programmers to develop their modelling software. However, this can lead to a lack of flexibility and understanding in model implementation and in resource problems for researchers. This paper presents a new programming language, Viola, based on a simple organisational concept which can be used by most researchers to develop complex simulations much (...) more easily than could be achieved with standard programming languages such as C++. The language is object oriented and implemented through a visual interface. It is specifically designed to cope with complicated individual based behavioural simulations and comes with embedded concurrency handling abilities. (shrink)
The progress in computer programming leads to the shift in traditional correlation between intuitive and formal components of mathematical knowledge. From epistemological point of view the role of intuition decreases in compare with formal representation of mathematical structures. The relevant explanation is to be found in D. Hilbert’s formalism and corresponding Kantian’s motives in it. The notion of sign belongs to both areas under consideration: on the one hand it is object of intuition in Kantian de re sense, on (...) the other hand, it is part of formal structure. Intuitive mathematical knowledge is expressed by primitive recursive reasoning. The W. Tait’s thesis, namely, that finitism as methodology of mathematics is equivalent to primitive recursive reasoning is discussed in connection with some explications of Kantian notion of intuition. The requirements of finitism are compared with normative role of logic. (shrink)
Let the chain antichain principle (CAC) be the statement that each partial order on $\mathbb{N}$ possesses an infinite chain or an infinite antichain. Chong, Slaman, and Yang recently proved using forcing over nonstandard models of arithmetic that CAC is $\Pi^1_1$-conservative over $\text{RCA}_0+\Pi^0_1\text{-CP}$ and so in particular that CAC does not imply $\Sigma^0_2$-induction. We provide here a different purely syntactical and constructive proof of the statement that CAC (even together with WKL) does not imply $\Sigma^0_2$-induction. In detail we show using a (...) refinement of Howard's ordinal analysis of bar recursion that $\text{WKL}_0^\omega+\text{CAC}$ is $\Pi^0_2$-conservative over PRA and that one can extract primitive recursive realizers for such statements. Moreover, our proof is finitary in the sense of Hilbert's program. CAC implies that every sequence of $\mathbb{R}$ has a monotone subsequence. This Bolzano-Weierstraß}-like principle is commonly used in proofs. Our result makes it possible to extract primitive recursive terms from such proofs. We also discuss the Erdős-Moser principle, which—taken together with CAC—is equivalent to $\text{RT}^2_2$. (shrink)
Theorists have oversold the usefulness of predicate logic and generative grammar to the study of language origins. They have searched for models that correspond to semantic properties, such as truth, when what is needed is an empirically testable model of evolution. Such a model is required if we are to explain the origins of linguistic properties by appealing to general properties of linguistic engendering, rather than to the advent of genotypes with the propensity to produce certain brain mechanisms. While the (...) latter sort of explanation has a place, no theory can be considered an `evolutionary' theory without the former. We introduce a general notion of engendering, whose primary virtue is its freedom from assumptions regarding the nature of colloquial change. We use it to frame a conjecture about the evolution of centre embedded clauses; one which makes the fewest possible assumptions about the neural requirements upon individual brains. Keywords: biology of language; epigenesis; engendering; evolution; mutation; population; recursion. (shrink)
Alonzo Church's mathematical work on computability and undecidability is well-known indeed, and we seem to have an excellent understanding of the context in which it arose. The approach Church took to the underlying conceptual issues, by contrast, is less well understood. Why, for example, was "Church's Thesis" put forward publicly only in April 1935, when it had been formulated already in February/March 1934? Why did Church choose to formulate it then in terms of Gödel's general recursiveness, not his own λ (...) -definability as he had done in 1934? A number of letters were exchanged between Church and Paul Bernays during the period from December 1934 to August 1937; they throw light on critical developments in Princeton during that period and reveal novel aspects of Church's distinctive contribution to the analysis of the informal notion of effective calculability. In particular, they allow me to give informed, though still tentative answers to the questions I raised; the character of my answers is reflected by an alternative title for this paper, Why Church needed Gödel's recursiveness for his Thesis. In Section 5, I contrast Church's analysis with that of Alan Turing and explore, in the very last section, an analogy with Dedekind's investigation of continuity. (shrink)
The modal logician's notion of possible world and the computer scientist's notion of state of a machine provide a point of commonality which can form the foundation of a logic of action. Extending ordinary modal logic with the calculus of binary relations leads to a very natural logic for describing the behavior of computer programs.
Over recent years, various semantics have been proposed for dealing with updates in the setting of logic programs. The availability of different semantics naturally raises the question of which are most adequate to model updates. A systematic approach to face this question is to identify general principles against which such semantics could be evaluated. In this paper we motivate and introduce a new such principle the refined extension principle. Such principle is complied with by the stable model semantics for (single) (...) logic programs. It turns out that none of the existing semantics for logic program updates, even though generalisations of the stable model semantics, comply with this principle. For this reason, we define a refinement of the dynamic stable model semantics for Dynamic Logic Programs that complies with the principle. (shrink)
The last Episode wasn’t about logic or formal theories at all: it was about common-or-garden arithmetic and the informal notion of computability. We noted that addition can be defined in terms of repeated applications of the successor function. Multiplication can be defined in terms of repeated applications of addition. The exponential and factorial functions can be defined, in different ways, in terms of repeated applications of multiplication. There’s already a pattern emerging here! The main task in the last Episode was (...) to get clear about this pattern. So first we said more about the idea of defining one function in terms of repeated applications of another function. Tidied up, that becomes the idea of defining a function by primitive recursion (Defn. 27). (shrink)
Art history cannot be sealed off in cultural isolation: given our innate forms of life, language, and human nature, cultural diversity is only skin deep. The identification of art by historical recursion could not be restricted to the fixed art history of one hermetically sealed cultural tradition because there is no such thing. Attempts to define artworks recursively thus lead to the absurdity that everything in the present might be art because of unknown art antecedents in earlier human cultures that (...) we in a contemporary culture would not call art. Making the lack of a theory the theoretical point of a practice leads to chaos. (shrink)
Let g E(m, n)=o mean that n is the Gödel-number of the shortest derivation from E of an equation of the form (m)=k. Hao Wang suggests that the condition for general recursiveness mn(g E(m, n)=o) can be proved constructively if one can find a speedfunction s s, with s(m) bounding the number of steps for getting a value of (m), such that mn s(m) s.t. g E(m, n)=o. This idea, he thinks, yields a constructivist notion of an effectively computable function, (...) one that doesn't get us into a vicious circle since we intuitively know, to begin with, that certain proofs are constructive and certain functions effectively computable. This paper gives a broad possibility proof for the existence of such classes of effectively computable functions, with Wang's idea of effective computability generalized along a number of dimensions. (shrink)
This paper studies the extent to which probability functions are recursively definable. It proves, in particular, that the (absolute) probability of a statement A is recursively definable from a certain point on, to wit: from the (absolute) probabilities of certain atomic components and conjunctions of atomic components of A on, but to no further extent. And it proves that, generally, the probability of a statement A relative to a statement B is recursively definable from a certain point on, to wit: (...) from the probabilities relative to that very B of certain atomic components and conjunctions of atomic components of A, but again to no further extent. These and other results are extended to the less studied case where A and B are compounded from atomic statements by means of `` ∀ '' as well as `` ∼ '' and "&". The absolute probability functions considered are those of Kolmogorov and Carnap, and the relative ones are those of Kolmogorov, Carnap, Renyi, and Popper. (shrink)
We study topological constructions in the recursion theoretic framework of the lattice of recursively enumerable open subsets of a topological space X. Various constructions produce complemented recursively enumerable open sets with additional recursion theoretic properties, as well as noncomplemented open sets. In contrast to techniques in classical topology, we construct a disjoint recursively enumerable collection of basic open sets which cannot be extended to a recursively enumerable disjoint collection of basic open sets whose union is dense in X.
The paper presents four open problems concerning recursively saturated models of Peano Arithmetic. One problems concerns a possible converse to Tarski's undefinability of truth theorem. The other concern elementary cuts in countable recursively saturated models, extending automorphisms of countable recursively saturated models, and Jonsson models of PA. Some partial answers are given.
It is an open problem within the study of recursively enumerable classes of recursively enumerable sets to characterize those recursively enumerable classes which can be recursively enumerated without repetitions. This paper is concerned with a weaker property of r.e. classes, namely that of being recursively enumerable with at most finite repetitions. This property is shown to behave more naturally: First we prove an extension theorem for classes satisfying this property. Then the analogous theorem for the property of recursively enumerable classes (...) of being recursively enumerable with a bounded number of repetitions is shown not to hold. The index set of the property of recursively enumerable classes "having an enumeration with finite repetitions" is shown to be Σ 0 6 -complete. (shrink)
