In this paper we study the Kolmogorov complexity for non-effective computations, that is, either halting or non-halting computations on Turing machines. This complexity function is defined as the length of the shortest input that produce a desired output via a possibly non-halting computation. Clearly this function gives a lower bound of the classical Kolmogorov complexity. In particular, if the machine is allowed to overwrite its output, this complexity coincides with the classical Kolmogorov complexity for halting computations (...) relative to the first jump of the halting problem. However, on machines that cannot erase their output –called monotone machines–, we prove that our complexity for non effective computations and the classical Kolmogorov complexity separate as much as we want. We also consider the prefix-free complexity for possibly infinite computations. We study several properties of the graph of these complexity functions and specially their oscillations with respect to the complexities for effective computations. (shrink)

Horsten and Roelants have raised a number of important questions about my analysis of effective procedures and my evaluation of the Church-Turing thesis. They suggest that, on my account, effective procedures cannot enter the mathematical world because they have a built-in component of causality, and, hence, that my arguments against the Church-Turing thesis miss the mark. Unfortunately, however, their reasoning is based upon a number of misunderstandings. Effective mundane procedures do not, on my view, provide an analysis (...) of ourgeneral concept of an effective procedure; mundane procedures and Turing machine procedures are different kinds of procedure. Moreover, the same sequence ofparticular physical action can realize both a mundane procedure and a Turing machine procedure; it is sequences of particular physical actions, not mundane procedures, which enter the world of mathematics. I conclude by discussing whether genuinely continuous physical processes can enter the world of real numbers and compute real-valued functions. I argue that the same kind of correspondence assumptions that are made between non-numerical structures and the natural numbers, in the case of Turing machines and personal computers, can be made in the case of genuinely continuous, physical processes and the real numbers. (shrink)

278 non-freshman university students taking a l2-week critical thinking course in a large single-section class, with computer-assisted guided practice as a replacement for small-group discussion, and all testing in machine-scored multiple-choice format, improved their critical thinking skills, as measured by the California Critical Thinking Skills Test, by half a standard deviation, a moderate improvement. The improvement was more than that reported with a traditional format without computer-assisted instruction, but less than that reported with a format using both computer-assisted instruction and (...) essay-type assignments. Further studies are needed to test hypotheses suggested by these results. (shrink)

This paper shows that a simple two-stage approach to handle non-local dependencies in Named Entity Recognition (NER) can outperform existing approaches that handle non-local dependencies, while being much more computationally efficient. NER systems typically use sequence models for tractable inference, but this makes them unable to capture the long distance structure present in text. We use a Conbel.

The Dutch mathematician and philosopher L. E. J. Brouwer (1881-1966) developed a foundation for mathematics called 'intuitionism'. Intuitionism considers mathematics to consist in acts of mental construction based on internal time awareness. According to Brouwer, that awareness provides the fundamental structure to all exact thinking. In this note, it will be shown how this strand of thought leads to an intuitionistic function that is effectively computable yet non-recursive.

Recently, the Dimension Problem for effective Hausdorff dimension was solved by J. Miller in [14], where the author constructs a Turing degree of non-integral Hausdorff dimension. In this article we settle the Dimension Problem for effective packing dimension by constructing a real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one (on the other hand, it is known via [10, 3, 7] that every real of strictly positive (...) class='Hi'>effective Hausdorff dimension computes reals whose effective packing dimensions are arbitrarily close to, but not necessarily equal to, one). (shrink)

When computing is defined as the causal implementation of algorithms and algorithms are defined as effective decision procedures, human thought is mental computation only if it is governed by mental algorithms. An examination of ordinary thinking, however, suggests that most human thought processes are non-algorithmic. Digital machines, moreover, are mark-manipulating or string-processing systems whose marks or strings do not stand for anything for those systems, while minds are semiotic (or “signusing”) systems for which signs stand for other things for (...) those systems. Computing, at best, turns out to be no more than a special kind of thinking. (shrink)

BackgroundThe prognosis of hypertensive intracerebral hemorrhage is poor at high altitudes. The objective of this study was to explore whether hyperbaric oxygen can improve the results of computed tomography perfusion imaging and the neurological function of patients with HICH, and influence the hemoglobin concentration.MethodThe patients with HICH were treated with puncture and drainage. Twenty-one patients were treated with HBO after the operation, and the other patients received conventional treatment. CTP was performed twice, and all indices were measured. Scatter plots were (...) used to determine the effect of hemoglobin concentration on CTP imaging. Receiver operating characteristic curves were plotted to analyze the effects of hemoglobin concentration and hematoma volume on recovery results. The patients were followed up for 6 months.ResultsForty-one patients with HICH were treated with puncture and drainage. In total, 21 were treated with HBO after the operation, and 20 received conventional treatment as the control group. No significant differences in the CBV and CBF values of the two groups were noted before treatment. After 10 days, the values of CBV and CBF in the HBO group were significantly higher than those in the control group. A scatter diagram showed there was no significant in the HBO group, but significant correlation for the CBV and CBF values in the control group’s hematoma center and margin. The ROC curves showed that hematoma volume had an influence on prognosis of the control group. The Glasgow Coma Scale scores of the HBO group were significantly higher than those of the control group.ConclusionsHBO therapy can improve the postoperative CBV and CBF values of patients with HICH and ameliorate their prognoses. There was no significant correlation between HBO group and hemoglobin concentration on admission. (shrink)

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)

