I compare several types of knowledge-based and knowledge-poor approaches to anaphora and ellipsis resolution. The former are able to capture fine-grained distinctions that depend on lexical meaning and real world knowledge, but they are generally not robust. The latter show considerable promise for yielding wide coverage systems. However, they consistently miss a small but significant subset of cases that are not accessible to rough-grained techniques of intepretation. I propose a sequenced model which first applies the most computationally efficient and inexpensive (...) methods to resolution and then progresses successively to more costly techniques to deal with cases not handled by previous modules. Confidence measures evaluate the judgements of each component in order to determine which instances of anaphora or ellipsis are to be passed on to the next, more fine-grained subsystem. (shrink)

We report the results of an experiment in which human subjects were trained to perform a perceptual matching task. Subjects were asked to manipulate comparison objects until they matched target objects using the fewest manipulations possible. An unusual feature of the experimental task is that efficient performance requires an understanding of the hidden or latent causal structure governing the relationships between actions and perceptual outcomes. We use two benchmarks to evaluate the quality of subjects’ learning. One benchmark is based on (...) optimal performance as calculated by a dynamic programming procedure. The other is based on an adaptive computational agent that uses a reinforcement-learning method known as Q-learning to learn to perform the task. Our analyses suggest that subjects were successful learners. In particular, they learned to perform the perceptual matching task in a near-optimal manner (i.e., using a small number of manipulations) at the end of training. Subjects were able to achieve near-optimal performance because they learned, at least partially, the causal structure underlying the task. In addition, subjects’ performances were broadly consistent with those of model-based reinforcement-learning agents that built and used internal models of how their actions influenced the external environment. We hypothesize that people will achieve near-optimal performances on tasks requiring sequences of action—especially sensorimotor tasks with underlying latent causal structures—when they can detect the effects of their actions on the environment, and when they can represent and reason about these effects using an internal mental model. (shrink)

As is well known the derivative of a computable and C1 function may not be computable. For a computable and C∞ function f, the sequence {f} of its derivatives may fail to be computable as a sequence, even though its derivative of any order is computable. In this paper we present a necessary and sufficient condition for the sequence {f} of derivatives of a computable and C∞ function f to be computable. We also give a sharp regularity (...) condition on an initial computable function f which insures the computability of its derivative f′. (shrink)

We examine how degrees of computably enumerable equivalence relations under computable reduction break down into isomorphism classes. Two ceers are isomorphic if there is a computable permutation of ω which reduces one to the other. As a method of focusing on nontrivial differences in isomorphism classes, we give special attention to weakly precomplete ceers. For any degree, we consider the number of isomorphism types contained in the degree and the number of isomorphism types of weakly precomplete ceers contained in the (...) degree. We show that the number of isomorphism types must be 1 or ω, and it is 1 if and only if the ceer is self-full and has no computable classes. On the other hand, we show that the number of isomorphism types of weakly precomplete ceers contained in the degree can be any member of $[0,\omega ]$. In fact, for any $n \in [0,\omega ]$, there is a degree d and weakly precomplete ceers ${E_1}, \ldots,{E_n}$ in d so that any ceer R in d is isomorphic to ${E_i} \oplus D$ for some $i \le n$ and D a ceer with domain either finite or ω comprised of finitely many computable classes. Thus, up to a trivial equivalence, the degree d splits into exactly n classes.We conclude by answering some lingering open questions from the literature: Gao and Gerdes [11] define the collection of essentially FC ceers to be those which are reducible to a ceer all of whose classes are finite. They show that the index set of essentially FC ceers is ${\rm{\Pi }}_3^0$-hard, though the definition is ${\rm{\Sigma }}_4^0$. We close the gap by showing that the index set is ${\rm{\Sigma }}_4^0$-complete. They also use index sets to show that there is a ceer all of whose classes are computable, but which is not essentially FC, and they ask for an explicit construction, which we provide.Andrews and Sorbi [4] examined strong minimal covers of downwards-closed sets of degrees of ceers. We show that if $\left$ is a uniform c.e. sequence of non universal ceers, then $\left\{ {{ \oplus _{i \le j}}{E_i}|j \in \omega } \right\}$ has infinitely many incomparable strong minimal covers, which we use to answer some open questions from [4].Lastly, we show that there exists an infinite antichain of weakly precomplete ceers. (shrink)

