Several results from classical computability theory (computability over discrete structures such as the natural numbers and strings over finite alphabets, due to Turing, Church, Kleene and others) have been shown to hold for a generalisation of computability theory over total abstract algebras, using for instance the model of \While\ computation. We present a number of results relating to computation on topological partial algebras, again using \While\ computation. We consider several results from the classical theory in the context of topological algebra of the reals: closure of semicomputable sets under finite union (Chapter \ref{chap:results1} Theorem \ref{thm:union_While_scomp_not_While_scomp}, p.\pageref{thm:union_While_scomp_not_While_scomp}), the equivalence of semicomputable and projectively (semi)computable sets (Chapter \ref{chap:results2} Theorem \ref{thm:proj_while_equivalents}, p.\pageref{thm:proj_while_equivalents}), and Post's Theorem (i.e.~a set is computable iff both it and its complement are semicomputable) (Appendix \ref{appendix:posts_theorem} Theorem \ref{thm:posts_general}, p.\pageref{thm:posts_general}). This research has significance in the field of scientific computation, which is underpinned by computability on the real numbers. We will consider a ``continuity principle", which states that computability should imply continuity; however, equality, order, and other total boolean-valued functions on the reals are clearly discontinuous. As we want these functions to be basic for the algebras under consideration, we resolve this incompatibility by redefining such functions to be partial, leading us to consider topological partial algebras. / Thesis / Master of Computer Science (MCS) / We investigate to what extent certain well-known results of classical computability theory on the natural numbers hold in the context of generalised computability theories on the real numbers.

