Computational and computer complexity of analogic cellular wave computers
Proceedings of the 2002 7th IEEE International Workshop on Cellular Neural Networks and Their Applications - Trang 323-338
Tóm tắt
Computational complexity and computer complexity issues are studied in different architectural settings. Three mathematical machines are considered: the universal machine on integers (UMZ), the universal machine on reals (UMR) and the universal machine on flows (UMF). The three machines induce different kinds of computational difficulties: combinatorial, algebraic, and dynamic, respectively. After a broader overview of computational complexity issues, it is shown, following the reasoning related the UMR, that in many cases the size is not the most important parameter related to computational complexity. Emerging new computing and computer architectures as well as their physical implementation suggest a new look at computational and computer complexities. The new analogic cellular array computer paradigm based on the CNN Universal Machine (generalized to UMF), and its physical implementation in CMOS and optical technologies, proves experimentally the relevance of the role of accuracy and problem parameter role in computational complexity, as well as the need of rigorous definition of computational complexity for UMF. It is also shown that choosing the spatial temporal elementary instructions, as well as taking into account the area and power dissipation, these choices inherently influence computational complexity and computer complexity, respectively. Comments related to biology relevance of the UMF are presented in relation to complexity theory. It is shown that algorithms using spatial-temporal continuous elementary instructions (a-recursive functions) represent not only a new world in computing, but also a more general type of logic inferencing.
Từ khóa
#Computational complexity #Turing machines #Physics computing #Optical arrays #CMOS technology #Biology computing #Computer aided instruction #Computer architecture #Optical computing #Cellular neural networksTài liệu tham khảo
2002, IEEE Int Solid-State Circuits Conf
10.1002/cta.204
10.1109/ISCAS.2000.856277
10.1002/(SICI)1097-007X(199901/02)27:1<171::AID-CTA47>3.0.CO;2-X
10.1109/81.780379
0, CNN software library
10.1109/81.222799
roska, 2001, Notes on the Complexity of Computations of Analogic Wave Computers, Report DNS-8-2001
szatmári, 2000, The Implementation of a Nonlinear Wave Metric for Image Analysis and Classification on the $64 \times 64$ analog I/O CNN-UM Chip, Proceedings of IEEE Int Workshop on Cellular Neural Networks and Their Applications (CNNA'2000), 395
10.1023/A:1008153320440
10.1038/35069068
werblin, 2001, Implementing a Retinal Visual Language in CNN: a Neuromprphic Case Study, Proc IEEE ISCAS 2001
10.1016/S0304-3975(98)00193-5
csuhaj-varju, 2001, Networks of language processors, In Current Trends in Theoretical Computer Science Entering the 21st Century, 771
prószéky, 1996, Syntax As Meta-morphology, Proceedings of of the 16th International Conference on Computational Linguistics (COLING-96), 2, 1123, 10.3115/993268.993381
prószéky, 2001, Psychological Reality and Mathematical Complexity in Computational Processing of Natural Languages, (Report under Publication)
roska, 2001, Analogic Wave Computers, Proc IEEE ISCAS 2001
10.1002/(SICI)1097-007X(199601/02)24:1<93::AID-CTA906>3.0.CO;2-M
liñán, 1999, A 0.5µm CMOS 106 Transistors Analog Programmable Array Processor for Real-Time Image Processing, Proc of the 1999 European Solid-State Circuits Conference, 358
10.1007/BF00332921
roska, 1999, Computer-Sensors: Spatial-Temporal Computers for Analog Array Signals, Dynamically Integrated with Sensors, Journal of VLSI Signal Processing, 23, 221, 10.1023/A:1008132715897
roska, 1988, Analog events and a dual computing structure using analog and digital circuits and oprators, Proc Discrete Event Systems Models and Applications 1987 (book Discrete Event Systems), 225
szatmari, 2000, The Implementation of a Nonlinear Wave Metric for Image Analysis and Classification on the $64 \times 64$ I/O CNN-UM Chip, Proceedings of IEEE Int Workshop on Cellular Neural Networks and Their Applications (CNNA'2000), 395
chua, 1998, CNN A Paradigm for Complexity, 10.1142/3801
heiligenberg, 1993, On biological sensory information processing principles relevant to cellular neural networks, Cellular Neural Networks, 201
10.1007/BF00375127
10.1137/1032043
blum, 1988, Complexity and Real Computation
10.1109/31.7600
10.1109/81.473590
10.1109/82.222815
gilli, 2001, CNN dynamics represents a broader class than PDEs, Report DNS-4-2001
roska, 2001, Toward the Visual Microprocessor-VLSI Design and the Use of Cellular Neural Network (CNN) Universal Machine Computers
petras, 2001, Novel spatial-temporal chaotic patterns and a prog-rammable, experimental, spatial-temporal bifurcation testbed, Report DNS-6-2001
10.1109/TIT.1974.1055172
chua, 2001, Cellular Neural Networks and Visual Computing
10.1109/81.224308
10.1109/81.747197