Logical Approaches to Computational Barriers

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 systems.

websites: Arnold Beckmann | 2006-05-02 |