In the first author's thesis [10], a sequential language, LRT, for real number computation is investigated. That thesis includes a proof that all polynomials are programmable, but that work comes short of giving a complete characterization of the expressive power of the language even for first-order functions. The technical problem is that LRT is non-deterministic. So a natural characterization of its expressive power should be in terms of relations rather than in terms of functions. In [2], Brattka examines a formalization (...) of recursive relations in the style of Kleene's recursive functions on the natural numbers. This paper is an expanded version of [13] which establishes the expressive power of LRTp, a variant of LRT, in terms of Brattka's recursive relations. Because Brattka already did the work of establishing the precise connection between his recursive relations and Type 2 Theory of Effectivity, we thus obtain a complete characterization of first-order definability in LRTp. (shrink)

Recent work on hypercomputation has raised new objections against the Church–Turing Thesis. In this paper, I focus on the challenge posed by a particular kind of hypercomputer, namely, SAD computers. I first consider deterministic and probabilistic barriers to the physical possibility of SAD computation. These suggest several ways to defend a Physical version of the Church–Turing Thesis. I then argue against Hogarth's analogy between non-Turing computability and non-Euclidean geometry, showing that it is a non-sequitur. I conclude that the Effective (...) version of the Church–Turing Thesis is unaffected by SAD computation. (shrink)

Oral communication often takes place in noisy environments, which challenge spoken-word recognition. Previous research has suggested that the presence of background noise extends the number of candidate words competing with the target word for recognition and that this extension affects the time course and accuracy of spoken-word recognition. In this study, we further investigated the temporal dynamics of competition processes in the presence of background noise, and how these vary in listeners with different language proficiency (i.e., native and non-native) using (...) computational modeling. We developed ListenIN (Listen-In-Noise), a neural-network model based on an autoencoder architecture, which learns to map phonological forms onto meanings in two languages and simulates native and non-native spoken-word comprehension. We also examined the model's activation states during online spoken-word recognition. These analyses demonstrated that the presence of background noise increases the number of competitor words, which are engaged in phonological competition and that this happens in similar ways intra and interlinguistically and in native and non-native listening. Taken together, our results support accounts positing a “many-additional-competitors scenario” for the effects of noise on spoken-word recognition. (shrink)

For the past two decades, it has widely been assumed by linguists that there is a single computational operation, Merge, which is unique to language, distinguishing it from other cognitive domains. The intention of this paper is to progress the discussion of language evolution in two ways: (i) survey what the ethological record reveals about the uniqueness of the human computational system, and (ii) explore how syntactic theories account for what ethology may determine to be human-specific. It is shown that (...) the operation Label, not Merge, constitutes the evolutionary novelty which distinguishes human language from non-human computational systems; a proposal lending weight to a Weak Continuity Hypothesis and leading to the formation of what is termed Computational Ethology. Some directions for future ethological research are suggested. (shrink)

Given a program of a linear bounded and bijective operator T, does there exist a program for the inverse operator T−1? And if this is the case, does there exist a general algorithm to transfer a program of T into a program of T−1? This is the inversion problem for computable linear operators on Banach spaces in its non-uniform and uniform formulation, respectively. We study this problem from the point of view of computable analysis which is the Turing machine based (...) theory of computability on Euclidean space and other topological spaces. Using a computable version of Banach’s Inverse Mapping Theorem we can answer the first question positively. Hence, the non-uniform version of the inversion problem is solvable, while a topological argument shows that the uniform version is not. Thus, we are in the striking situation that any computable linear operator has a computable inverse while there exists no general algorithmic procedure to transfer a program of the operator into a program of its inverse. As a consequence, the computable version of Banach’s Inverse Mapping Theorem is a powerful tool which can be used to produce highly non-constructive existence proofs of algorithms. We apply this method to prove that a certain initial value problem admits a computable solution. As a preparation of Banach’s Inverse Mapping Theorem we also study the Open Mapping Theorem and we show that the uniform versions of both theorems are limit computable, which means that they are effectively -measurable with respect to the effective Borel hierarchy. (shrink)

Query processing in ground definite deductive is known to correspond precisely to a linear programming problem. However, the “groundedness” requirement is a huge drawback to using linear programming techniques for logic program computations because the ground version of a logic program can be very large when compared to the original program. Furthermore, when we move from propositional logic programs to first-order logic programs, this effectively means that functions symbols may not occur in clauses. In this paper, we develop a (...) theory of “instantiate- by-need” that performs instantiations only when needed. We prove that this method is sound and complete when computing answer substitutions for non-ground logic programs including those containing function symbols. More importantly, when taken in conjunction with Colmerauer's result that unification can be viewed as linear programming, this means that resolution with unification can be completely replaced by linear programming as an operational paradigm. Additionally, our tree construction method is not rigidly tied to the linear programming paradigm-we will show that given any method M that can compute the set of atomic logical consequences of a propositional logic program, our method can use M to compute , the set of all atoms that are consequences of a first-order logic program. (shrink)

