Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out several examples. One motivation is to see whether some classes whose set of countable members is very complex become classifiable when we consider only (...) class='Hi'>computable members. We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. For real closed fields we show that the isomorphism problem is Δ1 1 complete (the maximum possible), and for others we show that it is of relatively low complexity. We show that the isomorphism problem for algebraically closed fields, Archimedean real closed fields, or vector spaces is Π0 3 complete. (shrink)

We establish that the isomorphism problem for the classes of computable nilpotent rings, distributive lattices, nilpotent groups, and nilpotent semigroups is \-complete, which is as complicated as possible. The method we use is based on uniform effective interpretations of computable binary relations into computable structures from the corresponding algebraic classes.

Let$ \le _c $be computable the reducibility on computably enumerable equivalence relations. We show that for every ceerRwith infinitely many equivalence classes, the index sets$\left\{ {i:R_i \le _c R} \right\}$,$\left\{ {i:R_i \ge _c R} \right\}$, and$\left\{ {i:R_i \equiv _c R} \right\}$are${\rm{\Sigma }}_3^0$complete, whereas in caseRhas only finitely many equivalence classes, we have that$\left\{ {i:R_i \le _c R} \right\}$is${\rm{\Pi }}_2^0$complete, and$\left\{ {i:R \ge _c R} \right\}$ is${\rm{\Sigma }}_2^0$complete. Next, solving an open problem from [1], we prove that the (...) index set of the effectively inseparable ceers is${\rm{\Pi }}_4^0$complete. Finally, we prove that the 1-reducibility preordering on c.e. sets is a${\rm{\Sigma }}_3^0$complete preordering relation, a fact that is used to show that the preordering relation$ \le _c $on ceers is a${\rm{\Sigma }}_3^0$complete preordering relation. (shrink)

The CMI Millennium “P vs NP Problem” can be resolved e.g. if one shows at least one counterexample to the "P = NP" conjecture. A certain class of problems being such counterexamples will be formulated. This implies the rejection of the hypothesis that "P = NP" for any conditions satisfying the formulation of the problem. Thus, the solution "P is different from NP" of the problem in general is proved. The class of counterexamples can be interpreted as any quantum (...) superposition of any finite set of quantum states. The Kochen-Specker theorem is involved. Any fundamentally random choice among a finite set of alternatives belong to "NP" but not to "P". The conjecture that the set complement of "P" to "NP" can be described by that kind of choice exhaustively is formulated. (shrink)

In the basic modal language and in the basic modal language with the added universal modality, first-order definability of all formulas over the class of all frames is shown. Also, it is shown that the problems of modal definability of first-order sentences over the class of all frames in the languages and are both PSPACE-complete.

Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parameterized problems that can be solved in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed (...) are considered, and it is shown that the class FPT of tractable parameterized problems has interesting and natural internal structure. (shrink)

When a professor from Middle Europe teaches Computer Ethics in the Middle East using a textbook from the US, cultural differences become apparent. A main challenge lies in avoiding cultural imperialism during teaching. In order to meet this challenge, personal portfolios have been used for course work. The course design as well as portfolio tasks are presented and experiences are discussed. Based on our experiences we recommend applying this approach to equally overcome effects of group dynamics in similar courses as (...) well as to bridge the generational gap that normally exists between students and professors. (shrink)

Examines some of the potential and some of the problems inherent in using computerized simulations in science and science studies classes by applying lessons from the epistemology of science. While computer simulations are useful pedagogical tools, they are not experiments and thus are of only limited utility as substitutes for actual laboratories. Contains 20 references. (Author/PVD).

Learning equivalence classes of acyclic models with latent and selection variables from multiple datasets with overlapping variables is discussed. The problem of inferring the presence of latent variables, their relation to the observables, and the relation among themselves, is considered. A different approach for identifying causal structures, one that results in much simpler equivalence classes, is provided. It is found that the computational cost is much higher than the procedure implemented, but if datasets are individually of modest dimensionality, (...) it might be doable in practice. From the point of view of search algorithms for optimizing structure, much of the machinery of combinatorial optimization could optimize the penalized composite likelihood score by enforcing constraints such that the independence models over different subsets of variables agree on the overlapping sets. (shrink)

