Jiří Wiedermann (Prague)
Computability and Non-Computability Issues in Amorphous Computing

Amorphous computing systems can be seen as extreme cases of wireless communicating networks. They consist of a huge set of tiny simple stationary or mobile processors whose computational, communication and sensory part is reduced to an absolute minimum. In an airborne medium the processors communicate via a short range radio while in a waterborne medium via molecular communication. In some cases the computational part of the processors can be simplified down to probabilistic finite state automata and the system as a whole can still possess universal computational power with a high probability. Thus, the resulting amorphous systems belong among the simplest (non-uniform) universal computational devices since their functionality is fully defined by any of their processors and there is no need to describe the ``architecture" of the system as a whole. An interesting question arises in the reverse simulation of amorphous computing systems by Turing machines. Namely, operation of certain amorphous computing systems also depends on abilities of their processors and those of their environment that are of non-computational nature. Therefore, it is questionable as to what extent the Church-Turing thesis covers the case of such amorphous computing systems.