This short autodidactic paper compactly introduces the epistemic algorithmic computation (EaC) paradox, a novel analogy to the Turing paradox. Firstly, it is elucidated why in the deepfake era, crafting a provisional solution to the EaC paradox may be beneficent as it may shed more light on one ingrained consequence of the prevailing algorithmic supremacy paradigm: the retrospective obsolescence of the entire biosphere in the game of life precipitated by algorithms instantiated on inert matter. Secondly, the paper analyzes and deconstructs the (...) EaC paradox elucidating why it is contingent on a mirage that can be dissolved by interpreting it as a manifestation of what one could call the epistemic Zeno-effect. There exists at least one computational task where the minimal latency of algorithmic computation would lead to epistemic stagnation – leading to an advantage for slower non-algorithmic computational alternatives. Peculiarly, the latter may be caused by the very lawfulness of nature subsuming both cellular and conscious supremacy. (shrink)

This commentary on John Symons’ and Jack Horner’s paper, besides sharing its main argument, challenges the authors’ statement that there is no effective method to evaluate software-intensive systems as a distinguishing feature of software intensive science. It is underlined here how analogous methodological limitations characterise the evaluations of empirical systems in non-software intensive sciences. The authors’ claim that formal methods establish the correctness of computational models rather than of the represented programme is here compared with the empirical adequacy problem (...) typifying the model-based reasoning approach in physics, and the remark that testing all the paths of a software-intensive system is unfeasible is related to the enumerative induction problem in the justification of empirical law-like hypotheses in non-software intensive sciences. (shrink)

Information technology (IT) is continuously making astounding progress in technical efficiency. The time, space, material and energy needed to provide a unit of IT service have decreased by three orders of magnitude since the first personal computer (PC) was sold. However, it seems difficult for society to translate IT’s efficiency progress into progress in terms of individual, organizational or socio-economic goals. In particular it seems to be difficult for individuals to work more efficiently, for organizations to be more productive and (...) for the socio-economic system to be more sustainable by using increasingly efficient IT. This article provides empirical evidence and potential explanations for this problem. Many counterproductive effects of IT can be explained economically by rebound effects. Beyond that, we conclude that the technological determinism adopted by decision-makers is the main obstacle in translating IT’s progress into non-technical goals. (shrink)

My aim in this article is to make accessible to non-mathematicians the groundwork of the theory of effective methods and unsolvable problems. The beauty of the theory is that it needs hardly any hard work to get very quickly from simple intuitive ideas to some extraordinarily interesting and surprising results.

This is a non-technical version of "The Decision Problem for Effective Procedures." The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that reason, the Church–Turing thesis (that the effectively calculable functions on natural numbers are exactly the general recursive functions), cannot be proved. However, it is logically provable from the notion (...) of an effective procedure--without reliance on any (partially) mathematical thesis or conjecture concerning effective procedures, such as the Church–Turing thesis--that the class of effective procedures is undecidable, i.e., that no effective procedure is possible for ascertaining whether a given procedure is effective. The proof does not appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of such a procedure. Though this undecidability result itself is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure is, in fact, a decision procedure, i.e., effective—for example, that it invariably terminates with the correct verdict. (shrink)

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

The study of ergodic theorems from the viewpoint of computable analysis is a rich field of investigation. Interactions between algorithmic randomness, computability theory and ergodic theory have recently been examined by several authors. It has been observed that ergodic measures have better computability properties than non-ergodic ones. In a previous paper we studied the extent to which non-ergodic measures inherit the computability properties of ergodic ones, and introduced the notion of an effectively decomposable measure. We asked the following question: if (...) the ergodic decomposition of a stationary measure is finite, is this decomposition effective? In this paper we answer the question in the negative. (shrink)

