Thesis (Ph. D.)--University of Chicago, Dept. of Physics, December 2000. / Includes bibliographical references. Also available on the Internet.

Thesis (MScEng)--University of Stellenbosch, 2008. / Bibliography. Also available via the Internet.

Thesis (Ph. D.)--University of Texas at Austin, 2006. / Vita. Includes bibliographical references and index.

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.

This paper is a critical essay on the question "Can machines think?", with particular attention paid to the articles appearing in an anthology Minds and Machines, A. R. Anderson editor. The general conclusion of this paper is that those arguments which have been advanced to show that machines can think are inconclusive. I begin by examining rather closely a paper by Hilary Putnam called "Minds and Machines" in which he argues that the traditional mind-body problem can arise with a complex cybernetic machine. My argument against Putnam's is that either there are no problems with computers which are analogous to the ones raised by mental states, or where there are problems with machines, these problems do not have at bottom the same difficulties that human experiences raises. I then continue by showing that a cybernetic machine is an instantiation of a formal system. This leads to a discussion of the relationship between formality and predictability in which I try to show that some types of machine are in principle predictable. In the next section I attempt to prove that any discussion of outward signs of imitative behavior presupposes that some linguistic theory, such as a type reduction, has been substantiated. The force of this argument is that such a theory has not in fact been substantiated. I offer some general theory about the complexity of concept-property relations. Finally I give a demonstration that no test or set of tests can be found that will be logically sufficient for the ascription of the concept "capable of thought." If this is successful, then I have shown that no test can be found, which when a machine is built to pass it, is logically adequate for saying that that .machine can think. This argument is offered as further criticism of the Imitation Game which A. M. Turing proposed as an adequate test for thinking subjects. Besides the specific conclusion that insufficient evidence, has been offered to say that machines can think, this paper offers a more general conclusion that most standard problems have at bottom a linguistic difficulty. However, this general conclusion is a broad speculative one to which the work in this paper, is only a small exemplification and as such reflects mainly the further ambitions of the author. / Arts, Faculty of / Philosophy, Department of / Graduate

This thesis aims to better represent a framework for asynchrony. Traditional asynchronous models, particularly those used to simulate cellular automata, have used stochasticity or randomness to generate update times. We claimthat, while they may make good representations of their application, such asynchronousmethods rid themodel of the essence of interesting asynchronous processes. Thus, we attempt to better harness the aspects internal to the decision process of such discretely dynamic cells as those in cellular automata.We propose the maxmin-m model as a suitable model for the asynchronous computation of cellular automata. The model uses maxmin-plus algebra, a special case of which is max-plus algebra. This algebra arises naturally from the cellular automaton requirement that a cell receives the state of its neighbours before updating. The maxmin-m model allows each cell to update after it receives m out of a possible n neighbours' states.The max-plus model shows that, while update times may be asynchronous in real time, there is no loss of information, since the corresponding asynchronous process is bijectively related to the synchronous model. In turn, the cellular automaton output, measured by the Shannon and word entropies, is shown to vary little from the synchronous model. Moreover, this type of asynchrony is simple, i.e. it is deterministically obtained due to the linearity of max-plus algebra.Indeed, the maxmin-m model is also shown to be deterministic and always reaches periodic behaviour. In the long time limit, this model is shown to be represented by a max-plus model, supporting its determinism further. Consequently, the complexity of such a model may be thought to be limited. However, we show through large scale experiments that the case where m is approximately n/2 generates most complex behaviour in terms of large periods and transients to the aforementioned periodic orbits. In particular, the complexity is empirically shown to obey a bell form as a function of m (where m ranges from 1 to n). The resulting cellular automaton simulations indicate a correspondence from the complexity of the update times. Therefore, cellular automaton behaviour may be predictable with the type of asynchrony employed in this thesis.

In this thesis, we consider three fundamental problems of transducers theory. The containment problem asks, given two transducers,whether the relation defined by the first is included into the relation defined by the second. The equivalence problem asks, given two transducers,whether they define the same relation. Finally, the sequential uniformisation problem,corresponding to the synthesis problem in the setting of transducers,asks, given a transducer, whether it is possible to deterministically pick an output correspondingto each input of its domain. These three decision problems are undecidable in general. As a first step, we consider different manners of recovering the decidability of the three problems considered.First, we characterise a family of classes of transducers, called controlled by effective languages, for which the containment and equivalence problems are decidable. Second, we add structural constraints to the problems considered: for instance, instead of only asking that two transducers define the same relation, we require that this relation is defined by both transducers in a similar way. This `similarity' is formalised through the notion of delay,used to measure the difference between the output production of two transducers. This allows us to introduce stronger decidable versions of our three decision problems, which we use to prove the decidability of the original problems in the setting of finite-valued transducers. In the second part, we study extensions of the automaton model,together with the adaptation of the sequential uniformisation problems to these new settings.Weighted automata are automata which,along each transition, output a weight in Z. Then, whereas a transducer preserves all the output mapped to a given input, weighted automata only preserve the maximal weight. In this setting, the sequential uniformisation problem turns into the determinisation problem: given a weighted automaton, is it possible to deterministically pick the maximal output mapped to each input? The decidability of this problem is open.The notion of delay allows us to devise a complete semi-algorithm deciding it. Finally, we consider two-way transducers, that are allowed to move back and forth over the input tape. These transducers enjoy good properties with respect to the sequential uniformisation problem: every transducer admits a sequential two-way uniformiser. We strengthen this result by showing that every transducer admits a reversible two-way uniformiser, i.e. a uniformiser that is both sequential and cosequential (backward sequential). / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

We extend earlier cellular automata models of spatially extended hypercycles by including an explicit genetic component into the model. This allows us to study the sequence evolution of hypercyclically coupled molecular replicators in addition to considering their population dynamics and spatial organization. In line with previous models, that considered either spatial organization or sequence evolution alone, we find both temporal oscillations of the relative concentration of the species forming the hypercycles as well as the formation of spatial organisations including spiral waves. We also confirm the greatly increased robustness of the spatially extended hypercycle against various classes of parasites. We find the sequence evolution of each of the hypercyclically coupled populations proceeds (after an inital selection-dominated phase) in a drift-like manner that can be described by a diffusion process in sequence space. Kimura's theory of neutral evolution is therefore applicable on long time-scales despite the fact that the hypercycle exhibits extreme periodic changes in population sizes and that are governed solely by frequency-dependent selection.

In order to identify complex systems capable of modeling artificial life, we study the notion of complexity within a class of dynamical systems called cellu- lar automata. We present a novel classification of cellular automata dynamics, which helps us identify interesting behavior in large automaton spaces. We give a detailed comparison of our results to previous methods of dynamics classification. In the second part of the thesis, we study the backward dynamics of cellular au- tomata. We present a novel representation of one-dimensional cellular automata, which can be used to charcterize all their garden of eden configurations. We demonstrate the usefulness of this method on examples. 1

This paper introduces and discusses automata systems as a new way for formal languages processing. In the text there are four models described. The first model works on sequential mode. At one computation step only one of components works. The second one works on semi-parallel mode. At the one computation step either one or all the components of the automata system work. In the last two models each component of the automata system has its own input string. The computation step of each component is influenced by their states, or used rules. The state, or used rule of the components of automata system can block or unblock some or all automata of the system.