Plante, Kristy and Jense, Tomas (2012) Computability theory & automata theory. College Publishing House, Delhi, India. ISBN 978-81-323-1266-6
Preview |
Text
KristyPlante2012_ComputabilityTheory&AutomataTheory.pdf - Published Version Download (2MB) | Preview |
Abstract
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability. In these areas, recursion theory overlaps with proof theory and effective descriptive set theory. The basic questions addressed by recursion theory are "What does it mean for a function from the natural numbers to themselves to be computable?" and "Can non-computable functions be classified into a hierarchy based on their level of noncomputability?". The answers to these questions have led to a rich theory that is still being actively researched. The field is also closely related to computer science. Recursion theorists in mathematical logic often study the theory of relative computability, reducibility notions and degree structures described here. This contrasts with the theory of subrecursive hierarchies, formal methods and formal languages that is common in the study of computability theory in computer science. There is considerable overlap in knowledge and methods between these two research communities, however, and no firm line can be drawn between them.
| Item Type: | Book |
|---|---|
| Subjects: | Q Science > Q Science (General) Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software |
| Divisions: | Electronic Books |
| Depositing User: | Practical Student 02 |
| Date Deposited: | 02 Nov 2021 08:46 |
| Last Modified: | 16 Aug 2022 04:30 |
| URI: | http://odlsystem2.utm.my/id/eprint/2330 |
Actions (login required)
 |
View Item |