Computability in Europe 2006
Logical Approaches to Computational Barriers
|Speaker:||Liesbeth De Mol|
|Slot:||Mon, 11:10-11:30, Faraday J (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||
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie06/conf-code.php on line 135