A real X is defined to be relatively c.e. if there is a real Y such that X is c.e.(Y) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X \not\leq_T Y}$$\end{document}. A real X is relatively simple and above if there is a real Y (...) nonempty \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} class contains a member which is not relatively c.e. and that every 1-generic real is relatively simple and above. (shrink)

I develop a theory of counterfactuals about relative computability, i.e. counterfactuals such as 'If the validity problem were algorithmically decidable, then the halting problem would also be algorithmically decidable,' which is true, and 'If the validity problem were algorithmically decidable, then arithmetical truth would also be algorithmically decidable,' which is false. These counterfactuals are counterpossibles, i.e. they have metaphysically impossible antecedents. They thus pose a challenge to the orthodoxy about counterfactuals, which would treat them as uniformly true. What’s (...) more, I argue that these counterpossibles don’t just appear in the periphery of relative computability theory but instead they play an ineliminable role in the development of the theory. Finally, I present and discuss a model theory for these counterfactuals that is a straightforward extension of the familiar comparative similarity models. (shrink)

The segregation of image parts into foreground and background is an important aspect of the neural computation of 3D scene perception. To achieve such segregation, the brain needs information about border ownership; that is, the belongingness of a contour to a specific surface represented in the image. This article presents psychophysical data derived from 3D percepts of figure and ground that were generated by presenting 2D images composed of spatially disjoint shapes that pointed inward or outward relative to the (...) continuous boundaries that they induced along their collinear edges. The shapes in some images had the same contrast (black or white) with respect to the background gray. Other images included opposite contrasts along each induced continuous boundary. Psychophysical results demonstrate conditions under which figure-ground judgment probabilities in response to these ambiguous displays are determined by the orientation of contrasts only, not by their relative contrasts, despite the fact that many border ownership cells in cortical area V2 respond to a preferred relative contrast. Studies are also reviewed in which both polarity-specific and polarity-invariant properties obtain perceptual figure-ground grouping results. The FACADE and 3D LAMINART models are used to explain these data. Keywords: figure-ground separation, border ownership, perceptual grouping, surface filling-in, V2, V4, FACADE Theory. (shrink)

Significant variation in performance in motor imagery tasks impedes their wide adoption for brain-computer interface applications. Previous researchers have found that resting-state alpha-band power is positively correlated with MI-BCI performance. In this study, we designed a neurofeedback training protocol based on the up-regulation of the alpha band relative power to investigate its effect on MI-BCI performance. The principal finding of this study is that alpha NFT could successfully help subjects increase alpha-rhythm power and improve their MI-BCI performance. An individual (...) difference was also found in this study in that subjects who increased alpha power more had a better performance improvement. Additionally, the functional connectivity of the frontal-parietal network was found to be enhanced after alpha NFT. However, the enhancement failed to reach a significant level after multiple comparisons correction. These findings contribute to a better understanding of the neurophysiological mechanism of cognitive control through alpha regulation. (shrink)

Traditional diversity measures such as the Shannon entropy are generally computed from the species' relative abundance vector of a given community to the exclusion of species' absolute abundances. In this paper, I first mention some examples where the total information content associated with a given community may be more adequate than Shannon's average information content for a better understanding of ecosystem functioning. Next, I propose a parametric measure of statistical information that contains both Shannon's entropy and total information content (...) as special cases of this more general function. (shrink)

The question ‘What is computation?’ might seem a trivial one to many, but this is far from being in consensus in philosophy of mind, cognitive science and even in physics. The lack of consensus leads to some interesting, yet contentious, claims, such as that cognition or even the universe is computational. Some have argued, though, that computation is a subjective phenomenon: whether or not a physical system is computational, and if so, which computation it performs, is entirely a matter of (...) an observer choosing to view it as such. According to one view, which we dub bold anti-realist pancomputationalism, every physical object (can be said to) computes every computer program. According to another, more modest view, some computational systems can be ascribed multiple computational descriptions. We argue that the first view is misguided, and that the second view need not entail observer-relativity of computation. At least to a large extent, computation is an objective phenomenon. Construed as a form of information processing, we argue that information-processing considerations determine what type of computation takes place in physical systems. (shrink)

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