The question of the relationship between ontology and theology, the main problem of the interpretation in volume 3, is also the guiding question of our last volume. The history of metaphysics is a history of the efforts towards an outlook on the world and life, which are about the meaning and connection of fundamental concepts: being, life, intellect, unity, truth, goodness. From these, the concept of divinity is derived. As in the previous volumes, a rich material of original texts and (...) interpretations is spread out. (shrink)

This article puts forward a novel class of Bézier smooth semi-supervised support vector machines(BS4VMs) for classification. As is well known, semi-supervised support vector machine is introduced for dealing with quantities of unlabeled data in the real world. Labeled data is utilized to train the algorithm and then adapting it to classify the unlabeled data. However, the objective semi-supervised function is not differentiable globally. It is required to endure heavy burden in solving two quadratic programming problems with inversion matrix operation. (...) To solve this problem, the interpolation Bézier functions for replacing the non-smooth term have been investigated. Firstly, the development of the novel BS4VMs classifier is introduced. Then, the non-linear model and convergence analysis are presented. To show how the BS4VMs can be practically implemented, experiments on synthetic and real data sets are offered. The theoretical analysis and experiments comparisons clearly illustrate the BS4VMs are superior to the proposed methods in both cross-validation classification accuracy and calculating time. (shrink)

An analogy between the evolution of organisms and some complex computational problems (cryptosystem cracking, determination of the shortest path in a graph) is considered. It is shown that in the absence of a priori information about possible species of organisms such a problem is complex (is rated in the class NP) and cannot be solved in a polynomial number of steps. This conclusion suggests the need for re-examination of evolution mechanisms. Ideas of a deterministic approach to the evolution are (...) discussed. (shrink)

Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples. We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable (...) classes from non-classifiable. In this paper, we calculate the degree of the isomorphism problem for Abelian p-groups of bounded Ulm length. The result is a sequence of classes whose isomorphism problems are cofinal in the hyperarithmetical hierarchy. In the process, new back-and-forth relations on such groups are calculated. (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)

This paper was motivated by the following two questions which arise in the theory of complexity for computation over ordered rings in the now famous computational model introduced by Blum, Shub and Smale: 1. is the answer to the question P = ?NP the same in every real-closed field?2. if P ≠ NP for , does there exist a problem of which is NP but neither P nor NP-complete ?Some unclassical complexity classes arise naturally in the study of these (...) questions. They are still open, but we could obtain unconditional results of independent interest.Michaux introduced/const complexity classes in an effort to attack question . We show that , answering a question of his. Here A is the class of real problems which are algorithmic in bounded time. We also prove the stronger result: , where PAR stands for parallel polynomial time. In our terminology, we say that is A-saturated and PAR-saturated. We also prove, at the nonuniform level, the above results for every real-closed field. It is not known whether is P-saturated. In the case of the reals with addition and order we obtain P-saturation ). More generally, we show that an ordered -vector space is P-saturated at the nonuniform level ).We also study a stronger notion that we call P-stability. Blum, Cucker, Shub and Smale have shown that fields of characteristic 0 are P-stable. We show that the reals with addition and order are P-stable, but real-closed fields are not.Questions and and the/const complexity classes have some model theoretic flavor. This leads to the theory of complexity over “arbitrary” structures as introduced by Poizat. We give a summary of this theory with a special emphasis on the connections with model theory and we study/const complexity classes from this point of view. Note also that our proof of the PAR-saturation of shows that an o-minimal structure which admits quantifier elimination is A-saturated at the nonuniform level. (shrink)

Aleksandar Ignjatović. Delineating Classes of Computational Complexity via Second Order Theories with Weak Set Existence Principles (I).