This dissertation investigates some philosophical issues using computational models. Chapter 1 presents a Lewis-Skyrms signaling game that can exhibit a type of compositionality novel to the signaling game literature. The structure of the signaling game is motivated by an analogy to the alarm calls of putty-nosed monkeys (Cercopithecus nictitans). Putty-nosed monkeys display a compositional system of alarm calls with a semantics that is sensitive to the ordering of terms. This sensitivity to the ordering of terms has not been previously modeled (...) with a Lewis-Skyrms signaling game literature. Signaling games are valued for showing how communicative systems can arise with minimal learning tools. Simulation results show that basic (Roth-Erev) reinforcement learning is sufficient for the acquisition of a compositional signaling system sensitive to the ordering of terms. Chapter 2 investigates social epistemology in the context of an effect of cognitive biases called the illusory truth effect. The illusory truth effect is exhibited when repeated exposure to a statement increases an individual's credence in that statement. While most investigations of the illusory truth effect focus on individuals' belief formation, humans typically form beliefs within a social structure. This is particularly relevant because various social structures can give rise to repeated exposure to statements; e.g. a popular book might recurringly be discussed in one's social circle, or one or two foundational papers might always be cited by a particular lab. So, how does the illusory truth effect influence learning and belief formation in a group? This chapter uses network models to investigate this question. These models show that the illusory truth effect can be very detrimental to a group's belief formation. The effect causes networks to prematurely settle on a belief, in part, through repeated exposure to data points that are not independently generated. Previous research has indicated that the probability of such failures is near zero when networks are large or scientists are forced to explore unpopular and risky science. However, simulation results show that the harmful consequences of the illusory truth effect are robust even in large networks with mandatory exploration. Finally, Chapter 3 shows how a rudimentary type of abstraction can obtain in Lewis-Skyrms signaling games. Here, abstraction is understood as occurring when different particulars take on the same functional role. Some abstraction may be guided by innate biases, and the chapter develops an analogy of reasoning about strategic thinking in chess to highlight some epistemic concerns that are raised by the presentation of abstraction. Concretely, the signaling game models of this chapter are developed in the context of two tasks that are much simpler than strategizing in chess. The first task is a transitive inference task that has been substantially studied in both humans and non-human animals. General features of the models developed for the transitive inference task are then carried over to a model for the second task of learning rudimentary grammatical structures. This second task is based on studies of human infants and non-human primates' ability to learn ``nonsense grammars". Closing discussion highlights some strengths of the abstraction exhibited in the Lewis-Skyrms signaling game models. (shrink)

This paper develops my (BJPS 2009) criticisms of the philosophical significance of a certain sort of infinitary computational process, a hyperloop. I start by considering whether hyperloops suggest that "effectively computable" is vague (in some sense). I then consider and criticise two arguments by Hogarth, who maintains that hyperloops undermine the very idea of effective computability. I conclude that hyperloops, on their own, cannot threaten the notion of an effective procedure.

The Lovász local lemma (LLL) is a technique from combinatorics for proving existential results. There are many different versions of the LLL. One of them, the lefthanded local lemma, is particularly well suited for applications to two player games. There are also constructive and computable versions of the LLL. The chief object of this thesis is to prove an effective version of the lefthanded local lemma and to apply it to effectivise constructions of non-repetitive sequences.The second goal of this (...) thesis is to categorize some classes of cohesive powers. We completely describe both the isomorphism types of cohesive powers of equivalence structures and injection structures, as well as clarify the relationship between these cohesive powers and their original structures. We also describe the finite condensation of cohesive powers of computable copies of the integers as a linear order by cohesive sets whose complement are computably enumerable.Finally, we investigate the possibility of decomposing problems in the Weihrauch degrees into a product of first order part and second order part. We give a preliminary result in this direction.Abstract prepared by Daniel Mourad.E-mail: [email protected]: https://daniel-mourad.scholar.uconn.edu/wp-content/uploads/sites/2530/2023/06/ThesisFinalWithRevisio ns-2.pdf. (shrink)

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

We explore the following two cognitive questions regarding crosslinguistic variation in lexical semantic systems: Why are some linguistic categories—that is, the associations between a term and a portion of the semantic space—harder to learn than others? How does learning a language‐specific set of lexical categories affect processing in that semantic domain? Using a computational word‐learner, and the domain of color as a testbed, we investigate these questions by modeling both child acquisition of color terms and adult behavior on a non‐verbal (...) color discrimination task. A further goal is to test an approach to lexical semantic representation based on the principle that the more languages label any two situations with the same word, the more conceptually similar those two situations are. We compare such a crosslinguistically based semantic space to one based on perceptual similarity. Our computational model suggests a mechanistic explanation for the interplay between term frequency and the semantic closeness of learned categories in developmental error patterns for color terms. Our model also indicates how linguistic relativity effects could arise from an acquisition mechanism that yields language‐specific topologies for the same semantic domain. Moreover, we find that the crosslinguistically inspired semantic space supports these results at least as well as—and in some aspects better than—the purely perceptual one, thus confirming our approach as a practical and principled method for lexical semantic representation in cognitive modeling. (shrink)

Inaccurate body size judgements are associated with body image disturbances, a clinical feature of many eating disorders. Accordingly, body related stimuli have become increasingly important in the study of estimation inaccuracies and body image disturbances. Technological advancements in the last decade have led to an increased use of computer generated (CG) body stimuli in body image research. However, recent face perception research has suggested that CG face stimuli are not recognised as readily and may not fully tap facial processing mechanisms. (...) The current study assessed the effectiveness of using CG stimuli in an established body size estimation task (the ‘bodyline’ task). Specifically, we examined whether employing CG body stimuli alters body size judgments and associated estimation biases. One hundred and six 17- to 25-year-old females completed the CG bodyline task, which involved estimating the size of full-length CG body stimuli along a visual analogue scale. Our results show that perception of body size for CG stimuli was non-linear. Participants struggled to discriminate between extreme bodies sizes and overestimated the size change between near to average bodies. Furthermore, one of our measured size estimation biases was larger for CG stimuli. Our collective findings suggest using caution when employing CG stimuli in experimental research on body perception. (shrink)