In a Common Law system, legal practitioners need frequent access to prior case documents that discuss relevant legal issues. Case documents are generally very lengthy, containing complex sentence structures, and reading them fully is a strenuous task even for legal practitioners. Having a concise overview of these documents can relieve legal practitioners from the task of reading the complete case statements. Legal catchphrases are (multi-word) phrases that provide a concise overview of the contents of a case document, and automated generation (...) of catchphrases is a challenging problem in legal analytics. In this paper, we propose a novel supervised neural sequence tagging model for the extraction of catchphrases from legal case documents. Specifically, we show that incorporating document-specific information along with a sequence tagging model can enhance the performance of catchphrase extraction. We perform experiments over a set of Indian Supreme Court case documents, for which the gold-standard catchphrases (annotated by legal practitioners) are obtained from a popular legal information system. The performance of our proposed method is compared with that of several existing supervised and unsupervised methods, and our proposed method is empirically shown to be superior to all baselines. (shrink)

Suppose that 〈xk〉k∈ℕ is a countable sequence of real numbers. Working in the usual subsystems for reverse mathematics, RCA0 suffices to prove the existence of a sequence of reals 〈uk〉k∈ℕ such that for each k, uk is the minimum of {x0, x1, …, xk}. However, if we wish to prove the existence of a sequence of integer indices of minima of initial segments of 〈xk〉k∈ℕ, the stronger subsystem WKL0 is required. Following the presentation of these reverse mathematics (...) results, we will derive computability theoretic corollaries and use them to illustrate a distinction between computable analysis and constructive analysis. (shrink)

One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. J. (...) Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Ω-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Lof test. (shrink)

This article proposes using structural description for graphical objects to solve an urgent task of trajectory analysis. A range of modern trajectory analysis approaches were analyzed and the best that is based on Graph Convolutional Neural Networks and Suffix Tree Clustering algorithm was chosen. Descripted ways to reduce computational sources for this neural network approach. This neural network was adapted to analyze structural description and advantages of this approach are shown.

This article proposes a new bi-directional way of understanding the convergence of biology and computing. It argues for a reciprocal interaction in which biology and computing have shaped and are currently reshaping each other. In so doing, we qualify both the view of a natural marriage and of a digital shaping of biology, which are common in the literature written by scientists, STS, and communication scholars. The DNA database is at the center of this interaction. We argue that DNA databases (...) are spaces of convergence for computing and biology that change in form, meaning, and function from the 1960s to the 2000s. The first part of the article shows how, in the 1980s, DNA sequencing shifted from passively incorporating computers to be increasingly modeled in digital coding and decoding. Information retrieval algorithms, reciprocally, were altered according to the peculiarities of DNA in the first sequence-storage databases. The second part of the article investigates the impact of these reciprocal interactions and globalization on the organization of research centers, ways of conducting big science, and scientific values. Through convergence and new technologies such as data mining, biology and computing were transformed technologically, institutionally, and culturally into a new bio-data enterprise called genomics. (shrink)

In the context of Kolmogorov's algorithmic approach to the foundations of probability, Martin‐Löf defined the concept of an individual random sequence using the concept of a constructive measure 1 set. Alternate characterizations use constructive martingales and measures of impossibility. We prove a direct conversion of a constructive martingale into a measure of impossibility and vice versa such that their success sets, for a suitably defined class of computable probability measures, are equal. The direct conversion is then generalized to give (...) a new characterization of constructive dimensions, in particular, the constructive Hausdorff dimension, the constructive packing dimension, and their generalizations, the constructive scaled dimension and the constructive scaled strong dimension (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

We consider two classical computability notions for functions mapping all computable real numbers to computable real numbers. It is clear that any function that is computable in the sense of Markov, i.e., computable with respect to a standard Gödel numbering of the computable real numbers, is computable in the sense of Banach and Mazur, i.e., it maps any computable sequence of real numbers to a computable sequence of real numbers. We show that the converse is not true. This (...) solves a long-standing open problem posed by Kushner. (shrink)

In this paper, we analyzed the periodicity of discrete Logistic and Tent sequences with different computational precision in detail. Further, we found that the process of iterations of the Logistic and Tent mapping is composed of transient and periodic stages. Surprisingly, for the different initial iterative values, we first discovered that all periodic stages have the same periodic limit cycles. This phenomenon has seriously affected the security of chaotic cipher. To solve this problem, we designed a novel discrete chaotic (...) sequence generator based on m-sequence and discrete chaotic mapping. The experimental results indicated that the chaotic sequence generator can generate pseudorandom chaotic sequences with large periodicity and good performance under the condition of limited computational precision. (shrink)

