5th ed. — UK.: Cambridge University Press, 2007. — 350 p. — (ISBN10: 0-511-36668-X, ISBN13: 978-0-511-36668-0), eBook, English. Computability and Logichas become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as G¨ odel’s incompleteness theorems, but...
5th ed. — UK.: Cambridge University Press, 2007. — 350 p. — ISBN13: 978-0-521-70146-4. Computability and Logichas become a classic because of its accessibility to students without a mathematical background and because it covers not simply the staple topics of an intermediate logic course, such as G¨ odel’s incompleteness theorems, but also a large number of optional topics,...
Springer, 2021. — 444 p. — ISBN 978-3-030-59233-2. Computable analysis is the modern theory of computability and complexity in analysis that arose out of Turing's seminal work in the 1930s. This was motivated by questions such as: which real numbers and real number functions are computable, and which mathematical tasks in analysis can be solved by algorithmic means? Nowadays...
Springer, 2009. — 166 p.
Among all computer-generated mathematical images, Julia sets of rational maps occupy, perhaps, the most prominent position. Their beauty and complexity can be fascinating. They also hold a deep mathematical content, and numerical experiments have become a defining feature of the subject of Complex Dynamics.
Computational hardness of Julia sets is the...
North-Holland, 1989. — 611 p. The theme of this book is a pair of concepts, already recognised as belonging together by Leibniz, whose mathematical development from Frege to Turing has laid the theoretical foundation of computer science: the concept of formal language as carrier of the precise expression of meaning, facts , problems, and the concept of algorithm or calculus,...
New York: Springer, 2013. — 193 p. Aimed at mathematicians and computer scientists who will only be exposed to one course in this area, Computability: AMathematical Sketchbookprovides a brief but rigorous introduction to the abstract theory of computation, sometimes also referred to as recursion theory. It develops major themes in computability theory, such as Rice's theorem and...
Berlin: Walter de Gruyter, 2019. - 342 p. - (De Gruyter Series in Logic and Its Applications, 9). - ISBN: 3110495627. Ordinal Computability discusses models of computation obtained by generalizing classical models, such as Turing machines or register machines , to transfinite working time and space. In particular, recognizability, randomness , and applications to other areas of...
MIT Press, 2023. — 103 p. — ISBN13 9780262048620. — ISBN10 0262048620. A clear, comprehensive, and rigorous introduction to the theory of computation. What is computable? What leads to efficiency in computation? Computability and Complexity offers a clear, comprehensive, and rigorous introduction to the mathematical study of the capabilities and limitations of computation....
The MIT Press, 2023. — 416 р. — ISBN-13: 978-0262048620. A clear, comprehensive, and rigorous introduction to the theory of computation. What is computable? What leads to efficiency in computation? Computability and Complexity offers a clear, comprehensive, and rigorous introduction to the mathematical study of the capabilities and limitations of computation. Hubie Chen covers...
The MIT Press, 2023. — 416 р. — ISBN-13: 978-0262048620. A clear, comprehensive, and rigorous introduction to the theory of computation. What is computable? What leads to efficiency in computation? Computability and Complexity offers a clear, comprehensive, and rigorous introduction to the mathematical study of the capabilities and limitations of computation. Hubie Chen covers...
The MIT Press, 2023. — 416 р. — ISBN-13: 978-0262048620. A clear, comprehensive, and rigorous introduction to the theory of computation. What is computable? What leads to efficiency in computation? Computability and Complexity offers a clear, comprehensive, and rigorous introduction to the mathematical study of the capabilities and limitations of computation. Hubie Chen covers...
Boston: The MIT Press, 2013. — 366 p. In the 1930s a series of seminal works published by Alan Turing, Kurt Gödel, Alonzo Church, and others established the theoretical basis for computability. This work, advancing precise characterizations of effective, algorithmic computability, was the culmination of intensive investigations into the foundations of mathematics. In the...
Cambridge: Cambridge University Press, 2018. — 261 p. What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively...
Academic Press, 1983. — 435 p. Theoretical computer science is the mathematical study of models of computation. As such, it originated in the 1930s, well before the existence of modern computers, in the work of the logicians Church, Godel, Kleene, Post, and Turing. This early work has had a profound influence on the practical and theoretical development of computer science. Not...
Springer, 2024. — 360 p. — (Undergraduate Topics in Computer Science). — ISBN 3031537432. This is a book about computation, something which is ubiquitous in the modern world. More precisely, it examines computability theory and computational complexity theory. Computability theory is the part of mathematics and computer science which seeks to clarify what we mean by computation...
Springer, 2024. — 360 p. — (Undergraduate Topics in Computer Science). — ISBN 3031537432. This is a book about computation, something which is ubiquitous in the modern world. More precisely, it examines computability theory and computational complexity theory. Computability theory is the part of mathematics and computer science which seeks to clarify what we mean by computation...
Academic Press, 2010. - 192 pages. Computability Theory: An Introduction to Recursion Theory, provides a concise, comprehensive, and authoritative introduction to contemporary computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is...
3rd ed. — Advanced Reasoning Forum, 2008. — 377 p. — ISBN-10 098155072X, ISBN-13 978-0981550725. The classic presentation of the theory of computable functions in the context of the foundations of mathematics. Part I motivates the study of computability with discussions and readings about the crisis in the foundations of mathematics in the early 20th century, while presenting...
Springer Science & Business Media, 2009. — 188 p. A Concise Introduction to Computation Models and Computability Theory provides an introduction to the essential concepts in computability, using several models of computation, from the standard Turing Machines and Recursive Functions, to the modern computation models inspired by quantum physics. An in-depth analysis of the basic...
Second Edition. — Springer, 2012. — 315 p. The theory of computing provides computer science with concepts, models, and formalisms for reasoning about both the resources needed to carry out computations and the efficiency of the computations that use these resources. It provides tools to measure the difficulty of combinatorial problems both absolutely and in comparison with...
Издательство MIT Press, 1997, -484 pp. Unlike most fields within computer science, computability and complexity theory deals with analysis as much as with synthesis and with some concepts of an apparently absolute nature. Work in logic and recursive function theory spanning nearly the whole century has quite precisely delineated the concepts and nature of effective procedures,...
Springer, 2015. — 571 p. This book offers a self-contained exposition of the theory of computability in a higher-order context, where 'computable operations' may themselves be passed as arguments to other computable operations. The subject originated in the 1950s with the work of Kleene, Kreisel and others, and has since expanded in many different directions under the influence...
Springer, 2011. — 300 p. — ISBN: 978-0-85729-534-7. Presents a detailed introduction to the theory of computation, complete with concise explanations of the mathematical prerequisites. Provides end-of-chapter problems with solutions, in addition to chapter-opening summaries and numerous examples and definitions throughout the text. Draws upon the author’s extensive teaching...
Oxford University Press, 2009. — 450 p. The interplay between computability and randomness has been an active area of research in recent years, reflected by ample funding in the USA, numerous workshops, and publications on the subject. The complexity and the randomness aspect of a set of natural numbers are closely related. Traditionally, computability theory is concerned with the...
CRC Press, Apple Academic Press, Inc, 2016. — 304 p. — ISBN: 1771882476. This book, Algebraic Computability and Enumeration Models: Recursion Theory and Descriptive Complexity, presents new techniques with functorial models to address important areas on pure mathematics and computability theory from the algebraic viewpoint. The reader is first introduced to categories and...
Springer, 2025. — 388 p. This textbook aims to provide a comprehensive introduction to the theory of computation for upper-level undergraduate students and first-year graduate students in Computer Science and related disciplines. It covers a wide range of foundational topics essential for understanding the principles and applications of computation. The book begins with regular...
Springer, 2025. — 388 p. This textbook aims to provide a comprehensive introduction to the theory of computation for upper-level undergraduate students and first-year graduate students in Computer Science and related disciplines. It covers a wide range of foundational topics essential for understanding the principles and applications of computation. The book begins with regular...
Springer Cham, 2023. — 252 p. — (Theory and Applications of Computability) — eBook ISBN: 978-3-031-34827-3. It is not always clear what computer programs mean in the various languages in which they can be written, yet a picture can be worth 1000 words, a diagram 1000 instructions. In this unique textbook/reference, programs are drawn as string diagrams in the language of...
Chapman and Hall/CRC, 2012. — 277 p. Limits of Computation: An Introduction to the Undecidable and the Intractable offers a gentle introduction to the theory of computational complexity. It explains the difficulties of computation, addressing problems that have no algorithm at all and problems that cannot be solved efficiently. The book enables readers to understand: What does...
Amsterdam: Mathematical Centre, 1982. — (MC Varia). — ISBN: 90-6196-234-X. The book contains a comprehensive bibliography of lambda-calculi (with and without types), combinatory logics and closely related topics up to 1982.
2nd edition. — Berlin: Springer, 2020. — xxii, 422 p. — ISBN: 978-3-662-62420-3, 978-3-662-62421-0. This book offers an original and informative view of the development of fundamental concepts of computability theory. The treatment is put into historical context, emphasizing the motivation for ideas as well as their logical and formal development. In Part I the author...
Springer, 2015. — 341 p. — ISBN: 978-3-662-44807-6. This book offers an original and informative view of the development of fundamental concepts of computability theory. The treatment is put into historical context, emphasizing the motivation for ideas as well as their logical and formal development. In Part I the author introduces computability theory, with chapters on the...
Springer, 2009. — 428 p. The foundation of computer science is built upon the following questions: What is an algorithm? What can be computed and what cannot be computed? What does it mean for a function to be computable? How does computational power depend upon programming constructs? Which algorithms can be considered feasible? For more than 70 years, computer scientists are...
New York: Springer, 2016. - 300p. Turing's famous 1936 paper introduced a formal definition of a computing machine, a Turing machine. This model led to both the development of actual computers and to computability theory, the study of what machines can and cannot compute. This book presents classical computability theory from Turing and Post to current results and methods, and...
Springer, 2022. - 651 p. - ISBN 3030832015. This survey of computability theory offers the techniques and tools that computer scientists (as well as mathematicians and philosophers studying the mathematical foundations of computing) need to mathematically analyze computational processes and investigate the theoretical limitations of computing. Beginning with an introduction to...
2-е изд., испр. — М.: Интуит, 2016. — 170 с. Скан. Курс написан по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В нем рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке,...
М.: Физматлит, 2006. — 296 с. Книга является учебным пособием по теории рекурсии в аспекте ее применения в области программирования. В ней рассматриваются основы теории рекурсии, и ее использование в области разработки и анализа рекурсивных алгоритмов. Приводятся основные сведения о рекурсивных последовательностях и функциях, даны примеры рекурсивных алгоритмов, разработанных...
Учебное пособие. — Омск: изд-во ОмГУ, 2016. — 152 с. — ISBN: 978-5-7779-1977-9. Излагаются элементы современной теории синтетической вычислимости. Дается представление об алгоритмах, рекурсивных функциях, интуиционизме, интуиционистской логике, конструктивной математике, реализуемости Клини, теории категорий, теории топосов, топосе реализуемости и др. Описываются эффективный...
Новосибирск: Научная книга, 1996. — 300 с. — (Сибирская школа алгебры и логики) Книга открывает учрежденную в 1995 г. Сибирским фондом алгебры и логики математическую книжную серию под редакцией академика Ю. Л. Ершова. Все книги серии издаются одновременно на английском языке издательством Plenum Publishing Corporation. В книге дается новое доказательство теоремы Гёделя о...
Перевод с англ. А. А. Мучника под ред. С. Ю. Маслова. — М.: Мир, Редакция литературы по математическим наукам, 1983. — 255 с. Книга известного английского математика, охватывающая основные вопросы теории вычислимых функций и ее приложений: сложность вычислений и алгоритмов, теоремы Гёделя о неполноте и Чёрча о неразрешимости, семантику языков программирования. Изложение замкнутое,...
Издательство Мир, 1970. — 432 с. Сборник переводов. Сборник содержит работы по актуальным проблемам математической логики, еще не получившим достаточного освещения в отечественной литературе. Эти работы посвящены оценкам сложности алгоритмов и вычислений, классификациям рекурсивных функций и различным типам вычислительных устройств, связанных с такими классификациями. В...
Учебное пособие. — Ярославль: ЯрГУ, 2006. — 140 с. В пособии в рамках теории вычислительных процессов и структур рассматриваются два направления теоретической информатики (теорети ческого программирования): теория схем программ и теория семантики и верификации программ. В первом разделе излагаются основы теории (стандартных) схем программ, математических моделей, отражающих...
М.: Физматлит, 2007. — 64 с. — ISBN: 978-5-9221-0825-6. Брошюра знакомит читателя с алгоритмически вычислимыми функциями натурального аргумента — рекурсивными функциями. Вначале изучается простейший тип рекурсивных функций — примитивно рекурсивные функции. Затем происходит расширение круга вычислимых функций: рассматриваются частично определенные вычислимые функции, а также...
Учебное пособие. Новосибирск: НГУ, 2005. 114 с. Данная книга - изложение курса лекций по теории алгоритмов, читанного автором на математическом факультете Новосибирского госуниверситета в 2001-2003 годах. Задача учебника - дать хорошее интуитивное понимание математического понятия алгоритма и служить введением для дальнейшего изучения других руководств по теории алгоритмов, а...
Новосибирск: НГУ, 2005. – 102 с. Нумерации. Вычислимые нумерации. Вычислимые нумерации конечных семейств и конечных частично упорядоченных множеств. m-сводимость и 1-сводимость. Иерархия Ершова. Табличные сводимости. Вычислимость с оракулом и сводимость по Тьюрингу. Универсальные функции и операция скачка. Арифметическая иерархия. Конструктивные ординалы.
Перевод с английского В.А.Душского, М.И.Кановича, Е.Ю.Ногиной. Под редакцией В.А.Успенского. — М.: Мир, 1972. — 624 с. Книга содержит изложение современного состояния теории рекурсивных функций и обзор основных приложений этой теории. В ней прослежено развитие теории рекурсивных функций, начиная с ее зарождения в тридцатых годах и кончая результатами исследований самых последних...
М.: Государственное издательство физико-математической литературы, 1960. — 492 с.
Понятия алгоритма и вычислимой функции являются одними из центральных понятий современной математики. Их роль в математике середины XX в. можно, пожалуй, сравнить с ролью понятия множества в математике конца XIX в. Настоящие «Лекции» посвящены изложению основ теории вычислимых функций (проводимому...
М.: Государственное издательство физико-математической литературы, 1960. - 492 с.
Понятия алгоритма и вычислимой функции являются одними из центральных понятий современной математики. Их роль в математике середины XX в. можно, пожалуй, сравнить с ролью понятия множества в математике конца XIX в. Настоящие «Лекции» посвящены изложению основ теории вычислимых функций (проводимому...
Перевод с немецкого Э. Г. Белаги. — Москва: Мир, 1972. — 264 с. — (Современная математика). В соответствии с принципом «Selecta Mathematica» в этом томике все существенные результаты сопровождаются полными доказательствами. Тем самым мы надеемся дать читателям основательное представление о мире абстрактных автоматов и побудить их познакомиться и с практическими аспектами...
Перевод с немецкого Э. Г. Белаги. — М.: Мир, 1972. — 264 с. — (Современная математика). В соответствии с принципом «Selecta Mathematica» в этом томике все существенные результаты сопровождаются полными доказательствами. Тем самым мы надеемся дать читателям основательное представление о мире абстрактных автоматов и побудить их познакомиться и с практическими аспектами теории....
Комментарии