Catálogo de publicaciones - libros

We present small polynomial time universal Turing machines with state-symbol pairs of (5,5), (6,4), (9,3) and (18,2). These machines simulate our new variant of tag system, the bi-tag system and are the smallest known universal Turing machines with 5, 4, 3 and 2-symbols respectively. Our 5-symbol machine uses the same number of instructions (22) as the smallest known universal Turing machine by Rogozhin.

In place of the traditional definition of a cellular automaton  = (, , , ), a new definition (, , , ) is given by introducing an injection called : {0, 1,..., − 1}→, which provides a connection between the variables of local function of arity and neighbors of CA: image() is a neighborhood of size . The new definition allows new analysis of cellular automata. We first show that from a single local function countably many CA are induced by changing and then prove that equivalence problem of such CA is decidable. Then we observe what happens if we change the neighborhood. As a typical research topics, we show that reversibility of 2 states 3 neighbors CA is preserved from changing the neighborhood, but that of 3 states CA is not.

A variant of Circuit Value Problem over the basis of Peirce’s arrow (NOR) is introduced, in which one of the inputs of every -th gate must be the ( − 1)-th gate. The problem, which remains -complete, is encoded as a simple formal language over a two-letter alphabet. It is shown that this language can be naturally and succinctly represented by language equations from several classes. Using this representation, a small conjunctive grammar and an even smaller LL(1) Boolean grammar for this language are constructed.

Inspired by genetic programming (GP), we study iterative algorithms for non-computable tasks and compare them to naive models. This framework justifies many practical standard tricks from GP and also provides complexity lower-bounds which justify the computational cost of GP thanks to the use of Kolmogorov’s complexity in bounded time.

An existence or non-existence of five-state firing squad synchronization protocol has been a long-standing, famous open problem for a long time. In this paper, we answer partially to this problem by proposing a smallest five-state firing squad synchronization algorithm that can synchronize any one-dimensional cellular array of length  = 2 in 3 − 3 steps for any positive integer . The number is the smallest one known at present in the class of synchronization protocols proposed so far.

We present two small universal Turing machines that have 3 states and 7 symbols, and 4 states and 5 symbols respectively. These machines are semi-weak which means that on one side of the input they have an infinitely repeated word and on the other side there is the usual infinitely repeated blank symbol. This work can be regarded as a continuation of early work by Watanabe on semi-weak machines. One of our machines has only 17 transition rules making it the smallest known semi-weakly universal Turing machine. Interestingly, our two machines are symmetric with Watanabe’s 7-state and 3-symbol, and 5-state and 4-symbol machines, even though we use a different simulation technique.

We present a new family of solutions to the firing squad synchronization problem. All these solutions are built with a few finite number of signals, which lead to simple implementations with 7 or 8 internal states. Using one of these schemes we are able to built a 7-states -steps solution to the firing squad synchronization problem. These solutions not only solves the unrestricted problem (initiator at one of the two ends), but also the problem with initiators at both ends and the problem on a ring.