Classification is an important goal in many branches of mathematics. The idea is to describe the members of some class of mathematical objects, up to isomorphism or other important equivalence, in terms of relatively simple invariants. Where this is impossible, it is useful to have concrete results saying so. In model theory and descriptive set theory, there is a large body of work showing that certain classes of mathematical structures admit classification while others do not. In the present paper, we (...) describe some recent work on classification in computable structure theory.Section 1 gives some background from model theory and descriptive set theory. From model theory, we give sample structure and non-structure theorems for classes that include structures of arbitrary cardinality. We also describe the notion of Scott rank, which is useful in the more restricted setting of countable structures. From descriptive set theory, we describe the basic Polish space of structures for a fixed countable language with fixed countable universe. We give sample structure and non-structure theorems based on the complexity of the isomorphism relation, and on Borel embeddings.Section 2 gives some background on computable structures. We describe three approaches to classification for these structures. The approaches are all equivalent. However, one approach, which involves calculating the complexity of the isomorphism relation, has turned out to be more productive than the others. Section 3 describes results on the isomorphism relation for a number of mathematically interesting classes—various kinds of groups and fields. In Section 4, we consider a setting similar to that in descriptive set theory. We describe an effective analogue of Borel embedding which allows us to make distinctions even among classes of finite structures. Section 5 gives results on computable structures of high Scott rank. Some of these results make use of computable embeddings. Finally, in Section 6, we mention some open problems and possible directions for future work. (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)

In this survey we discuss work of Levin and V’yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V’yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $\mathcal {A}$ and $\mathcal {B}$, $\mathcal {A}$ is below $\mathcal {B}$ in this ordering if $\mathcal {A}\setminus \mathcal {B}$ is negligible. The degree structure associated (...) with this ordering, the Levin–V’yugin degrees, can be shown to be a Boolean algebra, and in fact a measure algebra. We demonstrate the interactions of this work with recent results in computability theory and algorithmic randomness: First, we recall the definition of the Levin–V’yugin algebra and identify connections between its properties and classical properties from computability theory. In particular, we apply results on the interactions between notions of randomness and Turing reducibility to establish new facts about specific LV-degrees, such as the LV-degree of the collection of 1-generic sequences, that of the collection of sequences of hyperimmune degree, and those collections corresponding to various notions of effective randomness. Next, we provide a detailed explanation of a complex technique developed by V’yugin that allows the construction of semi-measures into which computability-theoretic properties can be encoded. We provide two examples of the use of this technique by explicating a result of V’yugin’s about the LV-degree of the collection of Martin-Löf random sequences and extending the result to the LV-degree of the collection of sequences of DNC degree. (shrink)

We expand our effective framework for weak convergence of measures on the real line by showing that effective convergence in the Prokhorov metric is equivalent to effective weak convergence. In addition, we establish a framework for the study of the effective theory of vague convergence of measures. We introduce a uniform notion and a non-uniform notion of vague convergence, and we show that both these notions are equivalent. However, limits under effective vague convergence may not (...) be computable even when they are finite. We give an example of a finite incomputable effective vague limit measure, and we provide a necessary and sufficient condition so that effective vague convergence produces a computable limit. Finally, we determine a sufficient condition for which effective weak and vague convergence of measures coincide. As a corollary, we obtain an effective version of the equivalence between classical weak and vague convergence of sequences of probability measures. (shrink)

Quantum mechanical and molecular dynamics methods were used to analyze the structure and stability of neutral and zwitterionic configurations of the extracted active site sequence from a Burkholderia cepacia lipase, histidyl-seryl-glutamin (His86-Ser87-Gln88) and its mutated form, histidyl-cysteyl-glutamin (His86-Cys87-Gln88) in vacuum and different solvents. The effects of solvent dielectric constant, explicit and implicit water molecules and side chain mutation on the structure and stability of this sequence in both neutral and zwitterionic forms are represented. The quantum mechanics computations represent that (...) the relative stability of zwitterionic and neutral configurations depends on the solvent structure and its dielectric constant. Therefore, in vacuum and the considered non-polar solvents, the neutral form of the interested sequences is more stable than the zwitterionic form, while their zwitterionic form is more stable than the neutral form in the aqueous solution and the investigated polar solvents in most cases. However, on the potential energy surfaces calculated, there is a barrier to proton transfer from the positively charged ammonium group to the negatively charged carboxylat group or from the ammonium group to the adjacent carbonyl oxygen and or from side chain oxygen and sulfur to negatively charged carboxylat group. Molecular dynamics simulations (MD) were also performed by using periodic boundary conditions for the zwitterionic configuration of the hydrated molecules in a box of water molecules. The obtained results demonstrated that the presence of explicit water molecules provides the more compact structures of the studied molecules. These simulations also indicated that side chain mutation and replacement of sulfur with oxygen leads to reduction of molecular flexibility and packing. (shrink)

