To have free will is to have what it takes to act freely. When an agent acts freely—when she exercises her free will—what she does is up to her. A plurality of alternatives is open to her, and she determines which she pursues. When she does, she is an ultimate source or origin of her action. So runs a familiar conception of free will.

In this paper, we provide a semantics for a range of positive substructural logics, including both logics with and logics without modal connectives. The semantics is novel insofar as it is meant to explicitly capture the computational flavor of these logics, and to do so in a way that builds in both nondeterministic and nonconcurrent computational processes.

Nondeterministic programs occurring in recently developed programming languages define nondeterminate partial functions. Formulas (Boolean expressions) of such nondeterministic languages are interpreted by a nonempty subset of {T (true), F (false), U (undefined)}. As a semantic basis for the propositional part of a corresponding nondeterministic three-valued logic we study the notion of a truth-function over {T, F, U} which is computable by a nondeterministic evaluation procedure. The main result is that these truth-functions are precisely the functions satisfying four basic properties, called (...) -isotonic, –-isotonic, hereditarily guarded, and hereditarily guard-using, and that a function satisfies these properties iff it is explicitly definable (in a certain normal form) from if..then..else..fi, binary choice, and constants. (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)

I argue that there cannot be a sense attached to “could have done otherwise” that is both compatible with the truth of determinism and relevant to the question of free will. Then I develop an incompatibilist response to the common objection that the incompatibilist requires of free actions that they have no causes and therefore cannot be anything for which an agent can be responsible. In the process, I bring out a similarity between compatibilism and incompatibilism in respect of where (...) their problem lies. (shrink)

I argue that there cannot be a sense attached to “could have done otherwise” that is both compatible with the truth of determinism and relevant to the question of free will. Then I develop an incompatibilist response to the common objection that the incompatibilist requires of free actions that they have no causes and therefore cannot be anything for which an agent can be responsible. In the process, I bring out a similarity between compatibilism and incompatibilism in respect of where (...) their problem lies. (shrink)

This paper proposes new semantics for propositional dynamic logic (PDL), replacing the standard relational semantics. Under these new semantics, program execution is represented as fundamentally deterministic (i.e., functional), while nondeterminism emerges as an epistemic relationship between the agent and the system: intuitively, the nondeterministic outcomes of a given process are precisely those that cannot be ruled out in advance. We formalize these notions using topology and the framework of dynamic topological logic (DTL) (Kremer and Mints in Ann Pure Appl (...) Logic 131:133–158, 2005). We show that DTL can be used to interpret the language of PDL in a manner that captures the intuition above, and moreover that continuous functions in this setting correspond exactly to deterministic processes. We also prove that certain axiomatizations of PDL remain sound and complete with respect to the corresponding classes of dynamic topological models. Finally, we extend the framework to incorporate knowledge using the machinery of subset space logic (Dabrowski et al. in Ann Pure Appl Logic 78:73–110, 1996), and show that the topological interpretation of public announcements as given in Bjorndahl (in: van Ditmarsch and Sandu (eds) Jaakko Hintikka on knowledge and game theoretical semantics, outstanding contributions to Logic, vol 12, Springer, 2018) coincides exactly with a natural interpretation of test programs. (shrink)

This paper describes an approach for reasoning in a dynamic domain with nondeterministic actions in which an agent’s beliefs correspond to the simplest, or most plausible, course of events consistent with the agent’s observations and beliefs. The account is based on an epistemic extension of the situation calculus, a first-order theory of reasoning about action that accommodates sensing actions. In particular, the account is based on a qualitative theory of nondeterminism. Our position is that for commonsense reasoning, the world (...) is most usefully regarded as deterministic, and that nondeterminism is an epistemic phenomenon, arising from an agent’s limited awareness and perception. The account offers several advantages: an agent has a set of categorical beliefs, yet can deal with equally-likely outcomes or with outcomes of differing plausibility. The agent maintains as its set of contingent beliefs the most plausible, or simplest, picture of the world, consistent with its beliefs and actions it believes it executed; yet it may modify these in light of later information. (shrink)