PurposeThe purpose of this paper is to present a four component model of ethical behavior (PRIMES) that integrates literature in moral psychology, computing ethics, and virtue ethics as informed by research on moral exemplars in computing. This is part 1 of a two‐part contribution.Design/methodology/approachThis psychologically based and philosophically informed model argues that moral action is: grounded in relatively stable PeRsonality characteristics (PR); guided by integration of morality into the self‐system; shaped by the context of the surrounding moral ecology; and facilitated (...) by morally relevant skills and knowledge (S).FindingsThe model seeks to explain the daily successful (and unsuccessful) performance of moral action by computing professionals and to provide groundwork for a pedagogy that emphasizes ethically effective performance.Practical implicationsThe model has significant implications for how ethical action might be taught to computer professionals and other design professionals. It also makes recommendations about what is needed to measure to construct a complete picture of sustained ethical action in a profession.Originality/valueMost accepted models of ethical behavior are unidimensional, emphasizing either principled reasoning or a simplistic model of integrity/character. This model brings together a variety of disparate literatures in the light of its emphasis on sustained moral action in the profession. It thereby provides researchers and educators with a picture of what is needed to construct a complete understanding of moral action in the profession. (shrink)

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

One of the most significant challenges in the application of brain-computer interfaces is the large performance variation, which often occurs over time or across users. Recent evidence suggests that the physiological states may explain this performance variation in BCI, however, the underlying neurophysiological mechanism is unclear. In this study, we conducted a seven-session motor-imagery experiment on 20 healthy subjects to investigate the neurophysiological mechanism on the performance variation. The classification accuracy was calculated offline by common spatial pattern and support vector (...) machine algorithms to measure the MI performance of each subject and session. Relative Power values from different rhythms and task stages were used to reflect the physiological states and their correlation with the BCI performance was investigated. Results showed that the alpha band RP from the supplementary motor area within a few seconds before MI was positively correlated with performance. Besides, the changes of RP between task and pre-task stage from theta, alpha, and gamma band were also found to be correlated with performance both across time and subjects. These findings reveal a neurophysiological manifestation of the performance variations, and would further provide a way to improve the BCI performance. (shrink)

We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko [19] et al. Although this definition of TIME as the maximum of a generally infinite family of numbers looks straightforward, at first glance, examples for which this maximum exists seem to be very rare. It is the main purpose of this paper to prove that, nevertheless, the (...) definition has a large number of important applications. Using the framework of TTE [40], we introduce computable metric spaces and computability on the compact subsets. We prove that every computable metric space has a c-proper c-admissible representation. We prove that Turing machine time complexity of a function computable relative to c-admissible c-proper representations has a computable bound on every computable compact subset. We prove that computably compact computable metric spaces have concise c-proper c-admissible representations and show by examples that many canonical representations are of this kind. Finally, we compare our definition with a similar one by Labhalla et al. [22]. Several examples illustrate the concepts. By these results natural and realistic definitions of computational complexity are now available for a variety of numerical problems such as image processing, integration, continuous Fourier transform or wave propagation. (shrink)

Computational techniques comparing co-occurrences of city names in texts allow the relative longitudes and latitudes of cities to be estimated algorithmically. However, these techniques have not been applied to estimate the provenance of artifacts with unknown origins. Here, we estimate the geographic origin of artifacts from the Indus Valley Civilization, applying methods commonly used in cognitive science to the Indus script. We show that these methods can accurately predict the relative locations of archeological sites on the basis of (...) artifacts of known provenance, and we further apply these techniques to determine the most probable excavation sites of four sealings of unknown provenance. These findings suggest that inscription statistics reflect historical interactions among locations in the Indus Valley region, and they illustrate how computational methods can help localize inscribed archeological artifacts of unknown origin. The success of this method offers opportunities for the cognitive sciences in general and for computational anthropology specifically. (shrink)

