Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Questions Concerning the Usefulness of Small Universal Systems

Speaker: Liesbeth De Mol
Slot: Array, 11:10-11:30, col. 5


In the fifties and sixties of the 20th century, there seemed to have
been a small hype for finding the smallest possible universal Turing
machine. The last few years interest in this subject was triggered
again, partly due to the highly criticized book by Stephen Wolfram,
which, in its turn, gave rise to another kind of hype. Given this and
related work, the question concerning the significance of finding
shortest universal systems should at least be taken into
consideration again. It will be shown that it is far from trivial to
investigate the ``behaviour'' of universal systems within a
reasonable time and space, especially if one wants to consider other
systems than cellular automata. It will be argued that finding
(short) universal systems might be interesting iff. a certain
condition is fulfilled: when it is possible to generate
non-trivial ``behaviour'' for practically feasible initial
conditions. This discussion will be related to some  preliminary
research of the author on the possibility of universal binary tag

websites: Arnold Beckmann 2006-05-02