1. On the super-turing computational power of non-uniform families of neuromata
- Creator:
- Wiedermann, Jiří
- Format:
- bez média and svazek
- Type:
- model:article and TEXT
- Subject:
- neuromata, Turing machines with advice, non-uniform computational complexity, and super-Turing computational power
- Language:
- English
- Description:
- It is shown that tlie computational power of iion-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/loy. Thus, such farnilies posses super-Turiug 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.
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public