The Probably Approximately Correct (PAC) learning is a machine learning model introduced by Leslie Valiant in 1984. The PACi reducibility refers to the PAC reducibility independent of size and computation time. This reducibility in PAC learning resembles the reducibility in Turing computability. The ordering of concept classes under PAC reducibility is nonlinear, even when restricted to particular concrete examples.Due to the resemblance to Turing Reducibility, we suspected that there could be incomparable PACi and PAC degrees for the PACi and PAC (...) reducibilities as in Turing incomparable degrees. In 1957 Friedberg and in 1956 Muchnik independently solved the Post problem by constructing computably enumerable sets A and B of incomparable degrees using the priority construction method. We adapt this idea to PACi and PAC reducibilities and construct two effective concept classes C and D such that C is not reducible to D and vice versa. When considering PAC reducibility it was necessary to work on the size of an effective concept class, thus we use Kolmogorov complexity to obtain the size. The non-learnability of concept classes in the PAC learning model is explained by the existence of PAC incomparable degrees.Analogous to the Turing jump, we give a jump operation on effective concept classes for the zero jump. To define the zero jump operator for PACi degrees the join of all the effective concept classes is constructed and proved that it is a greatest element. There are many properties proven for existing degrees. Thus we can explore proving those properties to PACi and PAC degrees. But if we prove an embedding from those degrees to PACi and PAC degrees then those properties will be true for PACi and PAC degrees without explicitly proving them.Abstract prepared by Dodamgodage Gihnee M. Senadheera and taken directly from the thesisE-mail: [email protected]: https://www.proquest.com/docview/2717762461/abstract/ACD19F29A8774AF6PQ/1?accountid=13864. (shrink)

In this paper, we establish a relationship between the join property and Turing degrees of members of effectively closed sets in Cantor space, i.e., classes. We first give a proof of the observation that there exists a non‐empty special class in which no join of two members computes the halting set. We then prove the existence of a non‐empty special class such that no member satisfies the join property, where a degree satisfies the join property if for all non‐zero there (...) exists such that. (shrink)

Information technology (IT) is continuously making astounding progress in technical efficiency. The time, space, material and energy needed to provide a unit of IT service have decreased by three orders of magnitude since the first personal computer (PC) was sold. However, it seems difficult for society to translate IT’s efficiency progress into progress in terms of individual, organizational or socio-economic goals. In particular it seems to be difficult for individuals to work more efficiently, for organizations to be more productive and (...) for the socio-economic system to be more sustainable by using increasingly efficient IT. This article provides empirical evidence and potential explanations for this problem. Many counterproductive effects of IT can be explained economically by rebound effects. Beyond that, we conclude that the technological determinism adopted by decision-makers is the main obstacle in translating IT’s progress into non-technical goals. (shrink)

Center of pressure measurements are often used to identify balance problems. A new method for COP signal analysis using mean frequency is proposed in this paper. The computation of mean frequency is based on the Fourier–Bessel expansion that is suitable for use in non-stationary COP signals. In addition, FB expansion provides better frequency resolution and low frequency detectability. Seventeen subjects were tested under eyes open and eyes closed conditions, with different vibration frequencies applied for the eyes closed condition in order (...) to further perturb sensory information. More accurate estimates of mean frequency were obtained for 200-point segments, with significant increase in mean frequency observed over time as subjects recovered from the initial perturbation of stepping on to the force plate. Subjects were significantly more stable in the mediolateral direction compared to anteroposterior one. Mean frequency as calculated by FB expansion was able to distinguish between eyes open and eyes closed conditions, but no effect of vibration could be detected. (shrink)

Focused on city-scale automation, and using self-driving cars (SDCs) as a case study, this article reflects on the role of AI—and in particular, computer vision systems used for mapping and navigation—as a catalyst for urban transformation. Urban research commonly presents AI and cities as having a one-way cause-and-effect relationship, giving undue weight to AI’s impact on cities and overlooking the role of cities in shaping AI. Working at the intersection of data science and social research, this paper aims to counter (...) this trend by exploring the reverse perspective: how do cities affect the development, and expose the present limits, of SDCs? The contribution of this paper is threefold. First, by comparing urban and nonurban environments and thoroughly examining the relationship between computer vision and city-specific sociality and form, it defines machine autonomy/automation as a function of the sociotechnical milieu in which an AI system operates. Second, and related, the paper problematizes the notion of SDCs as autonomous technologies and the role it plays in envisioning contending policy arrangements and technical solutions for achieving full driving automation. Finally, the article offers insight into a materialist and spatialized understanding of AI—namely, not as an abstract quality susceptible to replication within discrete machines, but rather as a distributed property emerging through embodied interactions among a multiplicity of agents (human, non-human, and technological) within/with their environments. (shrink)

