Computability and Non-computability Issues in Amorphous Computing

摘要: Amorphous computing systems consist of a huge set tiny simple stationary or mobile processors whose computational, communication and sen- sory part is reduced to an absolute minimum. In airborne medium the pro- cessors communicate via short-range radio while in waterborne molecular communication. some cases computational proces- sors can be simplified down finite state automata even combinatorial circuits system as whole still possess universal power with high probability. We will argue that amorphous belong among simplest (non-uniform) devices. On other hand, it questionable what extent standard models computation faithfully capture behavior function- ality also depends on non-computational and/or unpredictable operations certain parts entire system.