This volume summarizes the ethical, social and cultural contexts of interfacing brains and computers. It is intended for the interdisciplinary community of BCI stakeholders. Insofar, engineers, neuroscientists, psychologists, physicians, care-givers and also users and their relatives are concerned. For about the last twenty years brain-computer-interfaces (BCIs) have been investigated with increasing intensity and have in principle shown their potential to be useful tools in diagnostics, rehabilitation and assistive technology. The central promise of BCI technology is enabling severely impaired people in (...) mobility, grasping, communication, and entertainment. Successful applications are for instance communication devices enabling locked-in patients in staying in contact with their environment, or prostheses enabling paralysed people in reaching and grasping. In addition to this, it serves as an introduction to the whole field of BCI for any interested reader. (shrink)

The aim of this paper is to begin developing a version of Gualtiero Piccinini’s mechanistic account of computation that does not need to appeal to any notion of proper (or teleological) functions. The motivation for doing so is a general concern about the role played by proper functions in Piccinini’s account, which will be evaluated in the first part of the paper. I will then propose a potential alternative approach, where computing mechanisms are understood in terms of Carl Craver’s perspectival (...) account of mechanistic functions. According to this approach, the mechanistic function of ‘performing a computation’ can only be attributed relative to an explanatory perspective, but such attributions are nonetheless constrained by the underlying physical structure of the system in question, thus avoiding unlimited pancomputationalism. If successful, this approach would carry with it fewer controversial assumptions than Piccinini’s original account, which requires a robust understanding of proper functions. Insofar as there are outstanding concerns about the status of proper functions, this approach would therefore be more generally acceptable. (shrink)

Computer simulation modeling is an important part of contemporary scientific practice but has not yet received much attention from philosophers. The present project helps to fill this lacuna in the philosophical literature by addressing three questions that arise in the context of computer simulation of Earth's climate. Computer simulation experimentation commonly is viewed as a suspect methodology, in contrast to the trusted mainstay of material experimentation. Are the results of computer simulation experiments somehow deeply problematic in ways that the results (...) of material experiments are not? I argue against categorical skepticism toward the results of computer simulation experiments by revealing important parallels in the epistemologies of material and computer simulation experimentation. It has often been remarked that simple computer simulation models---but not complex ones---contribute substantially to our understanding of the atmosphere and climate system. Is this view of the relative contributions of simple and complex models tenable? I show that both simple and complex climate models can promote scientific understanding and argue that the apparent contribution of simple models depends upon whether a causal or deductive account of scientific understanding is adopted. When two incompatible scientific theories are under consideration, they typically are viewed as competitors, and we seek evidence that refutes at least one of the theories. In the study of climate change, however, logically incompatible computer simulation models are accepted as complementary resources for investigating future climate. How can we make sense of this use of incompatible models? I show that a collection of incompatible climate models persists in part because of difficulties faced in evaluating and comparing climate models. I then discuss the rationale for using these incompatible models together and argue that this climate model pluralism has both competitive and integrative components. (shrink)

Unlimited pancomputationalism is the claim that every physical system implements every computational model simultaneously. Some philosophers argue that unlimited pancomputationalism renders implementation ‘trivial’ or ‘vacuous’, unsuitable for serious scientific work. A popular and natural reaction to this argument is to reject unlimited pancomputationalism. However, I argue that given certain assumptions about the nature of computational ascription, unlimited pancomputationalism does not entail that implementation is trivial. These assumptions concern the relativity and context sensitivity of computational ascription. Very roughly: relative to (...) a specific, contextually salient way of regarding a physical system computationally, the claim that that system implements a specific computational model is as non-trivial as one could reasonably want. (shrink)