We systematically study the completion of choice problems in the Weihrauch lattice. Choice problems play a pivotal rôle in Weihrauch complexity. For one, they can be used as landmarks that characterize important equivalences classes in the Weihrauch lattice. On the other hand, choice problems also characterize several natural classes of computable problems, such as finite mind change computable problems, non-deterministically computable problems, Las Vegas computable problems and effectively (...) Borel measurable functions. The closure operator of completion generates the concept of total Weihrauch reducibility, which is a variant of Weihrauch reducibility with total realizers. Logically speaking, the completion of a problem is a version of the problem that is independent of its premise. Hence, studying the completion of choice problems allows us to study simultaneously choice problems in the total Weihrauch lattice, as well as the question which choice problems can be made independent of their premises in the usual Weihrauch lattice. The outcome shows that many important choice problems that are related to compact spaces are complete, whereas choice problems for unbounded spaces or closed sets of positive measure are typically not complete. (shrink)

Objective Apeiron was founded in 1966 and has developed into one of the oldest and most distinguished journals dedicated to the study of ancient philosophy, ancient science, and, in particular, of problems that concern both fields. Apeiron is committed to publishing high-quality research papers in these areas of ancient Greco-Roman intellectual history; it also welcomes submission of articles dealing with the reception of ancient philosophical and scientific ideas in the later western tradition. The journal appears quarterly. Articles are peer-reviewed (...) on a double-blind basis. Topics ancient philosophy ancient science reception of ancient philosophical and scientific ideas in the later western tradition Article formats Original Articles. (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)

The evolutionary circuit design is an approach allowing engineers to realize computational devices. The evolved computational devices represent a distinctive class of devices that exhibits a specific combination of properties, not visible and studied in the scope of all computational devices up till now. Devices that belong to this class show the required behavior; however, in general, we do not understand how and why they perform the required computation. The reason is that the evolution can utilize, in addition to the (...) “understandable composition of elementary components”, material-dependent constructions and properties of environment (such as temperature, electromagnetic field etc.) and, furthermore, unknown physical behaviors to establish the required functionality. Therefore, nothing is known about the mapping between an abstract computational model and its physical implementation. The standard notion of computation and implementation developed in computer science as well as in cognitive science has become very problematic with the existence of evolved computational devices. According to the common understanding, the evolved devices cannot be classified as computing mechanisms. (shrink)

Using educational robots to integrate computational thinking with cross-disciplinary content has gone beyond Science, Technology, Engineering, and Mathematics, to include foreign-language learning and further cross-context target-language acquisition. Such integration must not solely emphasise CT problem-solving skills. Rather, it must provide students with interactive learning to support their target-language interaction while reducing potential TL anxiety. This study aimed to validate the effects of the proposed method of pair programming along with question-and-response interaction in a board-game activity on young learners’ CT skills (...) and TL learning across contexts. Two Grade 6 classes, one with 16 students who were studying Chinese as a Second Language and the other with 16 students who were studying English as a Foreign Language, participated in the activity. A series of instruments on achievement assessment, questionnaires on CT skills and TL anxiety, and sequential learning behaviour analysis were used to critically examine the results. The main conclusion is that the EFL group showed better social skills of cooperation on CT and lower TL learning anxiety, while the CSL group demonstrated better problem-solving skills in CT, but presented more behaviours of trial-and-error loops. Results not only contribute suggestions for cross-disciplinary learning but also provide support for cross-context instruction beyond educational coursework. (shrink)

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

We present an overview of the topics in the title and of some of the key results pertaining to them. These have historically been topics of interest in computability theory and continue to be a rich source of problems and ideas. In particular, we draw attention to the links and connections between these topics and explore their significance to modern research in the field.

"A valuable collection both for original source material as well as historical formulations of current problems."-- The Review of Metaphysics "Much more than a mere collection of papers . . . a valuable addition to the literature."-- Mathematics of Computation An anthology of fundamental papers on undecidability and unsolvability by major figures in the field, this classic reference opens with Godel's landmark 1931 paper demonstrating that systems of logic cannot admit proofs of all true assertions of arithmetic. Subsequent papers (...) by Godel, Church, Turing, and Post single out the class of recursive functions as computable by finite algorithms. Additional papers by Church, Turing, and Post cover unsolvable problems from the theory of abstract computing machines, mathematical logic, and algebra, and material by Kleene and Post includes initiation of the classification theory of unsolvable problems. Suitable for graduate and undergraduate courses. 1965 ed. (shrink)