In this essay, I examine the notion of a nondeterministic algorithm from both a conceptual and historical point of view. I argue that the intuitions underwriting nondeterminism in the context of contemporary theoretical computer science cannot be reconciled with the intuitions that originally motivated nondeterminism. I identify four different intuitions about nondeterminism: nondeterminism as evidence for the Church Turing thesis; nondeterminism as a natural reflection of the mathematician's behavior; nondeterminism as a formal, mathematical generalization; (...) and nondeterminism as a physical process. I shall argue that there are irreconcilable tensions among these intuitions and, moreover, that these tensions have not been acknowledged in the conceptual development of theoretical computer science. In fact, a careful review of the received history reveals a number of gaps and discontinuities. For instance, I examine the seminal writings of Turing and argue that the formal introduction of the nondeterminism is to be found there and not, as is often supposed, in the research of the late 1950s and early 1960s. I also examine the period after 1960 and argue that even the more recent developments concerning nondeterminism are hard to reconstruct. ;Although I firmly believe that a rigorous philosophical account of nondeterminism is needed, I am not sure that such an account will bring us any closer to a solution to any of the notoriously difficult theoretical problems that turn on the notion of a nondeterministic algorithm. I do believe, however, that a clear conceptual account of nondeterminism will shed light on many long-standing philosophical problems. I conclude by pointing to a number of philosophical questions that resonate with issues raised by the foregoing investigation of nondeterministic algorithms. (shrink)

In the paper we define a class of languages for representation o knowledge in those application areas when a complete information about a domain is not available. In the languages we introduce modal operators determined by accessibility relations depending on parameters.

There are two well-developed formalizations of discrete time dynamic systems that evidently share many concerns but suffer from a lack of mutual awareness. One formalization is classical systems and automata theory. The other is the logic of actions in which the situation and event calculi are the strongest representatives. Researchers in artificial intelligence are likely to be familiar with the latter but not the former. This is unfortunate, for systems and automata theory have much to offer by way of insight (...) into problems raised in the logics of action. This paper is an outline of how the input-output view of systems and its associated solution of state realization may be applied to the formalization of dynamics that uses a situation calculus approach. In particular, because the latter usually admits incompletely specified dynamics, which induces a non-deterministic input-output system behavior, we first show that classical state realization can still be achieved if the behavior is causal. This is a novel systems-theoretic result. Then we proceed to indicate how situation calculi dynamic specifications can be understood in systems-theoretic terms, and how automata can be viewed as models of such specifications. As techniques for reasoning about automata are abundant, this will provide yet more tools for reasoning about actions. (shrink)

In this paper we systematically derive a predicate transformer semantics from a direct semantics for a simple probabilistic-nondeterministic programming language . This goal is achieved by exhibiting the direct semantics as isomorphic to a continuation semantics from which the predicate transformer semantics can be read off immediately. This isomorphism allows one to identify nonempty convex compact saturated sets of valuations on the set S of states with certain “good” functionals from to in a way similar to the one how H. (...) Minkowski in 1903 related nonempty convex compact subsets of to what is nowadays called Minkowski functionals. (shrink)

We present a model of computation for string functions over single-sorted, total algebraic structures and study some basic features of a general theory of computability within this framework. Our concept generalizes the Blum-Shub-Smale setting of computability over the reals and other rings. By dealing with strings of arbitrary length instead of tuples of fixed length, some suppositions of deeper results within former approaches to generalized recursion theory become superfluous. Moreover, this gives the basis for introducing computational complexity in a BSS-like (...) manner. Relationships both to classical computability and to Friedman's concept of eds computability are established. Two kinds of nondeterminism as well as several variants of recognizability are investigated with respect to interdependencies on each other and on properties of the underlying structures. For structures of finite signatures, there are universal programs with the usual characteristics. For the general case of not necessarily finite signature, this subject will be studied in a separate, forthcoming paper. (shrink)

This paper is an investigation in the use of truthmaker theory for exploring the relation of logic to world, and as a tool for metaphysics. A variant of truthmaker theory, which we call the simple theory, is defined and defended against objections. It is characterized formally, and its central features are derived. As part of this project, we give a formal metaphysics based on nondeterministic necessitation relations among possible entities. In what is called the fundamental theorem of truthmaking, it is (...) shown that, as long as a logic is sound and complete, its inferential structure will be isomorphic to the necessitation structure of our metaphysics. We thus arrive at a purely structural logic–world relationship which can be used for metaphysical investigations. Other products of our investigation are a sound and complete semantics for first-order logic with identity and a solution to a result of Restall which has threatened to make truthmaker theory trivial. (shrink)

