Post Three-Valued Computation

SUI Yuefei

PREFACE

Many-valued (multi-valued) logic has a long history in logic. Zach's thesis seems terminate the study of many-valued logic. Many-valued computations are an interesting goal to be reached.

   Computation is defined in standard model of binary-valued Peano arithmetic.

 To define computation in Post three-valued logic, L₃-valued preprimitively computable functions, L₃-valued primitively computable functions, L₃-valued pre-partially computable functions and L₃-valued partially  computable functions are defined, and correspondingly, L₃-valued precomputably enumerable sets and L₃-valued computably enumerable sets are defined. Halting problems for t and m are defined and shown to be not L₃-valued computable.

  L₃-valued Turing machines, L₃-valued Turing degrees will be defined and it will be shown that the upper-semilattice of all the L₃-valued precomputably/computably enumerable Turing degrees has L₃-valued pre-simple/simple degrees and L₃-valued minimal pairs.

  These statements show the appropriateness of the definition of L₃-valued

computation in some ways.

Sui Yuefei

2024,10,30

Contents

1 Introduction 81.

  1 Post three-valued logic . . . . . . . . . . . . . . . . . . . . . . 8 

  1.2 B2-valued computation . . . . . . . . . . . . . . . . . . . . . 9 

  1.3 L3-valued computable functions . . . . . . . . . . . . . . . . . 10 

    1.3.1 L3-valued pre-primitively computable functions . . . . 10 

    1.3.2 L3-valued primitively computable functions . . . . . . 11 

    1.3.3 L3-valued pre-partially computable functions . . . . . 13 

    1.3.4 L3-valued partially computable functions . . . . . . . 14 

  1.4 L3-valued computably enumerable sets . . . . . . . . . . . . . 16 

  1.5 L3-valued Turing degrees . . . . . . . . . . . . . . . . . . . . 16 

  1.6 Full L3-valued computable functions . . . . . . . . . . . . . . 17 

  1.7 Notions in computability . . . . . . . . . . . . . . . . . . . . . 19

2 Basic computability theory 23

  2.1 First-order logic . . . . . . . . . . . . . . . . . . . . . . . . . . 23 

    2.1.1 Deduction systems . . . . . . . . . . . . . . . . . . . . 24 

    2.1.2 Deduction system T2 . . . . . . . . . . . . . . . . . . 25 

  2.2 Arithmetic theory . . . . . . . . . . . . . . . . . . . . . . . . 26 

    2.2.1 Logical languages . . . . . . . . . . . . . . . . . . . . . 26 

    2.2.2 Axioms for Peano arithmetic . . . . . . . . . . . . . . 27 

    2.2.3 Standard model . . . . . . . . . . . . . . . . . . . . . . 27 

  2.3 Computability . . . . . . . . . . . . . . . . . . . . . . . . . . 28 

    2.3.1 Primitively computable functions . . . . . . . . . . . . 28 

    2.3.2 Turing machines . . . . . . . . . . . . . . . . . . . . . 30 

    2.3.3 Halting problem . . . . . . . . . . . . . . . . . . . . . 32 

    2.3.4 Partially computable functions . . . . . . . . . . . . . 32 

  2.4 Turing degrees . . . . . . . . . . . . . . . . . . . . . . . . . . 36 

    2.4.1 Relative Turing machines . . . . . . . . . . . . . . . . 36 

    2.4.2 Turing reducibility and Turing degrees . . . . . . . . . 37 

    2.4.3 Definablity . . . . . . . . . . . . . . . . . . . . . . . . 38 

  2.5 Turing-degree theory . . . . . . . . . . . . . . . . . . . . . . . 39 

    2.5.1 Turing degrees . . . . . . . . . . . . . . . . . . . . . . 39 

    2.5.2 Simple sets . . . . . . . . . . . . . . . . . . . . . . . . 40 

  2.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3  B2-valued computability theory 44

  3.1 B2-valued first-order logic . . . . . . . . . . . . . . . . . . . . 45 

    3.1.1 Deduction system T20 . . . . . . . . . . . . . . . . . . 47 

    3.1.2 Equivalence of T2 and T20 . . . . . . . . . . . . . . . . 49 

  3.2 Arithmetic theory . . . . . . . . . . . . . . . . . . . . . . . . 50 

    3.2.1 Logical languages . . . . . . . . . . . . . . . . . . . . . 50 

    3.2.2 Peano axioms . . . . . . . . . . . . . . . . . . . . . . . 52 

    3.2.3 Standard model N20 . . . . . . . . . . . . . . . . . . . 53 

  3.3 Computability theory . . . . . . . . . . . . . . . . . . . . . . 53 

    3.3.1 B2-valued computable functions . . . . . . . . . . . . 53 

    3.3.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 55 

    3.3.3 B2-valued Turing machines . . . . . . . . . . . . . . . 56 

    3.3.4 Halting problem . . . . . . . . . . . . . . . . . . . . . 57 

    3.3.5 Basic properties of B2-valued computable functions . 57 

    3.3.6 B2-valued definability . . . . . . . . . . . . . . . . . . 58 

    3.3.7 Computably enumerable sets . . . . . . . . . . . . . . 60 

  3.4 B2-valued Turing-Degrees . . . . . . . . . . . . . . . . . . . . 61 

  3.5 Turing-Degree theory . . . . . . . . . . . . . . . . . . . . . . . 61 

    3.5.1 Simple sets . . . . . . . . . . . . . . . . . . . . . . . . 63 

    3.5.2 Co-simple sets . . . . . . . . . . . . . . . . . . . . . . 65 

  3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

