Computer Science

Algebraic Computability and Enumeration Models
Recursion Theory and Descriptive Complexity

Cyrus F. Nourani, PhD

Algebraic Computability and Enumeration Models

Published. Available now.
Pub Date: March 2016
Hardback Price: $179.95 US
Hard ISBN: 9781771882477
E-Book ISBN: 9781771882484
Pages: 310 pages with index
Binding Type: hardback

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 view point. The reader is first introduced to categories and functorial models, with Kleene algebra examples for languages. Functorial models for Peano arithmetic are described toward important computational complexity areas on a Hilbert program, leading to computability with initial models. Infinite language categories are introduced also to explain descriptive complexity with recursive computability with admissible sets and urelements.

Algebraic and categorical realizability is staged on several levels, addressing new computability questions with omitting types realizably. Further applications to computing with ultrafilters on sets and Turing degree computability are examined. Functorial models computability are presented with algebraic trees realizing intuitionistic types of models. New homotopy techniques are applied to Marin Lof types of computations with model categories. Functorial computability, induction, and recursion are examined in view of the above, presenting new computability techniques with monad transformations and projective sets.

This informative volume will give readers a complete new feel for models, computability, recursion sets, complexity, and realizability. This book pulls together functorial thoughts, models, computability, sets, recursion, arithmetic hierarchy, filters, with real tree computing areas, presented in a very intuitive manner for university teaching, with exercises for every chapter. The book will also prove valuable for faculty in computer science and mathematics.

CONTENTS:
Preface
Chapter 1. Introduction

Chapter 2. Computing Categories, Language Fragments, and Models
2.1 Introduction
2.2 Limits and Infinitary Languages
2.3. Generic Functors and Language String Models
2.4 Fragment Consistent Algebras
2.5 Positive Consistency and Omitting Types
2.6 Positive Fragment Consistency Models
2.7 More on Kleene Structures

Chapter 3. Functorial Admissible Models
3.1 Infinitary Languages Basics
3.2 Admissible Languages
3.3 Admissible Models
3.4 Infinite Language Categories
3.5 A Descriptive Computing
3.6 Description Logic
3.7 High Fidelity Tree Computing

Chapter 4. Initial Tree Computing and Languages
4.1 Introduction
4.2 Initial Models and Their Algebraic Formulation
4.3 Tree Computing on Algebraic Theories
4.4 Tree Rewriting, Algebras, and Infinitary Models
4.5 Free Proof Trees and Computing Models
4.6 Word Problems and the SRS Roller Coaster
4.7 Concluding Comments

Chapter 5. Descriptive Sets and Infinitary Languages
5.1 Introduction
5.2 Admissible Sets and Structures
5.3 Basic Descriptive Characterizations
5.4 Boolean Valued Models
5.6. Admissible Sets and Ordinals
5.7 Set Reducibility
Chapter 6. Complexity and Computing
6.1 Introduction
6.2 Forcing, complexity, and Diophantine Definability
6.3 Technical Preliminaries
6.4 Positive Forcing and Infinitary Models
6.5 Complexity Classes, Models, and Urelements
6.6 Rudiments, KPU, and Recursion
6.7 Concrete Descriptive Complexity

Chapter 7. Arithmetic Hierarchy and Enumeration Degrees
7.1 Introduction
7.2 Turing Degrees and Isomorphism Types
7.3 Arithmetic Hierarchy on Infinitary Languages
7.4 Enumeration Computability Models
7.5 Computable Categorical Trees

Chapter 8. Peano Arithmetic Models and Computability
8.1 Introduction
8.2 Recursion on Arithmetic Fragments
8.3 Gödel Hierarchy and Arithmetic Fragments
8.4 More on Admissible and Finite Models
8.5 Fields, Fragments of Peano Arithmetic
8.6 Arithmetic, Borel Hierarchy, and Topological Structures
8.7 Infinitary Theories and Countable N Models
8.8 KPU Ordinal Models and Automata
8.9 Generic Computability and Filters
8.10 More on the Genericity, Priorities and R.E. Sets
8.10. Generic Computability and Filters

Chapter 9. Realizability and Computability
9.1 Introduction
9.2 Categorical Models and Realizability
9.3 Positive Realizability Morphisms and Models
9.4 Positive Categories and Consistency Models
9.5 Realizability on Ultrafilters
9.6 On PreSheaves Topos Realizability

Index


About the Authors / Editors:
Cyrus F. Nourani, PhD
Research Professor, Simon Fraser University, British Columbia, Canada; Academic R&D at Berlin, IMK Bonn, and Munich, Germany

Dr. Cyrus F. Nourani has a national and international reputation in computer science, artificial intelligence, mathematics, virtual haptic computation, information technology, and management. He has many years of experience in the design and implementation of computing systems. Dr. Nourani's academic experience includes faculty positions at the University of Michigan-Ann Arbor, the University of Pennsylvania, the University of Southern California, UCLA, MIT, and the University of California, Santa Barbara. He was also a Research Professor at Simon Frasier University in Burnaby, British Columbia, Canada. He was a Visiting Professor at Edith Cowan University, Perth, Australia, and a Lecturer of Management Science and IT at the the University of Auckland, New Zealand.

Dr. Nourani commenced his university degrees at MIT where he became interested in algebraic semantics. That was pursued with a category theorist at the University of California. Dr. Nourani’s dissertation on computing models and categories proved to have intuitionist forcing developments that were published from his postdoctoral times on at ASL. He has taught AI to the Los Angeles aerospace industry and has worked in many R&D and commercial ventures. He has written and co-authored several books. He has over 350 publications in mathematics and computer science and has written on additional topics, such as pure mathematics, AI, EC, and IT management science, decision trees, predictive economics game modeling. In 1987, he founded Ventures for computing R&D. He began independent consulting with clients such as System Development Corporation (SDC), the US Air Force Space Division, and GE Aerospace. Dr. Nourani has designed and developed AI robot planning and reasoning systems at Northrop Research and Technology Center, Palos Verdes, California. He also has comparable AI, software, and computing foundations and R&D experience at GTE Research Labs.




Follow us for the latest from Apple Academic Press:
Copyright © 2017 Apple Academic Press Inc. All Rights Reserved.