Trivalence is quite natural for deontic action logic, where actions are treated as good, neutral or bad.We present the ideas of trivalent deontic logic after J. Kalinowski and its realisation in a 3-valued logic of M. Fisher and two systems designed by the authors of the paper: a 4-valued logic inspired by N. Belnap’s logic of truth and information and a 3-valued logic based on nondeterministic matrices. Moreover, we combine Kalinowski’s idea of trivalence with deontic action logic based on boolean (...) algebra. (shrink)

Nondeterministic exponential time complexity bounds are established for recognizing true propositional formulas with partially ordered quantifiers on propositional variables.

Nondeterministic models of collective choice posit convergence among the outcomes of simple-majority decisions. The object of this research is to estimate the extent of convergence of majority choice under different procedural conditions. The paper reports results from a computer simulation of simple-majority decision making by committees. Simulation experiments generate distributions of majority-adopted proposals in two-dimensional space. These represent nondeterministic outcomes of majority choice by committees. The proposal distributions provide data for a quantitative evaluation of committee-choice procedures in respect to outcome (...) convergence. Experiments were run under general conditions, and under conditions that restrict committee choice to several game-theoretic solution sets. The findings are that, compared to distributions of voter ideal points, majority-adopted proposals confined to the solution sets demonstrate different degrees of convergence. Second, endogenous agenda formation is a more important obstacle to convergence than the inherent instability of simple-majority rule. Third, if members maximize preferences in respect to agenda formation, a committee choice that approximates the central tendency of the distribution of voter preferences is unlikely. The conclusion is that the most effective way to increase the convergence of majority choice is to restrict the role of individual preferences in agenda formation: identification of proposals to be voted up or down by a committee. (shrink)

For a prime k, the embeddability of finite lattices are discussed for various kind of the MODkP degrees of recursive sets. In particular, all finite lattices are embeddable into the MODkP Turing degrees, whereas the non distributive lattice M3 is embeddable into the MOD2P many-one degrees but N5 is not.

This comprehensive study offers a balanced assessment of libertarian accounts of free will. Bringing to bear recent work on action, causation, and causal explanation, Clarke defends a type of event-causal view from popular objections concerning rationality and diminished control. He subtly explores the extent to which event-causal accounts can secure the things for the sake of which we value free will, judging their success here to be limited. Clarke then sets out a highly original agent-causal account, one that integrates agent (...) causation and nondeterministic event causation. He defends this view from a number of objections but argues that we should find the substance causation required by any agent-causal account to be impossible. Clarke concludes that if a broad thesis of incompatibilism is correct--one on which both free will and moral responsibility are incompatible with determinism--then no libertarian account is entirely adequate. (shrink)

In this note, an error in the axiomatization of Ivlev’s modal system Sa+ which we inadvertedly reproduced in our paper “Finite non-deterministic semantics for some modal systems”, is fixed. Additionally, some axioms proposed in were slightly modified. All the technical results in which depend on the previous axiomatization were also fixed. Finally, the discussion about decidability of the level valuation semantics initiated in is taken up. The error in Ivlev’s axiomatization was originally pointed out by H. Omori and D. Skurt (...) in the paper “More modal semantics without possible worlds”, where an alternative solution was proposed. (shrink)

In this paper, we present an intelligent tutoring system developed to help students in learning Computer Theory. The Intelligent tutoring system was built using ITSB authoring tool. The system helps students to learn finite automata, pushdown automata, Turing machines and examines the relationship between these automata and formal languages, deterministic and nondeterministic machines, regular expressions, context free grammars, undecidability, and complexity. During the process the intelligent tutoring system gives assistance and feedback of many types in an intelligent manner according to (...) the behavior of the student. An evaluation of the intelligent tutoring system has revealed reasonably acceptable results in terms of its usability and learning abilities are concerned. (shrink)