Quasi-classical logic is a propositional logic for reasoning under inconsistency pointed out recently in the literature [3] [21]. Compared with several other paraconsistent logics, it has the nice feature that no special attention needs to be paid to a special form of premises. However, only few is known about its computational behaviour up to now. In this paper, we fill this gap by pointing out a linear time translation that maps every instance of the quasi-classical entailment problem for CNF formulas (...) into an instance of the classical entailment problem. This enables us to show that quasi-classical entailment for CNF formulas is “only” coNP -complete, take advantage of all existing automated reasoning techniques for classical entailment in order to improve quasi-classical inference from the practical side. Especially, tractable classes of formulas for quasi-classical entailment are pointed out. (shrink)

In their simplest form, hybrid languages are propositional modal languages which can refer to states. They were introduced by Arthur Prior, the inventor of tense logic, and played an important role in his work: because they make reference to specific times possible, they remove the most serious obstacle to developing modal approaches to temporal representation and reasoning. However very little is known about the computational complexity of hybrid temporal logics.In this paper we analyze the complexity of the satisfiability problem of (...) a number of hybrid temporal logics: the basic hybrid language over transitive trees; nominal Until logic; and referential interval logic. We discuss the effects of including nominals, the @ operator, the somewhere modality E, and the difference operator D. Adding nominals to tense logic leads for several frame-classes to an increase in complexity of the satisfiability problem from PSPACE to EXPTIME. On transitive trees, however, the satisfiability problem for this language can be decided in PSPACE. Along the way we make a detour through hybrid propositional dynamic logic: we establish upper bounds for a number of temporal logics by generalizing results due to Passy and Tinchev [29] and De Giacomo [16]. We conclude with some remarks on the relevance of our results to description logic, and draw attention to the utility of the spypoint technique for proving upper and lower bounds. (shrink)

In computational complexity theory, decision problems are divided into complexity classes based on the amount of computational resources it takes for algorithms to solve them. In theoretical computer science, it is commonly accepted that only functions for solving problems in the complexity class P, solvable by a deterministic Turing machine in polynomial time, are considered to be tractable. In cognitive science and philosophy, this tractability result has been used to argue that only functions in P can feasibly (...) work as computational models of human cognitive capacities. One interesting area of computational complexity theory is descriptive complexity, which connects the expressive strength of systems of logic with the computational complexity classes. In descriptive complexity theory, it is established that only first-order systems are connected to P, or one of its subclasses. Consequently, second-order systems of logic are considered to be computationally intractable, and may therefore seem to be unfit to model human cognitive capacities. This would be problematic when we think of the role of logic as the foundations of mathematics. In order to express many important mathematical concepts and systematically prove theorems involving them, we need to have a system of logic stronger than classical first-order logic. But if such a system is considered to be intractable, it means that the logical foundation of mathematics can be prohibitively complex for human cognition. In this paper I will argue, however, that this problem is the result of an unjustified direct use of computational complexity classes in cognitive modelling. Placing my account in the recent literature on the topic, I argue that the problem can be solved by considering computational complexity for humanly relevant problem solving algorithms and input sizes. (shrink)