Computational models of memory are often expressed as hierarchic sequence models, but the hierarchies in these models are typically fairly shallow, reflecting the tendency for memories of superordinate sequence states to become increasingly conflated. This article describes a broad-coverage probabilistic sentence processing model that uses a variant of a left-corner parsing strategy to flatten sentence processing operations in parsing into a similarly shallow hierarchy of learned sequences. The main result of this article is that a broad-coverage model (...) with constraints on hierarchy depth can process large newspaper corpora with the same accuracy as a state-of-the-art parser not defined in terms of sequential working memory operations. (shrink)

This thesis is devoted to the exploration of the complexity of some mathematical problems using the framework of computable analysis and descriptive set theory. We will especially focus on Weihrauch reducibility as a means to compare the uniform computational strength of problems. After a short introduction of the relevant background notions, we investigate the uniform computational content of problems arising from theorems that lie at the higher levels of the reverse mathematics hierarchy.We first analyze the strength of the (...) open and clopen Ramsey theorems. Since there is not a canonical way to phrase these theorems as multi-valued functions, we identify eight different multi-valued functions and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility.We then discuss some new operators on multi-valued functions and study their algebraic properties and the relations with other previously studied operators on problems. In particular, we study the first-order part and the deterministic part of a problem f, capturing the Weihrauch degree of the strongest multi-valued problem that is reducible to f and that, respectively, has codomain $\mathbb {N}$ or is single-valued.These notions proved to be extremely useful when exploring the Weihrauch degree of the problem $\mathsf {DS}$ of computing descending sequences in ill-founded linear orders. They allow us to show that $\mathsf {DS}$, and the Weihrauch equivalent problem $\mathsf {BS}$ of finding bad sequences through non-well quasi-orders, while being very “hard” to solve, are rather weak in terms of uniform computational strength. We then generalize $\mathsf {DS}$ and $\mathsf {BS}$ by considering $\boldsymbol {\Gamma }$ -presented orders, where $\boldsymbol {\Gamma }$ is a Borel pointclass or $\boldsymbol {\Delta }^1_1$, $\boldsymbol {\Sigma }^1_1$, $\boldsymbol {\Pi }^1_1$. We study the obtained $\mathsf {DS}$ -hierarchy and $\mathsf {BS}$ -hierarchy of problems in comparison with the Baire hierarchy and show that they do not collapse at any finite level.Finally, we work in the context of geometric measure theory and we focus on the characterization, from the point of view of descriptive set theory, of some conditions involving the notions of Hausdorff/Fourier dimension and Salem sets. We first work in the hyperspace $\mathbf {K}$ of compact subsets of $[0,1]$ and show that the closed Salem sets form a $\boldsymbol {\Pi }^0_3$ -complete family. This is done by characterizing the complexity of the family of sets having sufficiently large Hausdorff or Fourier dimension. We also show that the complexity does not change if we increase the dimension of the ambient space and work in $\mathbf {K}$. We also generalize the results by relaxing the compactness of the ambient space and show that the closed Salem sets are still $\boldsymbol {\Pi }^0_3$ -complete when we endow $\mathbf {F}$ with the Fell topology. A similar result holds also for the Vietoris topology.We conclude by analyzing the same notions from the point of view of effective descriptive set theory and Type-2 Theory of Effectivity, and show that the complexities remain the same also in the lightface case. In particular, we show that the family of all the closed Salem sets is $\Pi ^0_3$ -complete. We furthermore characterize the Weihrauch degree of the functions computing Hausdorff and Fourier dimension of closed sets.prepared by Manlio Valenti.E-mail:[email protected]. (shrink)