The computer is a relatively new invention in the history of man. It has found application in many sectors, and will undoubtedly influence our society. As we shall show, however, the computer is linked to a chain of development that started 10,000 years ago, when a society of hunters and gatherers changed into an agricultural society. The computer is completely dependent on this development towards a more and more formalized society.

Let R be a real closed field. An integer part I for R is a discretely ordered subring such that for every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r \in R}$$\end{document}, there exists an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${i \in I}$$\end{document} so that i ≤ r < i + 1. Mourgues and Ressayre (J Symb Logic 58:641–647, 1993) showed that every real closed field has an integer part. The procedure of Mourgues and (...) Ressayre appears to be quite complicated. We would like to know whether there is a simple procedure, yielding an integer part that is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2(R)}$$\end{document} —limit computable relative to R. We show that there is a maximal Z-ring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I \subseteq R}$$\end{document} which is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2(R)}$$\end{document}. However, this I may not be an integer part for R. By a result of Wilkie (Logic Colloquium ’77), any Z-ring can be extended to an integer part for some real closed field. Using Wilkie’s ideas, we produce a real closed field R with a Z-ring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I \subseteq R}$$\end{document} such that I does not extend to an integer part for R. For a computable real closed field, we do not know whether there must be an integer part in the class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2}$$\end{document}. We know that certain subclasses of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2}$$\end{document} are not sufficient. We show that for each \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n \in \omega}$$\end{document}, there is a computable real closed field with no n-c.e. integer part. In fact, there is a computable real closed field with no n-c.e. integer part for any n. (shrink)

Computational complexity theory is a subfield of computer science originating in computability theory and the study of algorithms for solving practical mathematical problems. Amongst its aims is classifying problems by their degree of difficulty — i.e., how hard they are to solve computationally. This paper highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones — e.g., about the notion of feasibility in mathematics, the $\mathbf{P} (...) \neq \mathbf{NP}$ problem and why it has proven hard to resolve, and the role of non-classical modes of computation and proof. (shrink)

The relationship between abstract formal procedures and the activities of actual physical systems has proved to be surprisingly subtle and controversial, and there are a number of competing accounts of when a physical system can be properly said to implement a mathematical formalism and hence perform a computation. I defend an account wherein computational descriptions of physical systems are high-level normative interpretations motivated by our pragmatic concerns. Furthermore, the criteria of utility and success vary according to our diverse purposes and (...) pragmatic goals. Hence there is no independent or uniform fact to the matter, and I advance the ‘anti-realist’ conclusion that computational descriptions of physical systems are not founded upon deep ontological distinctions, but rather upon interest-relative human conventions. Hence physical computation is a ‘conventional’ rather than a ‘natural’ kind. (shrink)

We introduce a notion of relative efficiency for axiom systems. Given an axiom system Aβ for a theory T consistent with S12, we show that the problem of deciding whether an axiom system Aα for the same theory is more efficient than Aβ is II2-hard. Several possibilities of speed-up of proofs are examined in relation to pairs of axiom systems Aα, Aβ, with Aα ⊇ Aβ, both in the case of Aα, Aβ having the same language, and in the (...) case of the language of Aα extending that of Aβ: in the latter case, letting Prα, Prβ denote the theories axiomatized by Aα, Aβ, respectively, and assuming Prα to be a conservative extension of Prβ, we show that if Aα — Aβ contains no nonlogical axioms, then Aα can only be a linear speed-up of Aβ; otherwise, given any recursive function g and any Aβ, there exists a finite extension Aα of Aβ such that Aα is a speed-up of Aβ with respect to g. (shrink)

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

Relative to digital computation, analogue computation has been neglected in the philosophical literature. To the extent that attention has been paid to analogue computation, it has been misunderstood. The received view—that analogue computation has to do essentially with continuity—is simply wrong, as shown by careful attention to historical examples of discontinuous, discrete analogue computers. Instead of the received view, I develop an account of analogue computation in terms of a particular type of analogue representation that allows for discontinuity. This (...) account thus characterizes all types of analogue computation, whether continuous or discrete. Furthermore, the structure of this account can be generalized to other types of computation: analogue computation essentially involves analogue representation, whereas digital computation essentially involves digital representation. Besides being a necessary component of a complete philosophical understanding of computation in general, understanding analogue computation is important for computational explanation in contemporary neuroscience and cognitive science. (shrink)