Some regularities enjoy only an attenuated existence in a body of training data. These are regularities whose statistical visibility depends on some systematic recoding of the data. The space of possible recodings is, however, infinitely large – it is the space of applicable Turing machines. As a result, mappings that pivot on such attenuated regularities cannot, in general, be found by brute-force search. The class of problems that present such mappings we call the class of “type-2 problems.” Type-1 (...) problems, by contrast, present tractable problems of search insofar as the relevant regularities can be found by sampling the input data as originally coded. Type-2 problems, we suggest, present neither rare nor pathological cases. They are rife in biologically realistic settings and in domains ranging from simple animat behaviors to language acquisition. Not only are such problems rife – they are standardly solved! This presents a puzzle. How, given the statistical intractability of these type-2 cases, does nature turn the trick? One answer, which we do not pursue, is to suppose that evolution gifts us with exactly the right set of recoding biases so as to reduce specific type-2 problems to type-1 mappings. Such a heavy-duty nativism is no doubt sometimes plausible. But we believe there are other, more general mechanisms also at work. Such mechanisms provide general strategies for managing problems of type-2 complexity. Several such mechanisms are investigated. At the heart of each is a fundamental ploy – namely, the maximal exploitation of states of representation already achieved by prior, simpler learning so as to reduce the amount of subsequent computational search. Such exploitation both characterizes and helps make unitary sense of a diverse range of mechanisms. These include simple incremental learning, modular connectionism, and the developmental hypothesis of “representational redescription”. In addition, the most distinctive features of human cognition – language and culture – may themselves be viewed as adaptations enabling this representation/computation trade-off to be pursued on an even grander scale. (shrink)

Church's thesis, that all reasonable definitions of “computability” are equivalent, is not usually thought of in terms of computability by acontinuouscomputer, of which the general-purpose analog computer (GPAC) is a prototype. Here we prove, under a hypothesis of determinism, that the analytic outputs of aC∞GPAC are computable by a digital computer.In [POE, Theorems 5, 6, 7, and 8], Pour-El obtained some related results. (The proof there of Theorem 7 depends on her Theorem 2, for which the proof in [POE] (...) is incorrect, but for which a correct proof is given in [LIR]. Also, the proof in [POE] of Theorem 8 depends on the unproved assertion that a solution of an algebraic differential equation must be analytic on an open subset of its domain. However, this assertion was later proved in [BRR].) As in [POE], we reduce the problem to a problem about solutions of certain systems of algebraic differential equations (ADE's). If such a system is nonsingular (i.e. if the “separant” does not vanish along the given solution), then the argument is very easy (see [VSD] for an even simpler situation), so that the essential difficulties arise fromsingularsystems. Our main tools in handling these difficulties are drawn from the excellent (and difficult) paper [DEL] by Denef and Lipshitz. The author especially wants to thank Leonard Lipshitz for his kind help in the preparation of the present paper.We emphasize here that our proof of the simulation result applies only to the GPAC as described below. The GPAC's form a natural subclass of the class of all analog computers, and are based on certain idealized components (“black boxes”), mostly associated with the technology of past decades. One can easily envisage other kinds of black boxes of an input-output character that would lead to different kinds of analog computers. (For example, one could incorporate delays, or spatial integrators in addition to the present temporal integrators, etc.) Whether digital simulation is possible for these “extended” analog computers poses a rich and challenging set of research questions. (shrink)

Tissue P systems with evolutional communication rules are computational models inspired by biochemical systems consisting of multiple individuals living and cooperating in a certain environment, where objects can be modified when moving from one region to another region. In this work, cell separation, inspired from membrane fission process, is introduced in the framework of tissue P systems with evolutional communication rules. The computational complexity of this kind of P systems is investigated. It is proved that only problems in class (...) P can be efficiently solved by tissue P systems with cell separation with evolutional communication rules of length at most, for each natural number n≥1. In the case where that length is upper bounded by, a polynomial time solution to the SAT problem is provided, hence, assuming that P≠NP a new boundary between tractability and NP-hardness on the basis of the length of evolutional communication rules is provided. Finally, a new simulator for tissue P systems with evolutional communication rules is designed and is used to check the correctness of the solution to the SAT problem. (shrink)