In the propositional modal treatment of two-variable first-order logic equality is modelled by a ‘diagonal’ constant, interpreted in square products of universal frames as the identity relation. Here we study the decision problem of products of two arbitrary modal logics equipped with such a diagonal. As the presence or absence of equality in two-variable first-order logic does not influence the complexity of its satisfiability problem, one might expect that adding a diagonal to product logics in general is similarly harmless. We (...) show that this is far from being the case, and there can be quite a big jump in complexity, even from decidable to the highly undecidable. Our undecidable logics can also be viewed as new fragments of first-order logic where adding equality changes a decidable fragment to undecidable. We prove our results by a novel application of counter machine problems. While our formalism apparently cannot force reliable counter machine computations directly, the presence of a unique diagonal in the models makes it possible to encode both lossy and insertion-error computations, for the same sequence of instructions. We show that, given such a pair of faulty computations, it is then possible to reconstruct a reliable run from them. (shrink)

The detection and categorization of animate motions is a crucial task underlying social interaction and perceptual decision making. Neural representations of perceived animate objects are partially located in the primate cortical region STS, which is a region that receives convergent input from intermediate-level form and motion representations. Populations of STS cells exist which are selectively responsive to specific animated motion sequences, such as walkers. It is still unclear how and to what extent form and motion information contribute to the generation (...) of such representations and what kind of mechanisms are involved in the learning processes. The article develops a cortical model architecture for the unsupervised learning of animated motion sequence representations. We demonstrate how the model automatically selects significant motion patterns as well as meaningful static form prototypes characterized by a high degree of articulation. Such key poses are selectively reinforced during learning through a cross talk between the motion and form processing streams. Furthermore, we show how sequence-selective representations are learned in STS by fusing static form and motion input from the segregated bottom-up driving input streams. Cells in STS, in turn, feed their activities recurrently to their input sites along top-down signal pathways. We show how such learned feedback connections enable predictions about future input as anticipation generated by sequence-selective STS cells. Network simulations demonstrate the computational capacity of the proposed model by reproducing several experimental findings from neurosciences and by accounting for recent behavioral data. (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)

Collecting, comparing, and computing molecular sequences are among the most prevalent practices in contemporary biological research. They represent a specific way of producing knowledge. This paper explores the historical development of these practices, focusing on the work of Margaret O. Dayhoff, Richard V. Eck, and Robert S. Ledley, who produced the first computer-based collection of protein sequences, published in book format in 1965 as the Atlas of Protein Sequence and Structure. While these practices are generally associated with the rise (...) of molecular evolution in the 1960s, this paper shows that they grew out of research agendas from the previous decade, including the biochemical investigation of the relations between the structures and function of proteins and the theoretical attempt to decipher the genetic code. It also shows how computers became essential for the handling and analysis of sequence data. Finally, this paper reflects on the relationships between experimenting and collecting as two distinct “ways of knowing” that were essential for the transformation of the life sciences in the twentieth century. (shrink)

Suppose a computer prints out the following little "poem": The shooting of the hunters she heardBut to pity it moved her not. What can we say about the meaning of this "poem"? We can say that it is ambiguous. It could mean: She heard the hunters shooting at animals, people, etc., but she had no pity for the victims. . . . She heard the hunters being shot but did not pity them. . . . She heard the hunters shooting (...) at someone or something and she heard the hunters being shot but did not pity either. An author could use the above word sequence to convey either , , or . But since we cannot treat the text produced by the computer as anyone's use of the words in question, it would not make sense to decide among its linguistically possible readings, just as it would not make sense to choose among the linguistically possible readings of an ambiguous sentence if it is considered in abstraction from its use by a speaker on a particular occasion. For example, it would not make sense to say of the sentence "He saw the man carrying the suitcase" that it just means "He saw the man who is carrying the suitcase" if we know that and in which what ways the sentence is ambiguous. If someone did say this, we would be inclined to think either that he does not know that the sentence is ambiguous or that he is talking not about the sentence but about an utterance of that sentence by a speaker on some occasion. Hence all we can do in interpreting the computer "poem" is to specify the set of its linguistically possible readings, namely, {, , }. But it would not make sense to select , for example, and say, "That is what the computer poem means, not , nor ." P. D. Juhl is an assistant professor of German at Princeton University. The present essay, in a different form, will appear in his forthcoming book, The Nature of Literary Interpretation. See also: "Against Theory" by Steven Knapp and Walter Benn Michaels in Vol. 8, No. 4. (shrink)

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