We examine the interrelationships between analog computational modelling and analogue (physical) modelling. To this end, we attempt a regimentation of the informal distinction between analog and digital, which turns on the consideration of computing in a broader context. We argue that in doing so one comes to see that (scientific) computation is better conceptualised as an epistemic process relative to agents, wherein representations play a key role. We distinguish between two, conceptually distinct, kinds of representation that, we argue, are (...) both involved in each case of computing. Based on the semantic and syntactic properties of each of these representations, we put forward a new account of the distinction between analog and digital computing. We discuss how the developed account is able to explain various properties of different models of computation, and we finish by conceptually comparing analog computational modelling to analogue (scale) modelling. It is concluded that, contrary to the standard view, the two practices are orthogonal, differing both in their foundations and in the epistemic functions they fulfil. (shrink)

A set of natural numbers B is computably enumerable in and strictly above (or c.e.a. for short) another set C if C < T B and B is computably enumerable in C. A Turing degree b is c.e.a. c if b and c respectively contain B and C as above. In this paper, it is shown that if b is c.e.a. c then b is c.e.a. some 1-generic g.

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

We consider the following problem for various infinite-time machines. If a real is computable relative to a large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable? We show that the answer is independent of ZFC for ordinal Turing machines with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite-time Turing machines, unresetting (...) and resetting infinite-time register machines, and α-Turing machines for countable admissible ordinals α. (shrink)

Neurulation, the curling of the neuroepithelium to form the neural tube, is an essential component of the development of animal embryos. Defects of neural tube formation, which occur with an overall frequency of one in 500 human births, are the cause of severe and distressing congenital abnormalities. However, despite the fact that there is increasing information from animal experiments about the mechanisms which effect neural tube formation, much less is known about the fundamental causes of neural tube defects (NTD). The (...) use of computer models provides one way of gaining clues about the ways in which neurulation may be compromised. Here we employ one computer model to examine the robustness of different cellular mechanisms which are thought to contribute to neurulation. The model, modified from that of Odell et al (Odell, G.M., Oster, G., Alberch, P. and Burnside, B., (1981)) mimics neurulation by laterally propagating a wave of apical contraction along an active zone within a ring of cells. We link the results to experimental evidence gained from studies of embryos in which neurulation has been perturbed. The results indicate that alteration of one of the properties of non-neural tissue can delay or inhibit neurulation, supporting the idea, gained from observation of embryos bearing genes which predispose to NTD, that the tissue underlying the neuroepithelium may contribute to the elevation of the neural folds. The results also show that reduction of the contractile properties of a small proportion of the neuroepithelial cell population may have a profound effect on overall tissue profiling. The results suggest that the elevation of the neural folds, and hence successful neurulation, may be vulnerable to relatively minor deficiencies in cell properties. (shrink)

This paper explores the concept of anticipation of future interaction (AFI) in Computer?Mediated Communication (CMC) with conflict management. Specifically, the tenet of the current paper is to determine whether CMC is suitable for conflict management. This central question was address drawing on anticipation of future interaction. Along this line, the issue of task, identity, self?presentations are discussed relative to the role of anticipation of future interaction in CMC encounters. Specific propositions are presented. The discussion addresses implications for group conflict (...) management process in general while paying attention to the key stages of conflict management. (shrink)