In this dissertation we study a pioneering model of analog computation called General Purpose Analog Computer (GPAC), introduced by Shannon in 1941. The GPAC is capable of manipulating real-valued data streams. Its power is characterized by the class of differentially algebraic functions, which includes the solutions of initial value problems for ordinary differential equations. We address two limitations of this model. The first is its fundamental inability to reason about functions of more than one independent variable (the `time' variable). In particular, the Shannon GPAC cannot be used to specify solutions of partial differential equations. The second concerns the notion of approximability, a desirable property in computation over continuous spaces that is however absent in the GPAC. To overcome these limitations, we extend the class of data types by taking channels carrying information on a general complete metric space X; for example the class of continuous functions of one real variable. We consider the original modules in Shannon's construction (constants, adders, multipliers, integrators) and add two new modules: a differential module which computes spatial derivatives; and a continuous limit module which computes limits. We then build networks using X-stream channels and the abovementioned modules. This leads us to a framework in which the speci cations of such analog systems are given by fi xed points of certain operators on continuous data streams, as considered by Tucker and Zucker. We study the properties of these analog systems and their associated operators. We present a characterization which generalizes Shannon's results. We show that some non-differentially algebraic functions such as the gamma function are generable by our model. Finally, we attempt to relate our model of computation to the notion of tracking computability as studied by Tucker and Zucker. / Thesis / Doctor of Philosophy (PhD)

We study the degree structures of the strong reducibilities $(\leq_{ibT})$ and $(\leq_{cl})$, as well as $(\leq_{rK})$ and $(\leq_{wtt})$. We show that any noncomputable c.e. set is part of a uniformly c.e. copy of $(\BQ,\leq)$ in the c.e. cl-degrees within a single wtt-degree; that there exist uncountable chains in each of the degree structures in question; and that any countable partially-ordered set can be embedded into the cl-degrees, and any finite partially-ordered set can be embedded into the ibT-degrees. We also offer new proofs of results of Barmpalias and Lewis-Barmpalias concerning the non-existence of cl-maximal sets.

We study the degree structures of the strong reducibilities $(\leq_{ibT})$ and $(\leq_{cl})$, as well as $(\leq_{rK})$ and $(\leq_{wtt})$. We show that any noncomputable c.e. set is part of a uniformly c.e. copy of $(\BQ,\leq)$ in the c.e. cl-degrees within a single wtt-degree; that there exist uncountable chains in each of the degree structures in question; and that any countable partially-ordered set can be embedded into the cl-degrees, and any finite partially-ordered set can be embedded into the ibT-degrees. We also offer new proofs of results of Barmpalias and Lewis-Barmpalias concerning the non-existence of cl-maximal sets.

<p> Various models of computability of partial functions f on the real numbers are studied: two abstract, based on approximable computation w.r.t high level programming languages; two concrete, based on computable tracking functions on the rationals; and two based on polynomial approximation. It is shown that these six models are equivalent, under the assumptions: (1) the domain of f is a union of an effective sequence of rational open intervals, and (2) f is effectively locally uniformly continuous. This includes the well-known functions of elementary real analysis (rational, exponential, trigonometric, etc., and their inverses) and generalises a previously know equivalence result for total functions on the reals. </p> / Thesis / Master of Science (MSc)

Master of Science / Department of Computer Science / Torben Amtoft / Shannon’s and Chomsky’s attempts to model natural language with Markov chains showed differing gauges of language complexity. These were codified with the Chomsky Hierarchy with four types of languages, each with an accepting type of grammar and au- tomaton. Though still foundationally important, this fails to identify remarkable proper subsets of the types including recursive languages among recursively enumerable languages. In general, with Rice’s theorem, it is undecidable whether a Turing machine’s language is re- cursive. But specifically, Hopcroft & Ullman show that the languages of space bound Turing machines are recursive. We show the converse also to be true. The space hierarchy theorem shows that there is a continuum of proper subsets within the recursive languages. With Myhill’s description of a linear bounded automata, Landweber showed that they accept a subset of the type 1 languages including the type 2 languages. Kuroda expanded the definition making the automata nondeterministic and showed that nondeterministic linear space is the set of type 1 languages. That only one direction was proven deterministically but both nondeterministically, would suggest that nondeterminism increases expressiveness. This is further supported by Savitch’s theorem. However, it is not without precedent for predictions in computability theory to be wrong. Turing showed that Hilbert’s Entschei- dungsproblem is unsolvable and Immerman disproved Landweber’s belief that type 1 lan- guages are not closed under complementation. Currently, a major use of language theory is computer language processing including compilation. We will show that for the Java programming language, compilability can be computed in nondeterministic linear space by the existence of a (nondeterministic) linear bounded automaton which abstractly computes compilability. The automaton uses the tra- ditional pipeline architecture to transform the input in phases. The devised compiler will attempt to build a parse tree and then check its semantic properties. The first two phases, lexical and syntactical analysis are classic language theory tasks. Lexical analysis greedily finds matches to a regular language. Each match is converted to a token and printed to the next stream. With this, linearity is preserved. With a Lisp format, a parse tree can be stored as a character string which is still linear. Since the tree string preserves structural information from the program source, the tree itself serves as a symbol table, which normally would be separately stored in a readable efficient manner. Though more difficult than the previous step, this will also be shown to be linear. Lastly, semantic analysis, including typechecking, and reachability are performed by traversing the tree and annotating nodes. This implies that there must exist a context-sensitive grammar that accepts compilable Java. Therefore even though the execution of Java programs is Turing complete, their compilation is not.

It is known that orderings can be formed with settling time domination and strong settling time domination as relations on c.e. sets. However, it has been shown that no such ordering can be formed when considering computation time domination as a relation on $n$-c.e. sets where $n \geq 3$. This will be extended to the case of $2$-c.e. sets, showing that no ordering can be derived from computation time domination on $n$-c.e. sets when $n\geq 2$. Additionally, we will observe properties of the orderings given by settling time domination and strong settling time domination on c.e. sets, respectively denoted as $\mathcal{E}_{st}$ and $\mathcal{E}_{sst}$. More specifically, it is already known that any countable partial ordering can be embedded into $\mathcal{E}_{st}$ and any linear ordering with no infinite ascending chains can be embedded into $\mathcal{E}_{sst}$. Continuing along this line, we will show that any finite partial ordering can be embedded into $\mathcal{E}_{sst}$.

It is known that orderings can be formed with settling time domination and strong settling time domination as relations on c.e. sets. However, it has been shown that no such ordering can be formed when considering computation time domination as a relation on $n$-c.e. sets where $n \geq 3$. This will be extended to the case of $2$-c.e. sets, showing that no ordering can be derived from computation time domination on $n$-c.e. sets when $n\geq 2$. Additionally, we will observe properties of the orderings given by settling time domination and strong settling time domination on c.e. sets, respectively denoted as $\mathcal{E}_{st}$ and $\mathcal{E}_{sst}$. More specifically, it is already known that any countable partial ordering can be embedded into $\mathcal{E}_{st}$ and any linear ordering with no infinite ascending chains can be embedded into $\mathcal{E}_{sst}$. Continuing along this line, we will show that any finite partial ordering can be embedded into $\mathcal{E}_{sst}$.

The ordering of concept classes under PAC reducibility is nonlinear, even when restricted to particular concrete examples. We construct two effective concept classes of incomparable PAC degrees to show that there exist incomparable PAC degrees, analogous to incomparable Turing degrees. The non-learnability of concept classes in the PAC learning model is explained by the existence of PAC incomparable degrees. It was necessary to deal with the size of an effective concept class thus we propose a method to compute the size of the effective concept class using Kolmogorov complexity. To define the jump operator for PACi degrees the join of effective concept classes is constructed and explores the possibility of embedding known degrees to PACi or PAC degrees. If an embedding exists it will enable proving properties of known degrees for PACi and PAC degrees without explicitly proving them.

La calculabilité est centrée autour de la notion de fonction calculable telle que définie par Church, Kleene, Rosser et Turing au siècle dernier. D'abord focalisée sur les nombres entiers, la calculabilité a été généralisée aux ensembles, notamment par le biais de la théorie axiomatique des ensembles de Kripke-Platek. Dans cette thèse, nous définissons une notion générale de calculabilité, les sous-calculabilités, dont les axiomes sont satisfaits à la fois par de nombreux fragments récursifs de la calculabilité classique, mais également par des calculabilités d'ordre supérieur sur les ensembles admissibles. Nous montrons, sur cette structure composée d'une énumération de fonctions totales et d'une énumération de fonctions partielles, que les théorèmes classiques de calculabilité (isomorphisme de Myhill, Rogers, théorème s-m-n,point fixe de Kleene, théorème de Rice, créativité, etc.) sont présents sous différentes formes alors même que les sous-calculabilités ne comprennent qu'un fragment des objets de la calculabilité classique. Les structures de degrés associées aux notions de récursivité que nous définissons reflètent également des propriétés de la calculabilité (degrés intermédiaires, high, low, etc.), mais nos réductions étant plus fortes, une structure fine apparaît à l'intérieur même des degrés récursifs. Finalement, nous montrons que les calculabilités sur les admissibles sont interprétables dans le formalisme des sous-calculabilités. En particulier, les énumérations des ensembles alpha-finis et alpha-énumérables présents dans ce contexte nous permettent de transférer certains résultats d'un modèle à l'autre. / Computability is centered on computable functions, as defined by Church, Kleene,Rosser and Turing in the twentieth century. Initially focused on integers,computability has been generalised to sets, in particular thanks toKripke-Platek's Axiomatic Set Theory.In this thesis, we define a general notion of computability,sub-computabilities, whose axioms are satisfied by numerous recursive fragmentsof classical computability, and also by higher-order computabilities overadmissible sets. We show how in sub-computabilities, containing an enumeration oftotal functions and an enumeration of partial functions, classical theoremssuch as Myhill and Rogers isomorphisms, s-m-n theorem, Kleene's fixed-point orRice's theorem hold in a slightly different way, even if a large part ofthe objects of computability are missing. Along with each of thesesub-computabilities and their different notions of recursivity comes a structureof degrees (with intermediate, high and low degrees, etc.), refining theclassical one, our notions of recursivity being stronger.Moreover, we show how admissible computability can be interpreted through theformalism of sub-computabilities. In particular, the enumerations ofalpha-finite and alpha-enumerable sets present in this setting allowsome interesting results to be carried from one model to the other.