Аннотация:
В настоящем обзоре приводятся различные теоремы (полученные в основном специалистами по математической логике и теории алгоритмов), устанавливающие невозможность алгоритмов для решения тех или иных диофантовых проблем. Техника, развитая для получения таких “отрицательных” результатов, зачастую позволяет доказать и много “положительных” теорем о возможности сформулировать диофантовы проблемы со специальными свойствами. В этом обзоре приведен также ряд вопросов, остающихся открытыми.
Образец цитирования:
Ю. В. Матиясевич, “Что можно и что невозможно делать с диофантовыми проблемами”, Классическая и современная математика в поле деятельности Бориса Николаевича Делоне, Сборник статей. К 120-летию со дня рождения члена-корреспондента АН СССР Бориса Николаевича Делоне, Труды МИАН, 275, МАИК «Наука/Интерпериодика», М., 2011, 128–143; Proc. Steklov Inst. Math., 275 (2011), 118–132
\RBibitem{Mat11}
\by Ю.~В.~Матиясевич
\paper Что можно и что невозможно делать с~диофантовыми проблемами
\inbook Классическая и современная математика в~поле деятельности Бориса Николаевича Делоне
\bookinfo Сборник статей. К~120-летию со дня рождения члена-корреспондента АН СССР Бориса Николаевича Делоне
\serial Труды МИАН
\yr 2011
\vol 275
\pages 128--143
\publ МАИК «Наука/Интерпериодика»
\publaddr М.
\mathnet{http://mi.mathnet.ru/tm3346}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2962974}
\elib{https://elibrary.ru/item.asp?id=17238819}
\transl
\jour Proc. Steklov Inst. Math.
\yr 2011
\vol 275
\pages 118--132
\crossref{https://doi.org/10.1134/S0081543811080074}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000305482400007}
\elib{https://elibrary.ru/item.asp?id=18034681}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84856460810}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/tm3346
https://www.mathnet.ru/rus/tm/v275/p128
Эта публикация цитируется в следующих 3 статьяx:
Bondar D.I., Pechen A.N., “Uncomputability and Complexity of Quantum Control”, Sci Rep, 10:1 (2020), 1195
Gillibert P., Ranieri G., “Julia Robinson Numbers”, Int. J. Number Theory, 15:8 (2019), 1565–1599
Lindstrom T., “Problems in Relating Various Tasks and Their Sample Solutions To Bloom'S Taxonomy”, Math. Enthus., 14:1-3 (2017), 15–27