Number of the records: 1
On the Super-Turing Computational Power of Non-Uniform Families of Neuromata
- 1.0404856 - UIVT-O 20020216 RIV CZ eng J - Journal Article
Wiedermann, Jiří
On the Super-Turing Computational Power of Non-Uniform Families of Neuromata.
Neural Network World. Roč. 12, č. 5 (2002), s. 509-516. ISSN 1210-0552.
[SOFSEM 2002 Workshop on Soft Computing. Milovy, 28.11.2002-29.11.2002]
R&D Projects: GA ČR GA201/00/1489
Institutional research plan: AV0Z1030915
Keywords : neuromata * Turing machines with advice * non-uniform computational complexity * super-Turing computational power
Subject RIV: BA - General Mathematics
It is shown that the computational power of non-uniform infinite families of (discrete) neural nets reading their inputs sequentially (so-called neuromata), of polynomial size, equals to PSPACE/poly, and of logarithmic size to LOGSPACE/log. Thus, such families posses super-Turing computational power. From computational complexity point of view the above mentioned results rank the respective families of neuromata among the most powerful computational devices known today.
Permanent Link: http://hdl.handle.net/11104/0003461
Number of the records: 1