RecursionTheory/ Church-Turing Thesis - Couverture souple

Pierantozzi Sc D, Donald C.

9781089544272: RecursionTheory/ Church-Turing Thesis

Couverture souple

ISBN 10 : 1089544278 ISBN 13 : 9781089544272

Editeur : Independently published, 2019

Afficher les exemplaires de cette �dition comportant l?ISBN

0 D'occasion

1 Neuf

De EUR 32,25

Recursion theory (theory of computability) is a branch of mathematical logic studying the notion of computability from a rather theoretical point of view. This includes giving a lot of attention to what is not computable, or what is computable relative to any given, not necessarily computable, function. The subject is interesting on philosophical-scientific grounds because of the Church-Turing Thesis and its role in computer science, and because of the intriguing concept of Kolmogorov complexity. This paper tries to keep touch with how recursion theory actually impacts mathematics and computer science. This impact is small, but it does exist.The first section covers the basics: primitive recursion, partial recursive functions and the Church-Turing Thesis, arithmetization and the theorems of Kleene, the halting problem and Rice’s theorem, recursively enumerable sets, selections and reductions, recursive inseparability, and index systems. (Turing machines are briefly discussed, but the arithmetization is based on a numerical coding of combinators.)The second section is devoted to the remarkable negative solution (but with positive aspects) of Hilbert’s 10th Problem. This uses only the most basic notions of recursion theory, plus some elementary number theory that is worth knowing in any case; the coding aspects of natural numbers are combined here ingeniously with the arithmetic of the semiring of natural numbers.The last section is on Kolmogorov complexity, where concepts of recursion theory are used to define and study notions of randomness and information content. This also involves a bit of measure theory.Finally, the extended Church-Turing Thesis is examined.

Les informations fournies dans la section � Synopsis � peuvent faire r�f�rence � une autre �dition de ce titre.