: The open-ended character of natural languages calls for the hypothesis that humans are endowed with a recursive procedure generating sentences which are hierarchically organized. Structural relations such as c-command, expressed on hierarchical sentential representations, determine all sorts of formal and interpretive properties of sentences. The relevant computational principles are well beyond the reach of conscious introspection, so that studying such properties requires the formulation of precise formal hypotheses, and empirically testing them. This article illustrates all these aspects of linguistic (...) research through the discussion of non-coreference effects. The article argues in favor of the formal linguistic approach based on hierarchical structures, and against alternatives based on vague notions of “analogical generalization”, and/or exploiting mere linear order. In the final part, the issue of cross-linguistic invariance and variation of non-coreference effects is addressed. Keywords: Linguistic Knowledge; Morphosyntactic Properties; Unconscious Computations; Coreference; Linguistic Representations Conoscenza linguistica e computazioni inconsce Riassunto: Il carattere aperto del linguaggio naturale avvalora l’ipotesi che gli esseri umani siano dotati di una procedura ricorsiva che genera frasi gerarchicamente organizzate. Relazioni strutturali come il c-comando, espresse su rappresentazioni frasali gerarchiche, determinano tutte le proprietà formali e interpretative delle frasi. I principi computazionali rilevanti sono totalmente al di fuori della portata della coscienza introspettiva e così lo studio di tali proprietà richiede la formulazione di precise ipotesi formali e la loro verifica sperimentale. Questo articolo illustra tutti questi aspetti della ricerca linguistica, esaminando gli effetti di non-coreferenza. Si argomenta in favore dell’approccio linguistico formale basato su strutture gerarchiche e contro alternative basate su vaghe nozioni di “generalizzazione analogica” e/o che impiegano il semplice ordine lineare. Nella parte finale si affronta il tema dell’invarianza e della variazione cross-linguistica degli effetti di non-coreferenza. Parole chiave: Conoscenza linguistica; Proprietà morfosintattiche; Computazioni inconsce; Coreferenzialità; Rappresentazioni linguistiche. (shrink)

On countable structures computability is usually introduced via numberings. For uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations and the infinitary normed limit operator computable. This characterizes the real numbers in terms of (...) the theory of effective algebras or computable structures, and is reflected by observations made in real number computer arithmetic. Demanding computability of the normed limit operator turns out to be essential: the basic operations without the normed limit operator can be made computable by more than one class of representations. We also give further evidence for the well-known non-appropriateness of the representation to some base b by proving that strictly less functions are computable with respect to these representations than with respect to a standard representation of the real numbers. Furthermore we consider basic constructions of representations and the countable substructure consisting of the computable elements of a represented, possibly uncountable structure. For countable structures we compare effectivity with respect to a numbering and effectivity with respect to a representation. Special attention is paid to the countable structure of the computable real numbers. (shrink)

Functional near-infrared spectroscopy has attracted increasing attention in the field of brain–computer interfaces owing to their advantages such as non-invasiveness, user safety, affordability, and portability. However, fNIRS signals are highly subject-specific and have low test-retest reliability. Therefore, individual calibration sessions need to be employed before each use of fNIRS-based BCI to achieve a sufficiently high performance for practical BCI applications. In this study, we propose a novel deep convolutional neural network -based approach for implementing a subject-independent fNIRS-based BCI. A total (...) of 18 participants performed the fNIRS-based BCI experiments, where the main goal of the experiments was to distinguish a mental arithmetic task from an idle state task. Leave-one-subject-out cross-validation was employed to evaluate the average classification accuracy of the proposed subject-independent fNIRS-based BCI. As a result, the average classification accuracy of the proposed method was reported to be 71.20 ± 8.74%, which was higher than the threshold accuracy for effective BCI communication as well as that obtained using conventional shrinkage linear discriminant analysis. To achieve a classification accuracy comparable to that of the proposed subject-independent fNIRS-based BCI, 24 training trials were necessary for the traditional subject-dependent fNIRS-based BCI. It is expected that our CNN-based approach would reduce the necessity of long-term individual calibration sessions, thereby enhancing the practicality of fNIRS-based BCIs significantly. (shrink)

This study evaluated the feasibility of using occipitoparietal alpha activity to drive target/non-target classification in a brain-computer interface for communication. EEG data were collected from 12 participants who completed BCI Rapid Serial Visual Presentation calibrations at two different presentation rates: 1 and 4 Hz. Attention-related changes in posterior alpha activity were compared to two event-related potentials : N200 and P300. Machine learning approaches evaluated target/non-target classification accuracy using alpha activity. Results indicated significant alpha attenuation following target letters at both 1 (...) and 4 Hz presentation rates, though this effect was significantly reduced in the 4 Hz condition. Target-related alpha attenuation was not correlated with coincident N200 or P300 target effects. Classification using posterior alpha activity was above chance and benefitted from individualized tuning procedures. These findings suggest that target-related posterior alpha attenuation is detectable in a BCI RSVP calibration and that this signal could be leveraged in machine learning algorithms used for RSVP or comparable attention-based BCI paradigms. (shrink)

The property of admissibility of representations plays an important role in Type–2 Theory of Effectivity . TTE defines computability on sets with continuum cardinality via representations. Admissibility is known to be indispensable for guaranteeing reasonable effectivity properties of the used representations.The question arises whether every function that is computable with respect to arbritrary representations is also computable with respect to closely related admissible ones. We define three operators which transform representations into admissible ones in such a way that relative computability (...) of functions is preserved. Thus the use of admissible representations rather than of non–admissible ones does not decrease the class of relatively computable functions. (shrink)