The computability of reals was introduced by Alan Turing [20] by means of decimal representations. But the equivalent notion can also be introduced accordingly if the binary expansion, Dedekind cut or Cauchy sequence representations are considered instead. In other words, the computability of reals is independent of their representations. However, as it is shown by Specker [19] and Ko [9], the primitive recursiveness and polynomial time computability of the reals do depend on the representation. In this paper, we explore (...) how the weak computability of reals depends on the representation. To this end, we introduce three notions of weak computability in a way similar to the Ershov's hierarchy of Δ02-sets of natural numbers based on the binary expansion, Dedekind cut and Cauchy sequence, respectively. This leads to a series of classes of reals with different levels of computability. We investigate systematically questions as on which level these notions are equivalent. We also compare them with other known classes of reals like c. e. and d-c. e. reals. (shrink)

Recent advances in philosophical thinking about consciousness, such as cognitive phenomenology and mereological analysis, provide a framework that facilitates using computational models to explore issues surrounding the nature of consciousness. Here we suggest that, in particular, studying the computational mechanisms of working memory and its cognitive control is highly likely to identify computational correlates of consciousness and thereby lead to a deeper understanding of the nature of consciousness. We describe our recent computational models of human working (...) memory and propose that three computational correlates of consciousness follow from the results of this work: itinerant attractor sequences, top-down gating, and very fast weight changes. Our current investigation is focused on evaluating whether these three correlates are sufficient to create more complex working memory models that encompass compositionality and basic causal inference. We conclude that computational models of working memory are likely to be a fruitful approach to advancing our understanding of consciousness in general and in determining the long-term potential for development of an artificial consciousness specifically. (shrink)

It is perhaps in the functioning of the brain that we can make contextual information most prominent. Indeed, while von Neumann and others invented computers with mimicking the brain in mind, the brain does not appear to behave as a Turing Machine. Neither is it a mechanical automaton. There is no “ghost in the machine.” However, nobody would doubt that the brain manages information, and in a very efficient way. To my view, this is a strong indication that the information (...) we describe when considering messages is a tiny part of what information is. Because we use language, built on the exchange of sequences of symbols, exactly as programs are exchanged in computers, linguists often saw the brain as a Turing Machine. But language is deeply associated to meaning, so that beside grammatical syntactic structures, there may exist a variety of superimposed contexts which transmit information mediated by channels that are not those usually considered. (shrink)

The problem of intentional identity, as originally offered by Peter Geach, says that there can be an anaphoric link between an indefinite term and a pronoun across a sentential boundary and across propositional attitude contexts, where the actual existence of an individual for the indefinite term is not presupposed. In this paper, a semantic resolution to this elusive puzzle is suggested, based on a new quantified intensional logic and game-theoretic semantics (GTS) of imperfect information. This constellation leads to an expressive (...) intensional language with a property of informational independence, argued to produce a purely semantic explication to intentional identity statements. One consequence is that various extra-logical and pragmatic factors become of secondary concern; it is possible to solve the puzzle by logico-semantic methods, albeit somewhat radically renewed ones. (shrink)

Cells are cognitive entities possessing great computational power. DNA serves as a multivalent information storage medium for these computations at various time scales. Information is stored in sequences, epigenetic modifications, and rapidly changing nucleoprotein complexes. Because DNA must operate through complexes formed with other molecules in the cell, genome functions are inherently interactive and involve two-way communication with various cellular compartments. Both coding sequences and repetitive sequences contribute to the hierarchical systemic organization of the genome. By virtue of nucleoprotein (...) complexes, epigenetic modifications, and natural genetic engineering activities, the genome can serve as a read-write storage system. An interactive informatic conceptualization of the genome allows us to understand the functional importance of DNA that does not code for protein or RNA structure, clarifies the essential multidirectional and systemic nature of genomic information transfer, and emphasizes the need to investigate how cellular computation operates in reproduction and evolution. (shrink)

This paper continues our study of computable point-free topological spaces and the metamathematical points in them. For us, a point is the intersection of a sequence of basic open sets with compact and nested closures. We call such a sequence a sharp filter. A function fF from points to points is generated by a function F from basic open sets to basic open sets such that sharp filters map to sharp filters. We restrict our study to functions that (...) have at least all computable points in their domains.We follow Turing's approach in stating that a point is computable if it is the limit of a computable sharp filter; we then define the Turing degree Deg of a general point x in an analogous way. Because of the vagaries of the definition, a result of J. Miller applies and we note that not all points in all our spaces have Turing degrees; but we also show a certain class of points do. We further show that in ℝn all points have Turing degrees and that these degrees are the same as the classical Turing degrees of points defined by other researchers.We also prove the following: For a point x that has a Turing degree and lies either on a computable tree T or in the domain of a computable function fF, there is a sharp filter on T or in dom converging to x and with the same Turing degree as x. Furthermore, all possible Turing degrees occur among the degrees of such points for a given computable function fF or a complete, computable, binary tree T. For each x ∈ dom for which x and fF have Turing degrees, Deg) ≤ Deg. Finally, the Turing degrees of the sharp filters convergent to a given x are closed upward in the partial order of all Turing degrees. (shrink)