I propose to consider the question, "Can machines think?" This should begin with definitions of the meaning of the terms "machine" and "think." The definitions might be framed so as to reflect so far as possible the normal use of the words, but this attitude is dangerous, If the meaning of the words "machine" and "think" are to be found by examining how they are commonly used it is difficult to escape the conclusion that the meaning and the answer to (...) the question, "Can machines think?" is to be sought in a statistical survey such as a Gallup poll. But this is absurd. Instead of attempting such a definition I shall replace the question by another, which is closely related to it and is expressed in relatively unambiguous words. The new form of the problem can be described in terms of a game which we call the 'imitation game." It is played with three people, a man (A), a woman (B), and an interrogator (C) who may be of either sex. The interrogator stays in a room apart front the other two. The object of the game for the interrogator is to determine which of the other two is the man and which is the woman. He knows them by labels X and Y, and at the end of the game he says either "X is A and Y is B" or "X is B and Y is A." The interrogator is allowed to put questions to A and B. We now ask the question, "What will happen when a machine takes the part of A in this game?" Will the interrogator decide wrongly as often when the game is played like this as he does when the game is played between a man and a woman? These questions replace our original, "Can machines think?". (shrink)

This book features more than 20 papers that celebrate the work of Hajnal Andréka and István Németi. It illustrates an interaction between developing and applying mathematical logic. The papers offer new results as well as surveys in areas influenced by these two outstanding researchers. They also provide details on the after-life of some of their initiatives. Computer science connects the papers in the first part of the book. The second part concentrates on algebraic logic. It features a range of papers (...) that hint at the intricate many-way connections between logic, algebra, and geometry. The third part explores novel applications of logic in relativity theory, philosophy of logic, philosophy of physics and spacetime, and methodology of science. They include such exciting subjects as time travelling in emergent spacetime. The short autobiographies of Hajnal Andréka and István Németi at the end of the book describe an adventurous journey from electric engineering and Maxwell’s equations to a complex system of computer programs for designing Hungary’s electric power system, to exploring and contributing deep results to Tarskian algebraic logic as the deepest core theory of such questions, then on to applications of the results in such exciting new areas as relativity theory in order to rejuvenate logic itself. (shrink)

It is natural for humans to judge the outcome of a decision under uncertainty as a percentage of an ex-post optimal performance. We propose a robust decision-making framework based on a relative performance index. It is shown that if the decision maker’s preferences satisfy quasisupermodularity, single-crossing, and a nondecreasing log-differences property, the worst-case relative performance index can be represented as the lower envelope of two extremal performance ratios. The latter is used to characterize the agent’s optimal robust decision, (...) which has implications both computationally and for obtaining closed-form solutions. We illustrate our results in an application which compares the performance of relative robustness to solutions that optimize worst-case payoffs, maximum absolute regret, and expected payoffs under a Laplacian prior. (shrink)

