350 руб
Журнал «Нейрокомпьютеры: разработка, применение» №6 за 2010 г.
Статья в номере:
Гибридная модель процесса вычислений: обобщение концепции машины Тьюринга
Ключевые слова: машина Тьюринга гибридная модель память
Авторы:
О. Н. Граничин - д. ф.-м. н., проф. кафедры системного программирования математико-механического факультета, СПбГУ, зав. лаб. стохастических вычислительных систем института информационных технологий. E-mail: Oleg_granichin@mail.ru В. И. Васильев - аспирант каф. СПбГУ. E-mail: gnome@bk.ru
Аннотация:
Предложена новая концепция вычислительного устройства, обобщающая схему классической машины Тьюринга. В рамках новой модели переосмысливаются ставшие традиционными понятия «такта» , «памяти» , «программы» и «состояния». Память представляет собой модель динамической системы, программа» - «скачкообразное» эволюцию памяти по достижении терминальных множеств, а «тактом» считается достижение терминальных множеств. Кроме того рассматривается динамика взаимодействия параллельных динамических систем с общей памятью в применении к такой модели. Представленная концепция упрощает и обобщает описанную ранее.
Страницы: 51-58
Список источников
  1. Moore, H.,Electronics, 38. 1965.
  2. Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. 1936. 2. 230-265.
  3. Feynman, R., Modeling of physics on computers // International Journal of Theoretical Physics, 21. 1982.
  4. Deutsch, D., Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer // Proceedings of the Royal Society: series A, 1985. 97-117.
  5. Church, A., A note on the Entscheidung problem // Journal of Symbolic Logic. 1936. 1. 56-68.
  6. Copeland, J. B., The Church-Turing thesis // NeuroQuantology. 2004.2. 101-115.
  7. da Costa,N.C.A. and Doria, F.A., Classical Physics and Penrose's Thesis // Foundations of Physics Letters. 1991. 4. 363-374.
  8. Doyle, J., What is Church-s Thesis - An Outline. Laboratory for Computer Science, MIT. 1982.
  9. Hogarth, M. L., Non-Turing computers and Non-Turing computability // PSA 1994, 1, 126-138.
  10. Gao, Y. G., Lygeros, J., and Quincampoix, M., On the reachability problem for uncertain hybrid systems //IEEE Transactions on Automatic Control.2007. 52(9). 1572-1586.
  11. Goebel, R., Sanfelice, R., G., and Teel, A. R., Hybrid dynamical systems // IEEE Control Systems Magazine.2009. 29(2). 28-93.
  12. Shor, P., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAMJ. Comput. 26, 1997. 1484-1509.
  13. Tien, D. K., Computing the non-computable // Contemporary Physics, 2003. 44. 51-71.
  14. Граничин О. Н., Жувикова И. А., Новая модель процесса вычислений, основанная на эволюционных примитивах: обобщение концепции машины Тьюринга // Нейрокомпьютеры: разработка, применение. 2006.
  15. Hopcroft, J.E., and Ullman, J. D., Introduction to Automata Theory, Languages, and Computation. 1979.
  16. Granichin, O. N., and Khantuleva, T. A., Hybrid systems and randomized measuring in nonequilibrium processes // Differential Equation and Control Processes. 2004.3.
  17. Granichin, O. N., Linear regression and filtering under nonstandard assumptions (Arbitrary noise)// IEEE Transactions on Automatic Control.2004. 49 (10). 1830-1835.
  18. Граничин О. Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука. 2003.