Basic Predicate Logic, BQC, is a proper subsystem of Intuitionistic Predicate Logic, IQC. For every formula in the language {, , , , , , }, we associate two sequences of formulas 0,1,... and 0,1,... in the same language. We prove that for every sequent , there are natural numbers m, n, such that IQC , iff BQC n m. Some applications of this translation are mentioned.

What do people learn when they do not know that they are learning? Until recently, all of the work in the area of implicit learning focused on empirical questions and methods. In this book, Axel Cleeremans explores unintentional learning from an information-processing perspective. He introduces a theoretical framework that unifies existing data and models on implicit learning, along with a detailed computational model of human performance in sequence-learning situations.

Unlike the standard Quantum Computational Logic, where the carrier of information is conventionally assumed to be only the last qubit over a sequence of many qubits, here we propose an extended version of the QCL where the number and the position of the target qubits are arbitrary.

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)

This study is concerned with processes for discovering new theories in science. It considers a computational approach to scientific discovery, as applied to the discovery of theories in cognitive science. The approach combines two ideas. First, a process-based scientific theory can be represented as a computer program. Second, an evolutionary computational method, genetic programming, allows computer programs to be improved through a process of computational trialand-error. Putting these two ideas together leads to a system that can automatically (...) generate and improve scientific theories. The application of this method to the discovery of theories in cognitive science is examined. Theories are built up from primitive operators. These are contained in a theory language that defines the space of possible theories. An example of a theory generated by this method is described. These results support the idea that scientific discovery can be achieved through a heuristic search process, even for theories involving a sequence of steps. However, this computational approach to scientific discovery does not eliminate the need for human input. Human judgment is needed to make reasonable prior assumptions about the characteristics of operators used in the theory generation process, and to interpret and provide context for the computationally generated theories. (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)

The accurate annotation of an unknown protein sequence depends on extant data of template sequences. This could be empirical or sets of reference sequences, and provides an exhaustive pool of probable functions. Individual methods of predicting dominant function possess shortcomings such as varying degrees of inter-sequence redundancy, arbitrary domain inclusion thresholds, heterogeneous parameterization protocols, and ill-conditioned input channels. Here, I present a rigorous theoretical derivation of various steps of a generic algorithm that integrates and utilizes several statistical methods (...) to predict the dominant function in unknown protein sequences. The accompanying mathematical proofs, interval definitions, analysis, and numerical computations presented are meant to offer insights not only into the specificity and accuracy of predictions, but also provide details of the operatic mechanisms involved in the integration and its ensuing rigor. The algorithm uses numerically modified raw hidden markov model scores of well defined sets of training sequences and clusters them on the basis of known function. The results are then fed into an artificial neural network, the predictions of which can be refined using the available data. This pipeline is trained recursively and can be used to discern the dominant principal function, and thereby, annotate an unknown protein sequence. Whilst, the approach is complex, the specificity of the final predictions can benefit laboratory workers design their experiments with greater confidence. -/- . (shrink)

Various algorithms have been proposed for learning (partial) genetic regulatory networks through systematic measurements of differential expression in wild type versus strains in which expression of specific genes has been suppressed or enhanced, as well as for determining the most informative next experiment in a sequence. While the behavior of these algorithms has been investigated for toy examples, the full computational complexity of the problem has not received sufficient attention. We show that finding the true regulatory network requires (...) (in the worst-case) exponentially many experiments (in the number of genes). Perhaps more importantly, we provide an algorithm for determining the set of regulatory networks consistent with the observed data. We then show that this algorithm is infeasible for realistic data (specifically, nine genes and ten experiments). This infeasibility is not due to an algorithmic flaw, but rather to the fact that there are far too many networks consistent with the data (10 18 in the provided example). We conclude that gene perturbation experiments are useful in confirming regulatory network models discovered by other techniques, but not a feasible search strategy. (shrink)