The paper is devoted to applications of algebraic logic to databases. In databases a query is represented by a formula of first order logic. The same query can be associated with different formulas. Thus, a query is a class of equivalent formulae: equivalence here being similar to that in the transition to the Lindenbaum-Tarski algebra. An algebra of queries is identified with the corresponding algebra of logic. An algebra of replies to the queries is also associated with algebraic logic. These (...) relations lie at the core of the applications.In this paper it is shown how the theory of Halmos (polyadic) algebras (a notion introduced by Halmos as a tool in the algebraization of the first order predicate calculus) is used to create the algebraic model of a relational data base. The model allows us, in particular, to solve the problem of databases equivalence as well as develop a formal algebraic definition of a database's state description. In this paper we use the term "state description" for the logical description of the model. This description is based on the notion of filters in Halmos algebras. When speaking of a state description, we mean the description of a function which realizes the symbols of relations as real relations in the given system of data. (shrink)

The central paradigm of arti?cial intelligence is rapidly shifting toward biological models for both robotic devices and systems performing such critical tasks as network management, vehicle navigation, and process control. Here we use a recent mathematical analysis of the necessary conditions for consciousness in humans to explore likely failure modes inherent to a broad class of biologically inspired computing machines. Analogs to developmental psychopathology, in which regulatory mechanisms for consciousness fail progressively and subtly understress, and toinattentional blindness, where a narrow (...) 'syntactic band pass' de?ned by the rate distortion manifold of conscious attention results in pathological ?xation, seem inevitable. Similar problems are likely to confront other possible architectures, although their mathematical description may be far less straightforward. Computing devices constructed on biological paradigms will inevitably lack the elaborate, but poorly understood, system of control mechanisms which has evolved over the last few hundred million years to stabilize consciousness in higher animals. This will make such machines prone to insidious degradation, and, ultimately, catastrophic failure. (shrink)

According to Church’s thesis, we can identify the intuitive concept of effective computability with such well-defined mathematical concepts as Turing computability and partial recursiveness. The almost universal acceptance of Church’s thesis among logicians and computer scientists is puzzling from some epistemological perspectives, since no formal proof is possible of a thesis that involves an informal concept such as effectiveness. Elliott Mendelson has recently argued, however, that equivalencies between intuitive notions and precise notions need not always be considered unprovable theses, and (...) that Church’s thesis should be accepted as true.I want to discuss a thesis that is nearly as important in current research in computer science as Church’s thesis. I call the newer thesis the tractability thesis, since it identifies the intuitive class of computationally tractable problems with a precise class of problems whose solutions can be computed in polynomial time. After briefly reviewing the theory of intractability, I compare the grounds for accepting the tractability thesis with the grounds for accepting Church's thesis. Intimately connected with the tractability thesis is the mathematical conjecture, whose meaning I shall shortly explain, that P≠NP. Unlike Church's thesis, this conjecture is precise enough to be capable of mathematical proof, but most computer scientists believe it even though no proof has been found. As we shall see below, understanding the grounds for acceptance of the conjecture that P≠NP has implications for general questions in the philosophy of mathematics and science, especially concerning the epistemological importance of explanatory and conceptual coherence. (shrink)

What is computational explanation? Many accounts treat it as a kind of causal explanation. I argue against two more specific versions of this view, corresponding to two popular treatments of causal explanation. The first holds that computational explanation is mechanistic, while the second holds that it is interventionist. However, both overlook an important class of computational explanations, which I call limitative explanations. Limitative explanations explain why certain problems cannot be solved computationally, either in principle or in practice. I argue (...) that limitative explanations are not plausibly understood in either mechanistic or interventionist terms. One upshot of this argument is that there are causal and non-causal kinds of computational explanation. I close the paper by suggesting that both are grounded in the notion of computational implementation. (shrink)

In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial (...) time. Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)

A completeness theory for parameterized computational complexity has been studied in a series of recent papers, and has been shown to have many applications in diverse problem domains including familiar graph-theoretic problems, VLSI layout, games, computational biology, cryptography, and computational learning [ADF,BDHW,BFH, DEF,DF1-7,FHW,FK]. We here study the parameterized complexity of two kinds of problems: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} (...) \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps (the Short TM Computation Problem), and (2) problems concerning derivations and factorizations, such as determining whether a word \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $x$\end{document} can be derived in a grammar \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $G$\end{document} in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} steps, or whether a permutation has a factorization of length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $k$\end{document} over a given set of generators. We show hardness and completeness for these problems for various levels of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W$\end{document} hierarchy. In particular, we show that Short TM Computation is complete for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $W[1]$\end{document}. This gives a new and useful characterization of the most important of the apparently intractable parameterized complexity classes. (shrink)