In this book, Christopher Evan Franklin develops and defends a novel version of event-causal libertarianism. This view is a combination of libertarianism--the view that humans sometimes act freely and that those actions are the causal upshots of nondeterministic processes--and agency reductionism--the view that the causal role of the agent in exercises of free will is exhausted by the causal role of mental states and events (e.g., desires and beliefs) involving the agent. Franklin boldly counteracts a dominant theory that has similar (...) aims, put forth by well-known philosopher Robert Kane. -/- Many philosophers contend that event-causal libertarians have no advantage over compatibilists when it comes to securing a distinctively valuable kind of freedom and responsibility. To Franklin, this position is mistaken. Assuming agency reductionism is true, event-causal libertarians need only adopt the most plausible compatibilist theory and add indeterminism at the proper juncture in the genesis of human action. The result is minimal event-causal libertarianism: a model of free will with the metaphysical simplicity of compatibilism and the intuitive power of libertarianism. And yet a worry remains: toward the end of the book, Franklin reconsiders his assumption of agency reductionism, arguing that this picture faces a hitherto unsolved problem. This problem, however, has nothing to do with indeterminism or determinism, or even libertarianism or compatibilism, but with how to understand the nature of the self and its role in the genesis of action. Crucially, if this problem proves unsolvable, then not only is event-causal libertarianism untenable, so also is event-causal compatibilism. (shrink)

People’s concept of free will is often assumed to be incompatible with the deterministic, scientific model of the universe. Indeed, many scholars treat the folk concept of free will as assuming a special form of nondeterministic causation, possibly the notion of uncaused causes. However, little work to date has directly probed individuals’ beliefs about what it means to have free will. The present studies sought to reconstruct this folk concept of free will by asking people to define the concept (Study (...) 1) and by confronting them with a neuroscientific claim that free will is an illusion (Study 2), which invited them to either reconcile or contrast free will with determinism. The results suggest that the core of people’s concept of free will is a choice that fulfills one’s desires and is free from internal or external constraints. No evidence was found for metaphysical assumptions about dualism or indeterminism. (shrink)

In this paper, we investigate the use of event models for automated planning. Event models are the action defining structures used to define a semantics for dynamic epistemic logic. Using event models, two issues in planning can be addressed: Partial observability of the environment and knowledge. In planning, partial observability gives rise to an uncertainty about the world. For single-agent domains, this uncertainty can come from incomplete knowledge of the starting situation and from the nondeterminism of actions. In multi-agent (...) domains, an additional uncertainty arises from the fact that other agents can act in the world, causing changes that are not instigated by the agent itself. For an agent to successfully construct and execute plans in an uncertain environment, the most widely used formalism in the literature on automated planning is “belief states”: sets of different alternatives for the current state of the world. Epistemic logic is a significantly more expressive and theoretically better founded method for representing knowledge and ignorance about the world. Further, epistemic logic allows for planning according to the knowledge (and iterated knowledge) of other agents, allowing the specification of a more complex class of planning domains, than those simply concerned with simple facts about the world. We show how to model multi-agent planning problems using Kripke-models for representing world states, and event models for representing actions. Our mechanism makes use of slight modifications to these concepts, in order to model the internal view of agents, rather than that of an external observer. We define a type of planning domain called epistemic planning domains, a generalisation of classical planning domains, and show how epistemic planning can successfully deal with partial observability, nondeterminism, knowledge and multiple agents. Finally, we show epistemic planning to be decidable in the single-agent case, but only semi-decidable in the multi-agent case. (shrink)

There are two foundational, but not fully developed, ideas in paraconsistency, namely, the duality between paraconsistent and intuitionistic paradigms, and the introduction of logical operators that express metalogical notions in the object language. The aim of this paper is to show how these two ideas can be adequately accomplished by the logics of formal inconsistency and by the logics of formal undeterminedness. LFIs recover the validity of the principle of explosion in a paraconsistent scenario, while LFUs recover the validity of (...) the principle of excluded middle in a paracomplete scenario. We introduce definitions of duality between inference rules and connectives that allow comparing rules and connectives that belong to different logics. Two formal systems are studied, the logics mbC and mbD, that display the duality between paraconsistency and paracompleteness as a duality between inference rules added to a common core—in the case studied here, this common core is classical positive propositional logic. The logics mbC and mbD are equipped with recovery operators that restore classical logic for, respectively, consistent and determined propositions. These two logics are then combined obtaining a pair of LFI and undeterminedness, namely, mbCD and mbCDE. The logic mbCDE exhibits some nice duality properties. Besides, it is simultaneously paraconsistent and paracomplete, and able to recover the principles of excluded middle and explosion one at a time. The last sections offer an algebraic account for such logics by adapting the swap structures semantics framework of the LFIs the LFUs. This semantics highlights some subtle aspects of these logics, and allows us to prove decidability by means of finite nondeterministic matrices. (shrink)