This study investigates the procedural learning, retention, and reactivation of temporal sensorimotor sequences in children with and without developmental coordination disorder. Twenty typically-developing children and 12 children with DCD took part in this study. The children were required to tap on a keyboard, synchronizing with auditory or visual stimuli presented as an isochronous temporal sequence, and practice non-isochronous temporal sequences to memorize them. Immediate and delayed retention of the audio-motor and visuo-motor non-isochronous sequences were tested by removing auditory or (...) visual stimuli immediately after practice and after a delay of 2 h. A reactivation test involved reintroducing the auditory and visual stimuli after the delayed recall. Data were computed via circular analyses to obtain asynchrony, the stability of synchronization and errors. Firstly, an overall deficit in synchronization with both auditory and visual isochronous stimuli was observed in DCD children compared to TD children. During practice, further improvements were found for the audio-motor non-isochronous sequence compared to the visuo-motor non-isochronous sequence in both TD children and children with DCD. However, a drastic increase in errors occurred in children with DCD during immediate retention as soon as the auditory stimuli were removed. Reintroducing auditory stimuli decreased errors in the audio-motor sequence for children with DCD. Such changes were not seen for the visuo-motor non-isochronous sequence, which was equally learned, retained and reactivated in DCD and TD children. All these results suggest that TD children benefit from both auditory and visual stimuli to memorize the sequence, whereas children with DCD seem to present a deficit in integrating an audio-motor sequence in their memory. The immediate effect of reactivation suggests a specific dependency on auditory information in DCD. Contrary to the audio-motor sequence, the visuo-motor sequence was both learned and retained in children with DCD. This suggests that visual stimuli could be the best information for memorizing a temporal sequence in DCD. All these results are discussed in terms of a specific audio-motor coupling deficit in DCD. (shrink)

A new approach for a uniform classification of the computably approximable real numbers is introduced. This is an important class of reals, consisting of the limits of computable sequences of rationals, and it coincides with the 0'-computable reals. Unlike some of the existing approaches, this applies uniformly to all reals in this class: to each computably approximable real x we assign a degree structure, the structure of all possible ways available to approximate x. So the main criterion for such classification (...) is the variety of the effective ways we have to approximate a real number. We exhibit extreme cases of such approximation structures and prove a number of related results. (shrink)

We study the uniform computational content of different versions of the Baire category theorem in the Weihrauch lattice. The Baire category theorem can be seen as a pigeonhole principle that states that a complete metric space cannot be decomposed into countably many nowhere dense pieces. The Baire category theorem is an illuminating example of a theorem that can be used to demonstrate that one classical theorem can have several different computational interpretations. For one, we distinguish two different logical (...) versions of the theorem, where one can be seen as the contrapositive form of the other one. The first version aims to find an uncovered point in the space, given a sequence of nowhere dense closed sets. The second version aims to find the index of a closed set that is somewhere dense, given a sequence of closed sets that cover the space. Even though the two statements behind these versions are equivalent to each other in classical logic, they are not equivalent in intuitionistic logic, and likewise, they exhibit different computational behavior in the Weihrauch lattice. Besides this logical distinction, we also consider different ways in which the sequence of closed sets is “given.” Essentially, we can distinguish between positive and negative information on closed sets. We discuss all four resulting versions of the Baire category theorem. Somewhat surprisingly, it turns out that the difference in providing the input information can also be expressed with the jump operation. Finally, we also relate the Baire category theorem to notions of genericity and computably comeager sets. (shrink)

A basic function of cognition is to detect regularities in sensory input to facilitate the prediction and recognition of future events. It has been proposed that these implicit expectations arise from an internal predictive coding model, based on knowledge acquired through processes such as statistical learning, but it is unclear how different types of statistical information affect listeners’ memory for auditory stimuli. We used a combination of behavioral and computational methods to investigate memory for non-linguistic auditory sequences. Participants repeatedly (...) heard tone sequences varying systematically in their information-theoretic properties. Expectedness ratings of tones were collected during three listening sessions, and a recognition memory test was given after each session. Information-theoretic measures of sequential predictability significantly influenced listeners’ expectedness ratings, and variations in these properties had a significant impact on memory performance. Predictable sequences yielded increasingly better memory performance with increasing exposure. Computational simulations using a probabilistic model of auditory expectation suggest that listeners dynamically formed a new, and increasingly accurate, implicit cognitive model of the information-theoretic structure of the sequences throughout the experimental session. (shrink)

