1st Edition

Algebraic Computability and Enumeration Models Recursion Theory and Descriptive Complexity

By Cyrus F. Nourani Copyright 2016
    310 Pages
    by Apple Academic Press

    310 Pages
    by Apple Academic Press

    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 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 also introduced 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 is 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.

    Preface

    Introduction

    Computing Categories, Language Fragments, and Models

    Introduction

    Limits and Infinitary Languages

    Generic Functors and Language String Models

    Positive Generic Models

    Fragment Consistent Algebras

    Generic Products

    Positive Morphisms and Models

    Positive Consistency and Omitting Types

    Positive Fragment Consistency Models

    Horn Models

    Positive Categories and Horn Fragments

    Fragment Consistent Kleene Models

    More on Kleene Structures

    Process Algebras

    Functorial Admissible Models

    Infinitary Languages Basics

    Admissible Languages

    Admissible Models

    Infinite Language Categories

    A Descriptive Computing

    Computing Model Diagrams

    Situations and Compatibility

    Boolean Computing Diagrams

    Description Logic

    Functorial Model Theory and HIFI Computing

    Generic Functor Initial Models

    Initial Tree Algebras and Amplification

    Tree Amplifiers and The Sonic Booms

    The Recursion Theorem

    Tree Amplifiers and Recursion

    Admissible Gain Synthesizer

    Initial Tree Computing and Languages

    Initial Models and Their Algebraic Formulation

    The Basics

    Canonical Models

    Generic diagrams of Initial Models

    Initial Algebras and Computable Trees

    Tree Rewriting, Algebras, and Infinitary Models

    Are There Models for Nothing

    Free Proof Trees and Computing Models

    Generating Models by Positive Forcing

    Algebraically Closed Groups

    Word Problems and the SRS Roller Coaster

    The Roller Coaster

    Private Languages and Wittgenstein’s Paradox

    Concluding Comments

    Descriptive Sets and Infinitary Languages

    Introduction

    Admissible Sets and Structures

    Basic Descriptive Characterizations

    Boolean Valued Models

    Admissible Sets and Ordinals Error! Bookmark not defined.

    Set Reducibility

    Admissible Tree Recursion

    Admissible Set Reducibility

    Complexity and Computing

    Introduction

    Forcing, Complexity, and Diaphontine Definability

    Technical Preliminaries

    Initial Models

    Generic Diagrams for Initial Models

    Models and Fragment Inductive Closure

    Positive Forcing and Infinitary Models

    Generating Models by Positive Forcing

    Forcing and Computability

    Complexity Classes, Models, and Urlements

    Functorial Implicit Complexity Error! Bookmark not defined.

    Abstract Descriptive Complexity

    A Descriptive Computing Example Revisit

    Rudiments, KPU, and Recursion

    Admissible Hulls

    Concrete Descriptive Complexity

    Concrete Implicit Complexity

    Overview to Arithmetic Hierarchy

    Arithmetic Hierarchy and Enumeration Degrees

    Introduction

    Turing Degrees and Isomorphism Types

    Arithmetic Hierarchy and Infinitary Languages

    Computability and Hierarchy with Infinitary Languages

    Computability on Infinitary Languages

    Enumeration Degrees

    Enumeration Definability and Turing Jumps

    Automorphisms and Lifts on K-Pairs

    Enumeration Computability Models

    Rudiments, KPU, and Recursion

    Computable Categorical Trees

    Enumerations Model Theory

    Peano Arithmetic Models and Computability

    Introduction

    Recursion on Arithmetic Fragments

    Godel’s Incompleteness and Ordinal Arithmetic

    Descriptive Sets and Automata

    Finite Models

    Fields and Fragments of Peano Arithmetic

    Arithmetic Hierarchy and Borel Sets

    Infinitary Theories and c=Countable N Models

    KPU Ordinal Models

    Generic Computability and Filters

    Realizability and Computability

    Introduction

    Categorical Models and Realizability

    Categorical Intuitionistic Models

    Infinitary Language Product Models

    Positive Generic Models

    Omitting Types Realizability

    Positive Realizability Morphisms and Models

    Fragment Product Algebra Realizability

    Positive Realizability on Horn Filters

    Computability and Positive Realizability

    Morphic Realization Functors

    Positive Categories and Consistency Models

    Horn Computability and Realizability

    Intuitionistic Types and Realizability

    Realizability on Ultrafilters

    Computing Morphisms on Topos

    Relative Realizability on Topos

    Realizability Triposes

    More on Topos Realizability

    On PreSheaves Topos Realizability

    Index

    Biography

    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 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 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 authored 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.

    One of the 14 Best-Selling Recursion Theory eBooks of All Time by BookAuthority