BackgroundType-Token Ratio, given its relatively simple hand computation, is one of the few LSA measures calculated by clinicians in everyday practice. However, it has significant well-documented shortcomings; these include instability as a function of sample size, and absence of clear developmental profiles over early childhood. A variety of alternative measures of lexical diversity have been proposed; some, such as Number of Different Words/100 can also be computed by hand. However, others, such as Vocabulary Diversity and the Moving Average Type Token (...) Ratio rely on complex resampling algorithms that cannot be conducted by hand. To date, no large-scale study of all four measures has evaluated how well any capture typical developmental trends over early childhood, or whether any reliably distinguish typical from atypical profiles of expressive child language ability.Materials and MethodsWe conducted linear and non-linear regression analyses for TTR, NDW, VocD, and MATTR scores for samples taken from 946 corpora from typically developing preschool children, engaged in adult-child toy play, from the Child Language Data Exchange System. These were contrasted with 504 samples from children known to have delayed expressive language skills. We also conducted a separate sub-analysis which examined possible contextual effects of sampling environment on lexical diversity.ResultsOnly VocD showed significantly different mean scores between the typically -developing children and delayed developing children group. Using TTR would actually misdiagnose typical children and miss children with known language impairment. However, computation of VocD as a function of toy interactions was significant and emerges as a further caution in use of lexical diversity as a valid proxy index of children’s expressive vocabulary skill.DiscussionThis large scale statistical comparison of computer-implemented algorithms for expressive lexical profiles in young children with traditional, hand-calculated measures showed that only VocD met criteria for evidence-based use in LSA. However, VocD was impacted by sample elicitation context, suggesting that non-linguistic factors, such as engagement with elicitation props, contaminate estimates of spoken lexical skill in young children. Implications and suggested directions are discussed. (shrink)

ArgumentThis paper is the first part of a two-part examination of computer modeling practice and philosophy. It discusses electrical engineer Jay Forrester's work on Industrial Dynamics, later called System Dynamics. Forrester developed Industrial Dynamics after being recruited to the newly-established School of Industrial Management at the Massachusetts Institute of Technology (MIT), which had been seeking a novel pedagogical program for management for five years before Forrester's arrival. We argue that Industrial Dynamics should be regarded in light of this institutional context. (...) Unlike economics, as well as operations research and management science (twin fields which were also gaining traction at that time), Industrial Dynamics was not meant to be applied by mathematicians and technical specialists in consultation with managers, but by managers themselves. This concern shifted the emphasis in modeling from the specialist act of analysis of a crucial problem to the managerial act of choosing which problems were crucial and developing effective policies around them. (shrink)

Espousing non-reductive physicalism, how do we pick out the specific relevant physical notion(s) from physical facts, specifically in relation to phenomenal experience? Beginning with a historical review of Gilbert Ryle’s behaviorism and moving through Hilary Putnam’s machine-state functionalism and Wilfrid Sellars’ inferential framework, up to more contemporaneous computationalist- and cognitivist-functionalism (Gualtiero Piccinini), we survey accounts of mentality that countenance the emergence of mental states vide input- and output-scheme. Ultimately arriving at the conclusion that functionalism cannot account for problems such as (...) no-cognition reports, we see any robust defense of physicalism must appeal to other principles. Thus we move on to the question of emergence, not as it pertains to the hard(er) problem, but to the matter of conceptual externalization of mental properties from physical properties. Accordingly, we navigate Karen Bennett’s compatibilist solution to the exclusion argument against mental causation for the non-reductive physicalist position, according to which the physical effects of mental cases are not overdetermined, demonstrating that this backfires by offering a path for the mind-body interactionist Dualist to claim causal closure by appealing to this same schema. We conclude with a series of conceptual musings regarding rationality which take into account our challenges and findings, querying about whether phenomenal consciousness is a fundamentally private, or socially configured, notion. (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)

We prove two embedding and extension theorems in the context of the constructive theory of metric spaces. The first states that Cantor space embeds in any inhabited complete separable metric space (CSM) without isolated points, X, in such a way that every sequentially continuous function from Cantor space to ℤ extends to a sequentially continuous function from X to ℝ. The second asserts an analogous property for Baire space relative to any inhabited locally non‐compact CSM. Both results rely on having (...) careful constructive formulations of the concepts involved.As a first application, we derive new relationships between “continuity principles” asserting that all functions between specified metric spaces are pointwise continuous. In particular, we give conditions that imply the failure of the continuity principle “all functions from X to ℝ are continuous”, when X is an inhabited CSM without isolated points, and when X is an inhabited locally non‐compact CSM. One situation in which the latter case applies is in models based on “domain realizability”, in which the failure of the continuity principle for any inhabited locally non‐compact CSM, X, generalizes a result previously obtained by Escardó and Streicher in the special case X = C[0, 1].As a second application, we show that, when the notion of inhabited complete separable metric space without isolated points is interpreted in a recursion‐theoretic setting, then, for any such space X, there exists a Banach‐Mazur computable function from X to the computable real numbers that is not Markov computable. This generalizes a result obtained by Hertling in the special case that X is the space of computable real numbers. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)