4  L3-valued primitively computable functions 69

  4.1 L3-valued pre-primitively computable functions . . . . . . . . 69 

  4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 

  4.3 Some L3-valued pre-primitively computable functions and relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 

  4.4 Diagonalization . . . . . . . . . . . . . . . . . . . . . . . . . . 76 

  4.5 De-valued L3-valued pre-primitively computable functions . . 78 

  4.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5 Theory of L3-valued pre-p. r. functions 81

  5.1 PRA theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 

  5.2 Basic L3-valued pre-primitively recursive functions . . . . . . 82 

  5.3 Properties of basic L3-valued pre-primitively recursive functions and relations . . . . . . . . . . . . . . . . . . . . . . . . 85 

  5.4 Coding finite sets and sequences . . . . . . . . . . . . . . . . 88 

  5.5 First-order arithmeic . . . . . . . . . . . . . . . . . . . . . . . 93 

  5.6 Definition of truth . . . . . . . . . . . . . . . . . . . . . . . . 97 

  5.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

6 L3-valued first-order logic 102

  6.1 Logical language . . . . . . . . . . . . . . . . . . . . . . . . . 102 

    6.1.1 Deduction system T3 . . . . . . . . . . . . . . . . . . 104 

  6.2 Cut elimination theorem . . . . . . . . . . . . . . . . . . . . . 109 

  6.3 Peano axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 

  6.4 Standard model N3 . . . . . . . . . . . . . . . . . . . . . . . . 116 

  6.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

7 L3-valued computable functions 119

  7.1 L3-valued pre-partially computable functions . . . . . . . . . 120 

  7.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 

  7.3 Reduction to B2-valued pre-partially computable functions . 123 

  7.4 L3-valued Turing machines . . . . . . . . . . . . . . . . . . . 124 

  7.5 Properties of L3-valued pre-partially computable functions . . 126 

  7.6 L3-valued partially computable functions . . . . . . . . . . . 128 

  7.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

8 L3-valued computably enumerable sets 131

  8.1 L3-valued pre-c. e. sets . . . . . . . . . . . . . . . . . . . . . . 131 

  8.2 L3-valued s-m-n theorem . . . . . . . . . . . . . . . . . . . . . 133 

  8.3 L3-valued c. e. sets . . . . . . . . . . . . . . . . . . . . . . . . 135 

  8.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

9 Turing degrees 144

  9.1 Relatived L3-valued Turing machines . . . . . . . . . . . . . . 144 

  9.2 L3-valued Turing-Degrees . . . . . . . . . . . . . . . . . . . . 146 

  9.3 L3-valued computably enumerable degrees . . . . . . . . . . . 147 

  9.4 L3-valued pre-simple and simple set pairs . . . . . . . . . . . 149 

    9.4.1 L3-valued simple set pairs . . . . . . . . . . . . . . . . 149 

    9.4.2 L3-valued pre-simple set pairs . . . . . . . . . . . . . . 150 

    9.4.3 L3-valued simple set pairs . . . . . . . . . . . . . . . . 153 

  9.5 L3-valued pre-minimal pairs and minimal pairs . . . . . . . . 156 

    9.5.1 L3-valued pre-minimal pairs . . . . . . . . . . . . . . . 157 

    9.5.2 Lt3-pre-minimal pairs . . . . . . . . . . . . . . . . . . . 157 

    9.5.3 L3-valued minimal pairs . . . . . . . . . . . . . . . . . 160 

  9.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

10 L2+2-valued computability theory 166

  10.1 B2+2-valued first-order logic . . . . . . . . . . . . . . . . . . . 168 

    10.1.1 Deduction system T2+2 . . . . . . . . . . . . . . . . . 170 

    10.1.2 Equivalence of T3 and T2+2 . . . . . . . . . . . . . . . 172 

  10.2 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 

  10.3 Peano axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 

    10.3.1 Standard model N2+2 . . . . . . . . . . . . . . . . . . 176

  10.4 B2+2-valued computability theory . . . . . . . . . . . . . . . 178 

    10.4.1 L2+2-valued computable functions . . . . . . . . . . . 178 

    10.4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 181 

  10.5 Equivalences of L3-valued and L2+2-valued computable functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 

    10.5.1 B2+2-valued halting problem . . . . . . . . . . . . . . 184 

    10.5.2 L2+2-valued computably enumerable sets . . . . . . . 184 

    10.5.3 Definability . . . . . . . . . . . . . . . . . . . . . . . . 185 

    10.5.4 L2+2-valued simple sets . . . . . . . . . . . . . . . . . 186 

  10.6 B2+2-minimal pairs . . . . . . . . . . . . . . . . . . . . . . . . 190 

  10.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193