We study computable PAC (CPAC) learning as introduced by Agarwal et al. (2020). First, we consider the main open question of finding characterizations of proper and improper CPAC learning. We give a characterization of a closely related notion of strong CPAC learning, and provide a negative answer to the COLT open problem posed by Agarwal et al. (2021) whether all decidably representable VC classes are improperly CPAC learnable. Second, we consider undecidability of (computable) PAC learnability. We give (...) a simple general argument to exhibit such ndecidability, and initiate a study of the arithmetical complexity of learnability. We briefly discuss the relation to the undecidability result of Ben-David et al. (2019), that motivated the work of Agarwal et al. (shrink)

Basic Digital Education is already planned to be integrated with the forthcoming curriculum for Austrian primary schools as it was already implemented for lower secondary schools in 2018. BDE includes the most essential and novel developments of Computational Thinking, which are fundamentally responsible for nurturing students' problem-solving skills. Thus, evaluating teaching materials, scaffolding guidelines, and assessments is becoming increasingly important for the successful implementation of CT in Austrian classrooms. This study is a part of a longitudinal multi-cycle educational design research (...) project aiming to explore how to foster CT and to raise the awareness, importance, and confidence of teachers and students in applying CT for everyday uses. Our paper focuses on a sub-study in which teaching units for grade 3 and 4 students were designed by combining an Open Educational Resource textbook and Physical Computing with the micro:bit device. The designed learning environment consists of three units and was implemented in two classes over 3 weeks. The two classes were further split into two groups each, to ensure better support during implementation. The class teachers received upfront teacher training and conducted pre- and post-test assessments with the students. The resulting data was then analyzed to gain insights into the effects on CT skills of the young learners. Results showed that combining block-based programming and physical computing devices could become a promising approach to promote computational thinking skills in lower school grades. Furthermore, the observed direction of the designed units supports low-barrier access to increase the desired uses of CT in classrooms. (shrink)

Introduction -- Algorithms, programs, procedures, and abstract automata -- Functioning of algorithms and automata, computation, and operations with algorithms and automata -- Basic postulates and axioms for algorithms -- Power of algorithms and classes of algorithms: comparison and evaluation -- Computing, accepting, and deciding modes of algorithms and programs -- Problems that people solve and related properties of algorithms -- Boundaries for algorithms and computation -- Software and hardware verification and testing -- Conclusion.

Twenty classes in ten schools with 627 sixth?grade students in five cities in Taiwan participated in this study. The research provides information on the performance differences among written computation, pictorial representation, symbolic representation and number sense. The results of One?way ANOVA analysis indicate that significant difference was found among WCT, PRT, SRT and NST tests, with F=536.327, p=0.000. The a posteriori comparisons show for each pair (WCT vs PRT, WCT vs SRT, WCT vs NST, PRT vs SRT and SRT (...) vs NST) significant difference at the 0.001 level (p=0.000), except for the pair comparison between PRT and NST. This implies that these Taiwanese students were highly skilled in written computation but their written skills were not equally transferred to use of non?computational paths that depended on symbolic representation, pictorial representation and number sense to solve similar problems. (shrink)