Maximality is a desirable property of paraconsistent logics, motivated by the aspiration to tolerate inconsistencies, but at the same time retain from classical logic as much as possible. In this paper we introduce the strongest possible notion of maximal paraconsistency, and investigate it in the context of logics that are based on deterministic or non-deterministic three-valued matrices. We show that all reasonable paraconsistent logics based on three-valued deterministic matrices are maximal in our strong sense. This applies to practically all three-valued (...) paraconsistent logics that have been considered in the literature, including a large family of logics which were developed by da Costa's school. Then we show that in contrast, paraconsistent logics based on three-valued properly nondeterministic matrices are not maximal, except for a few special cases (which are fully characterized). However, these non-deterministic matrices are useful for representing in a clear and concise way the vast variety of the (deterministic) three-valued maximally paraconsistent matrices. The corresponding weaker notion of maximality, called premaximal paraconsistency, captures the "core" of maximal paraconsistency of all possible paraconsistent determinizations of a non-deterministic matrix, thus representing what is really essential for their maximal paraconsistency. (shrink)

What can the creation of artificial habitats to replace old-growth forests tell us about the process, value and future of design? This chapter takes a concrete and provocative example and uses it to rethink design as a gradual, ecological action. To illustrate this understanding, the chapter begins with a description of a proposal to provide artificial habitats for wild animals such as birds, bats and invertebrates. The controversial idea to replace rapidly disappearing old-growth trees with artificial structures puts in doubt (...) habitual assumptions about the clients, procedures and goals of design. This example is of relevance to all design because the need to provide artificial habitats to nonhumans will be increasingly common under the influence of such phenomena as global warming or urbanisation. … The invention of artificial structures in place of natural habitats is described in this chapter as an incitement that highlights the need for further research into values, participants and methods of design. This discussion concludes with a proposal for an attitude of modesty in the face of increasingly overwhelming volumes of information as well as in the presence of an even greater ignorance about the futures of nondeterministic, volatile and incompletely controllable natural systems. The dilemma of design in these conditions is in the tension between its remit to act and the uncertainty that inescapably underlies any creative endeavour. (shrink)

Based on the computation mode introduced in [13], we deal with the time complexity of computations over arbitrary first-order structures.The main emphasis is on parameter-free computations. Some transfer results for solutions of P versus NP problems as well as relationships to quantifier elimination are discussed. By computation tree analysis using first-order formulas, it follows that P versus NP solutions and other results of structural complexity theory are invariant under elementary equivalence of structures.

A graph-theoretic account of logics is explored based on the general notion of m-graph (that is, a graph where each edge can have a finite sequence of nodes as source). Signatures, interpretation structures and deduction systems are seen as m-graphs. After defining a category freely generated by a m-graph, formulas and expressions in general can be seen as morphisms. Moreover, derivations involving rule instantiation are also morphisms. Soundness and completeness theorems are proved. As a consequence of the generality of the (...) approach our results apply to very different logics encompassing, among others, substructural logics as well as logics with nondeterministic semantics, and subsume all logics endowed with an algebraic semantics. (shrink)

Bohm’s interpretation of quantum mechanics has generally been received as an attempt to restore the determinism of classical physics. However, although this interpretation, as Bohm initially proposed it in 1952, does indeed have the feature of being deterministic, for Bohm this was never the main point. In fact, in other publications and in correspondence from this period, he argued that the assumption that nature is deterministic is unjustified and should be abandoned. Whereas it has been argued before that Bohm’s commitment (...) to determinism was connected to his interest in Marxism, I argue for the opposite: Bohm found resources in Marxist philosophy for developing a nondeterministic notion of causality, which is based on the idea of infinite complexity and an infinite number of levels of nature. From ca. 1954 onwards, Bohm’s conception of causality further weakened, as he developed the idea of a dialectical relation between causality and chance. (shrink)

We define theories of bounded arithmetic, whose definable functions and relations are exactly those in certain complexity classes. Based on a recursion-theoretic characterization of NC in Clote , the first-order theory TNC, whose principal axiom scheme is a form of short induction on notation for nondeterministic polynomial-time computable relations, has the property that those functions having nondeterministic polynomial-time graph Θ such that TNC x y Θ are exactly the functions in NC, computable on a parallel random-access machine in polylogarithmic parallel (...) time with a polynomial number of processors.0 We then define three theories of weak second-order arithmetic which respectively characterize relations in the classes of alternating logarithmic time, logspace and nondeterministic logspace. (shrink)