The three‐dimensional structure of DNA depends subtly on its sequence, and this property is used by the proteins that regulate gene expression to locate their target sequences. Despite the large body of experimental data that has been accumulated on the relationship between sequence and DNA structure, we still do not fully understand the molecular basis for these properties, nor can we predict a three‐dimensional structure from a given sequence. We have been using computer modelling to tackle these (...) problems. Some of our results and the implications for understanding the biological role of key sequences are discussed here. (shrink)

In this paper, we argue for the centrality of prediction in the use of computational models in science. We focus on the consequences of the irreversibility of computational models and on the conditional or ceteris paribus, nature of the kinds of their predictions. By irreversibility, we mean the fact that computational models can generally arrive at the same state via many possible sequences of previous states. Thus, while in the natural world, it is generally assumed that physical (...) states have a unique history, representations of those states in a computational model will usually be compatible with more than one possible history in the model. We describe some of the challenges involved in prediction and retrodiction in computational models while arguing that prediction is an essential feature of non-arbitrary decision making. Furthermore, we contend that the non-predictive virtues of computational models are dependent to a significant degree on the predictive success of the models in question. (shrink)

The article discusses the possibilities of the formal analysis of the fine-art painting composition on the basis of the classical definitions of beauty and computational aesthetics’ approaches of the second half of the 20th century he authors define the problem and consider solutions for the formalization of aesthetic perception in the context of aesthetic text, i.e., as part of the fine arts composition – a formal sequence of signs simply ordered in accordance with the syntactic rules’ system. The (...) methodology of the research is defined by the general semiotics, distinguishing semantics, syntax, and pragmatics of a sign, by the aesthetic analysis’ methods, ranging according to the author’s message aesthetics, receptive aesthetics, and text aesthetics, as well as by the computational analysis methods connected with neural network means of defining the images’ symmetry. The article reveals preconditions for the emergence and also the current state of computational aesthetics as an interdisciplinary branch of knowledge. Analyzing the problem from the perspective of philosophy, aesthetics, semiotics, and technology, the authors draw attention to the need to improve the computational aesthetics methods. Firstly, the existing methods do not always enable to describe the fine-art object adequately. Secondly, there exists the so-called reduction of aesthetic assertion transforming it into the assertion concerning the object’s external characteristics. As a result, the authors assume that the increasing complexity of the current mathematical models and the experts’ subjective assessment support will allow to reach a compromise solution that enables the development of computational aesthetics as a branch of knowledge. Enhancement and development of the mathematical models, taking into account the rules of semiotics and subjectivism of the human perception, is the relevant objective of computational analysis of the aesthetic fine-arts text. The results of the present research supports the classic statement regarding the underivability of semantic and pragmatic propositions from syntax. The research concludes that relevant objectives are to find a correlation between, one the one hand, the axes and points of symmetry, deriving from the neural simulation, and, on the other hand, aesthetic effect, emerging from the perception of fine-art paintings. (shrink)

Much of the progress in the fields constituting cognitive science has been based upon the use of explicit information processing models, almost exclusively patterned after conventional serial computers. An extension of these ideas to massively parallel, connectionist models appears to offer a number of advantages. After a preliminary discussion, this paper introduces a general connectionist model and considers how it might be used in cognitive science. Among the issues addressed are: stability and noise‐sensitivity, distributed decision‐making, time and sequence problems, (...) and the representation of complex concepts. (shrink)

Expression of most genes is regulated by the interaction of multiple transcription factors with cis‐regulatory sequences. Many studies have focused on how changes in promoters and enhancers alter gene expression and phenotype. Recently, Hare et al., using elegant wet and computational approaches uncovered a series of enhancers driving the expression of the even‐skipped gene in scavenger flies (Sepsidae).1 Despite the strong sequence divergence between the enhancers in sepsids and drosophilids, they lead to remarkably similar patterns of gene expression (...) in transgenic Drosophila embryos. This can be explained by the existence of intra‐enhancer compensatory mutations and the presence of overlapping/near binding sites for activators and repressors. BioEssays 30:1052–1057, 2008. © 2008 Wiley Periodicals, Inc. (shrink)