The paper considers the intellectual computer mathematics system InparSolver, which is designed to automatically explore and solve basic classes of computational mathematics problems on multi-core computers with graphics accelerators. The problems of results reliability of solving problems with approximate input data are outlined. The features of the use of existing computer mathematics systems are analyzed, their weaknesses are found. The functionality of InparSolver, some innovative approaches to the implementation of effective solutions to problems in a (...) hybrid architecture are described. Examples of applied usage of InparSolver for processes mathematical modeling in various subject areas are given. Nowadays, new more complex objects and phenomena in many subject areas are constantly emerging, which are subject to mathematical research on a computer. This encourages the development of new numerical methods and technologies of mathematical modeling, as well as the creation of more powerful computers for their implementation. With the advent and constant development of supercomputers of various architectures, the problems of their effective use, expansion of tasks range should be solved, ensuring the reliability of computer results and increasing the level of intellectual information support for users ‒ specialists in various fields. Today, the issues of solving these problems are given special attention by many specialists in the fields of information technology and parallel programming. The world's leadingscientists in the field of computer technology see the solution to the problems of efficient usage of modern supercomputers in algorithmic software creation that easily adapts to different computer architectures with different types of memory and coprocessors, supports efficient parallelism on millions of cores etc. In addition, improving the efficiency of high-performance computing on modern supercomputers is provided by their intellectualization, transferring to the computer to perform a significant part of the functions. The industry of development and usage of intelligent computer technologies is one of the main directions of science and technology development in modern society. (shrink)

A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if every member of Q Turing computes a member of P. We say that P is strongly reducible to Q if every member of Q Turing computes a member of P via a fixed Turing functional. The weak degrees and strong degrees are the equivalence classes of mass problems under weak and strong (...) reducibility, respectively. We focus on the countable distributive lattices P w and P s of weak and strong degrees of mass problems given by nonempty Π 1 0 subsets of 2 ω . Using an abstract Gödel/Rosser incompleteness property, we characterize the Π 1 0 subsets of 2 ω whose associated mass problems are of top degree in P w and P s , respectively. Let R be the set of Turing oracles which are random in the sense of Martin-Löf, and let r be the weak degree of R. We show that r is a natural intermediate degree within P w . Namely, we characterize r as the unique largest weak degree of a Π 1 0 subset of 2 ω of positive measure. Within P w we show that r is meet irreducible, does not join to 1, and is incomparable with all weak degrees of nonempty thin perfect Π 1 0 subsets of 2 ω . In addition, we present other natural examples of intermediate degrees in P w . We relate these examples to reverse mathematics, computational complexity, and Gentzen-style proof theory. (shrink)

We propose a framework for including information‐processing bounds in rational analyses. It is an application of bounded optimality (Russell & Subramanian, 1995) to the challenges of developing theories of mechanism and behavior. The framework is based on the idea that behaviors are generated by cognitive mechanisms that are adapted to the structure of not only the environment but also the mind and brain itself. We call the framework computational rationality to emphasize the incorporation of computational mechanism into the definition of (...) rational action. Theories are specified as optimal program problems, defined by an adaptation environment, a bounded machine, and a utility function. Such theories yield different classes of explanation, depending on the extent to which they emphasize adaptation to bounds, and adaptation to some ecology that differs from the immediate local environment. We illustrate this variation with examples from three domains: visual attention in a linguistic task, manual response ordering, and reasoning. We explore the relation of this framework to existing “levels” approaches to explanation, and to other optimality‐based modeling approaches. (shrink)

We overview logical and computational explanations of the notion of tractability as applied in cognitive science. We start by introducing the basics of mathematical theories of complexity: computability theory, computational complexity theory, and descriptive complexity theory. Computational philosophy of mind often identifies mental algorithms with computable functions. However, with the development of programming practice it has become apparent that for some computable problems finding effective algorithms is hardly possible. Some problems need too much computational resource, e.g., (...) time or memory, to be practically computable. Computational complexity theory is concerned with the amount of resources required for the execution of algorithms and, hence, the inherent difficulty of computational problems. An important goal of computational complexity theory is to categorize computational problems via complexity classes, and in particular, to identify efficiently solvable problems and draw a line between tractability and intractability. -/- We survey how complexity can be used to study computational plausibility of cognitive theories. We especially emphasize methodological and mathematical assumptions behind applying complexity theory in cognitive science. We pay special attention to the examples of applying logical and computational complexity toolbox in different domains of cognitive science. We focus mostly on theoretical and experimental research in psycholinguistics and social cognition. (shrink)