This article discusses what may be referred to as ``adjectival relatives''''in Japanese and related constructions in other languages (such asadjectival passives in English). The most intriguing characteristicof this construction is that the verb contained in it occurs in the pasttense form, but its primary role is to describe a state that obtains atthe local evaluation time, rather than the past event that producedthis state. In fact, in some cases, the putative event that presumablyproduced the target state is non-existent, and the (...) entire constructionreceives a purely stative interpretation. In other words, it is possiblefor an adjectival relative to describe a target state without having itstriggering event. The proposal I put forth in the article states that whatI refer to as an adjectival relative does not have a clausal structure.It rather has a verbal projection (technically a Tense Phrase, or TP). Mod(the modifier head) then combined with TP to yield a MP (modifierphrase), which denotes a property of states that appear to have resultedfrom an event the verb describes. In order to reach this conclusion, I adopttwo additional ideas: (i) Kratzer''s (1996) idea that the so-called externalargument of a verb is not really its argument at all; (ii) direct causationdoes not have to be overtly represented in natural language syntax (Bittner1999). Having incorporated these two ideas, the proposal explains therelation between the state that the adjectival relative describes and theputative event as a modal one, thereby accounting for the non-existenceof putative past events in some examples. (shrink)

We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber [7]. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any (...) Borel quotient of the reals reduces to it. (shrink)

The vision of the new generation of office systems is based on the hypothesis that an automatic support system is all the more useful and acceptable, the more systems behaviour and performance are in accordance with features ofhuman behaviour. Consequently recent development activities are influenced by the paradigm of the computer as man's “cooperative assistant”. The metaphors ofassistance andcooperation illustrate some major requirements to be met by new office systems. Cooperative office systems will raise a set of new questions about (...) the future of human work, human-machine interaction, the forms of individual control of work, the scope of action and the development of competence in the frame of AI-supported cooperative work, the relative benefits of different types of organizations, etc. With increasing autonomy of the computer in task accomplishment, research should also be concerned with the question of the limits of such a development. In AI-research and development there is much discussion of the intended performance of that new technology. Perhaps this will provide insights into, how these new machines should support numerous aspects of individual or cooperative work. But we find fewer ideas about the future ofhuman work. What will the role of thehuman actor be in future AI-supported cooperative work? What kind of work do we want to support with AI-machines? In the following article I will try to identify some questions for further sociological research activities. I will base my considerations on some theoretical aspects ofunderstanding andmeaning. Regarding identical and non-identical aspects in communication behaviour of human and machines, I will focus on some questions to be investigated. Finally some methodological problems of sociological research in the field of Artificial Intelligence will be discussed, especially the so-called “Time-Dilemma” of sociological research in technology. (shrink)

We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elements enter them relative to elements entering other sets, and the Martin Invariance Conjecture on their Turing degrees, i.e., their information content with respect to relative computability (Turing reducibility).

odel-L¨ ob computability logic. In order to make things relatively self-contained, I sketch the essential ideas of GL, and discuss the significance of its fixpoint theorem. Then I give the algorithm embodied in the program in a little more detail. It should be emphasized that nothing new is presented here — all the theory and methodology are due to others. The main interest is, in a sense, psychological. The approach taken here has been declared in the literature, more than (...) once, to be of theoretical interest only, being too unwieldly in practice. Experimentation shows this is not so provided formulas are not too complicated. A copy of the program can be obtained by ftp from venus.gc.cuny.edu. It is in the subdirectory “/pub/fitting,” under the name “glfixpt.pro.” Log on as “anonymous” and use your full e-mail address as password. If there are difficulties with ftp, send e-mail to the author at mlfl[email protected]. The Prolog code is standard, and should run under any implementation, though minor modifications may be necessary for some systems. These modifications are described in the last section, and also in the program itself. (shrink)

We begin with the history of the discovery of computability in the 1930’s, the roles of Gödel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines . To whom did Gödel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine and Post’s development of it in [1944, §11], [1948], and finally Kleene-Post [1954] into its present form. A number of topics arose from Turing functionals including continuous functionals (...) on Cantor space and online computations. Almost all the results in theoretical computability use relative reducibility and o-machines rather than a-machines and most computing processes in the real world are potentially online or interactive. Therefore, we argue that Turing o-machines, relative computability, and online computing are the most important concepts in the subject, more so than Turing a-machines and standard computable functions since they are special cases of the former and are presented first only for pedagogical clarity to beginning students. At the end in §10–§13 we consider three displacements in computability theory, and the historical reasons they occurred. Several brief conclusions are drawn in §14. (shrink)

We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph into a structure such that has a isomorphic copy if and only if has a computable isomorphic copy.A computable structure is (...) categorical if for all computable isomorphic copies of , there is an isomorphism from onto , which is . We prove that for every computable successor ordinal α, there is a computable, categorical structure, which is not relatively categorical. This generalizes the result of Goncharov that there is a computable, computably categorical structure, which is not relatively computably categorical.An additional relation R on the domain of a computable structure is intrinsically on if in all computable isomorphic copies of , the image of R is . We prove that for every computable successor ordinal α, there is an intrinsically relation on a computable structure, which not relatively intrinsically . This generalizes the result of Manasse that there is an intrinsically computably enumerable relation on a computable structure, which is not relatively intrinsically computably enumerable.The dimension of a structure is the number of computable isomorphic copies, up to isomorphisms. We prove that for every computable successor ordinal α and every n≥1, there is a computable structure with dimension n. This generalizes the result of Goncharov that there is a structure of computable dimension n for every n≥1.Finally, we prove that for every computable successor ordinal α, there is a countable structure with isomorphic copies in just the Turing degrees of sets X such that relative to X is not . In particular, for every finite n, there is a structure with isomorphic copies in exactly the non- Turing degrees. This generalizes the result obtained by Wehner, and independently by Slaman, that there is a structure with isomorphic copies in exactly the nonzero Turing degrees. (shrink)

Adams and Dziobiak proved that any finite-to-finite universal quasivariety must be Q-universal, and then asked whether a somewhat weaker hypothesis could lead to the same conclusion. We show that their original hypothesis cannot be weakened to its naturally extreme form.

Subthalamic nucleus deep brain stimulation is an established therapy for Parkinson’s disease motor symptoms. The ideal site for implantation within STN, however, remains controversial. While many argue that placement of a DBS lead within the sensorimotor territory of the STN yields better motor outcomes, others report similar effects with leads placed in the associative or motor territory of the STN, while still others assert that placing a DBS lead “anywhere within a 6-mm-diameter cylinder centered at the presumed middle of the (...) STN produces similar clinical efficacy.” These discrepancies likely result from methodological differences including targeting preferences, imaging acquisition and the use of brain atlases that do not account for patient-specific anatomic variability. We present a first-in-kind within-patient demonstration of severe mood side effects and minimal motor improvement in a Parkinson’s disease patient following placement of a DBS lead in the limbic/associative territory of the STN who experienced marked improvement in motor benefit and resolution of mood side effects following repositioning the lead within the STN sensorimotor territory. 7 Tesla magnetic resonance imaging data were used to generate a patient-specific anatomical model of the STN with parcellation into distinct functional territories and computational modeling to assess the relative degree of activation of motor, associative and limbic territories. (shrink)

One usually identifies a particular collection of geometric objects with the models of general relativity. But within this standard collection lurk ‘physically unreasonable’ models of spacetime. If such models are ruled out, attention can be restricted to some sub-collection of ‘physically reasonable’ models which can be considered a variant theory of general relativity. Since we have yet to identify a privileged sub-collection of ‘physically reasonable’ models, it is helpful to think of ‘general relativity’ in a pluralistic way; we can study (...) a collection of such ‘physically reasonable’ collections of models. (shrink)

Does Nature permit the implementation of behaviours that cannot be simulated computationally? We consider the meaning of physical computation in some detail, and present arguments in favour of physical hypercomputation: for example, modern scientific method does not allow the specification of any experiment capable of refuting hypercomputation. We consider the implications of relativistic algorithms capable of solving the (Turing) Halting Problem. We also reject as a fallacy the argument that hypercomputation has no relevance because non-computable values are indistinguishable from sufficiently (...) close computable approximations. In addition to considering the nature of computability relative to any given physical theory, we can consider the relationship between versions of computability corresponding to different models of physics. Deutsch and Penrose have argued on mathematical grounds that quantum computation and Turing computation have equivalent formal power. We suggest this equivalence is invalid when considered from the physical point of view, by highlighting a quantum computational behaviour that cannot meaningfully be considered feasible in the classical universe. (shrink)

Following a line of research initiated in [4], we describe a general framework for turning reduction concepts of relative computability into diagrams forming an analogy with the Cichoń diagram for cardinal characteristics of the continuum. We show that working from relatively modest assumptions about a notion of reduction, one can construct a robust version of such a diagram. As an application, we define and investigate the Cichoń diagram for degrees of constructibility relative to a fixed inner model (...) W. Many analogies hold with the classical theory as well as some surprising differences. Along the way, we introduce a new axiom stating, roughly, that the constructibility diagram is as complex as possible. (shrink)