Kleene's T predicate

<h2 id="definition">Definition</h2>

The definition depends on a suitable <a href="/facts/G%C3%B6del_numbering/36BpTK1g">Gödel numbering</a> that assigns natural numbers to <a href="/facts/Computable_function/dzwBlLGn">computable functions</a> (given as <a href="/facts/Turing_machine/ojCtglYu">Turing machines</a>). This numbering must be sufficiently effective that, given an index of a computable function and an input to the function, it is possible to effectively simulate the computation of the function on that input. The 
 
 
 
 T
 
 
 {\displaystyle T}
 
 predicate is obtained by formalizing this simulation.
The <a href="/facts/Ternary_relation/m5wypU94">ternary relation</a> 
 
 
 
 
 T
 
 1
 
 
 (
 e
 ,
 i
 ,
 x
 )
 
 
 {\displaystyle T_{1}(e,i,x)}
 
 takes three natural numbers as arguments. 
 
 
 
 
 T
 
 1
 
 
 (
 e
 ,
 i
 ,
 x
 )
 
 
 {\displaystyle T_{1}(e,i,x)}
 
 is true if 
 
 
 
 x
 
 
 {\displaystyle x}
 
 encodes a computation history of the computable function with index 
 
 
 
 e
 
 
 {\displaystyle e}
 
 when run with input 
 
 
 
 i
 
 
 {\displaystyle i}
 
, and the program halts as the last step of this computation history. That is, 

<ul><li>
 
 
 
 
 T
 
 1
 
 
 
 
 {\displaystyle T_{1}}
 
 first asks whether 
 
 
 
 x
 
 
 {\displaystyle x}
 
 is the <a href="/facts/G%C3%B6del_numbering_for_sequences/0ScAUVTL">Gödel number</a> of a finite sequence 
 
 
 
 ⟨
 
 x
 
 j
 
 
 ⟩
 
 
 {\displaystyle \langle x_{j}\rangle }
 
 of complete configurations of the Turing machine with index 
 
 
 
 e
 
 
 {\displaystyle e}
 
, running a computation on input 
 
 
 
 i
 
 
 {\displaystyle i}
 
.</li>
<li>If so, 
 
 
 
 
 T
 
 1
 
 
 
 
 {\displaystyle T_{1}}
 
 then asks if this sequence begins with the starting state of the computation and each successive element of the sequence corresponds to a single step of the Turing machine.</li>
<li>If it does, 
 
 
 
 
 T
 
 1
 
 
 
 
 {\displaystyle T_{1}}
 
 finally asks whether the sequence 
 
 
 
 ⟨
 
 x
 
 j
 
 
 ⟩
 
 
 {\displaystyle \langle x_{j}\rangle }
 
 ends with the machine in a halting state.</li></ul>
If all three of these questions have a positive answer, then 
 
 
 
 
 T
 
 1
 
 
 (
 e
 ,
 i
 ,
 x
 )
 
 
 {\displaystyle T_{1}(e,i,x)}
 
 is true, otherwise, it is false.
The 
 
 
 
 
 T
 
 1
 
 
 
 
 {\displaystyle T_{1}}
 
 predicate is <a href="/facts/Primitive_recursive/4z97gRnl">primitive recursive</a> in the sense that there is a primitive recursive function that, given inputs for the predicate, correctly determines the truth value of the predicate on those inputs. 
There is a corresponding primitive recursive function 
 
 
 
 U
 
 
 {\displaystyle U}
 
 such that if 
 
 
 
 
 T
 
 1
 
 
 (
 e
 ,
 i
 ,
 x
 )
 
 
 {\displaystyle T_{1}(e,i,x)}
 
 is true then 
 
 
 
 U
 (
 x
 )
 
 
 {\displaystyle U(x)}
 
 returns the output of the function with index 
 
 
 
 e
 
 
 {\displaystyle e}
 
 on input 
 
 
 
 i
 
 
 {\displaystyle i}
 
.
Because Kleene's formalism attaches a number of inputs to each function, the predicate 
 
 
 
 
 T
 
 1
 
 
 
 
 {\displaystyle T_{1}}
 
 can only be used for functions that take one input. There are additional predicates for functions with multiple inputs; the relation

T
          
            k
          
        
        (
        e
        ,
        
          i
          
            1
          
        
        ,
        …
        ,
        
          i
          
            k
          
        
        ,
        x
        )
      
    
    {\displaystyle T_{k}(e,i_{1},\ldots ,i_{k},x)}

is true if 
 
 
 
 x
 
 
 {\displaystyle x}
 
 encodes a halting computation of the function with index 
 
 
 
 e
 
 
 {\displaystyle e}
 
 on the inputs 
 
 
 
 
 i
 
 1
 
 
 ,
 …
 ,
 
 i
 
 k
 
 
 
 
 {\displaystyle i_{1},\ldots ,i_{k}}
 
.
Like 
 
 
 
 
 T
 
 1
 
 
 
 
 {\displaystyle T_{1}}
 
, all functions 
 
 
 
 
 T
 
 k
 
 
 
 
 {\displaystyle T_{k}}
 
 are primitive recursive.
Because of this, any theory of arithmetic that is able to represent every primitive recursive function is able to represent 
 
 
 
 T
 
 
 {\displaystyle T}
 
 and 
 
 
 
 U
 
 
 {\displaystyle U}
 
. Examples of such arithmetical theories include <a href="/facts/Robinson_arithmetic/FAFPDus0">Robinson arithmetic</a> and stronger theories such as <a href="/facts/Peano_arithmetic/DhhDnNug">Peano arithmetic</a>.

<h2 id="normal-form-theorem">Normal form theorem</h2>
The 
 
 
 
 
 T
 
 k
 
 
 
 
 {\displaystyle T_{k}}
 
 predicates can be used to obtain Kleene's normal form theorem for computable functions (Soare 1987, p. 15; Kleene 1943, p. 52—53). This states there exists a fixed <a href="/facts/Primitive_recursive_function/4z97gRnl">primitive recursive function</a> 
 
 
 
 U
 
 
 {\displaystyle U}
 
 such that a function 
 
 
 
 f
 :
 
 
 N
 
 
 k
 
 
 →
 
 N
 
 
 
 {\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }
 
 is computable if and only if there is a number 
 
 
 
 e
 
 
 {\displaystyle e}
 
 such that for all 
 
 
 
 
 n
 
 1
 
 
 ,
 …
 ,
 
 n
 
 k
 
 
 
 
 {\displaystyle n_{1},\ldots ,n_{k}}
 
 one has

f
 (
 
 n
 
 1
 
 
 ,
 …
 ,
 
 n
 
 k
 
 
 )
 ≃
 U
 (
 μ
 x
 
 
 T
 
 k
 
 
 (
 e
 ,
 
 n
 
 1
 
 
 ,
 …
 ,
 
 n
 
 k
 
 
 ,
 x
 )
 )
 
 
 {\displaystyle f(n_{1},\ldots ,n_{k})\simeq U(\mu x\,T_{k}(e,n_{1},\ldots ,n_{k},x))}
 
,
where μ is the <a href="/facts/Mu_operator/Kj5YLWy9">μ operator</a> (
 
 
 
 μ
 x
 
 ϕ
 (
 x
 )
 
 
 {\displaystyle \mu x\,\phi (x)}
 
 is the smallest natural number for which 
 
 
 
 ϕ
 (
 x
 )
 
 
 {\displaystyle \phi (x)}
 
 is true) and 
 
 
 
 ≃
 
 
 {\displaystyle \simeq }
 
 is true if both sides are undefined or if both are defined and they are equal. By the theorem, the definition of every <a href="/facts/General_recursive_function/pQezUupS">general recursive function</a> f can be rewritten into a normal form such that the μ operator is used only once, viz. immediately below the topmost 
 
 
 
 U
 
 
 {\displaystyle U}
 
, which is independent of the computable function 
 
 
 
 f
 
 
 {\displaystyle f}
 
.

<h2 id="arithmetical-hierarchy">Arithmetical hierarchy</h2>
In addition to encoding computability, the T predicate can be used to generate <a href="/facts/Turing_complete_set/qczcQTbz">complete sets</a> in the <a href="/facts/Arithmetical_hierarchy/rQptcBFK">arithmetical hierarchy</a>. In particular, the set

K
        =
        {
        e
        
          
             
          
        
        :
        
          
             
          
        
        ∃
        x
        
          T
          
            1
          
        
        (
        e
        ,
        0
        ,
        x
        )
        }
      
    
    {\displaystyle K=\{e{\mbox{ }}:{\mbox{ }}\exists xT_{1}(e,0,x)\}}

which is of the same <a href="/facts/Turing_degree/yDkWYeT1">Turing degree</a> as the <a href="/facts/Halting_problem/Xz1bac40">halting problem</a>, is a 
 
 
 
 
 Σ
 
 1
 
 
 0
 
 
 
 
 {\displaystyle \Sigma _{1}^{0}}
 
 complete unary relation (Soare 1987, pp. 28, 41). More generally, the set

K
          
            n
            +
            1
          
        
        =
        {
        ⟨
        e
        ,
        
          a
          
            1
          
        
        ,
        …
        ,
        
          a
          
            n
          
        
        ⟩
        :
        ∃
        x
        
          T
          
            n
          
        
        (
        e
        ,
        
          a
          
            1
          
        
        ,
        …
        ,
        
          a
          
            n
          
        
        ,
        x
        )
        }
      
    
    {\displaystyle K_{n+1}=\{\langle e,a_{1},\ldots ,a_{n}\rangle :\exists xT_{n}(e,a_{1},\ldots ,a_{n},x)\}}

is a 
 
 
 
 
 Σ
 
 1
 
 
 0
 
 
 
 
 {\displaystyle \Sigma _{1}^{0}}
 
-complete (n+1)-ary predicate. Thus, once a representation of the Tn predicate is obtained in a theory of arithmetic, a representation of a 
 
 
 
 
 Σ
 
 1
 
 
 0
 
 
 
 
 {\displaystyle \Sigma _{1}^{0}}
 
-complete predicate can be obtained from it.
This construction can be extended higher in the arithmetical hierarchy, as in <a href="/facts/Post%27s_theorem/wPId3E7D">Post's theorem</a> (compare Hinman 2005, p. 397). For example, if a set 
 
 
 
 A
 ⊆
 
 
 N
 
 
 k
 +
 1
 
 
 
 
 {\displaystyle A\subseteq \mathbb {N} ^{k+1}}
 
 is 
 
 
 
 
 Σ
 
 n
 
 
 0
 
 
 
 
 {\displaystyle \Sigma _{n}^{0}}
 
 complete then the set

{
        ⟨
        
          a
          
            1
          
        
        ,
        …
        ,
        
          a
          
            k
          
        
        ⟩
        :
        ∀
        x
        (
        ⟨
        
          a
          
            1
          
        
        ,
        …
        ,
        
          a
          
            k
          
        
        ,
        x
        )
        ∈
        A
        )
        }
      
    
    {\displaystyle \{\langle a_{1},\ldots ,a_{k}\rangle :\forall x(\langle a_{1},\ldots ,a_{k},x)\in A)\}}

is 
 
 
 
 
 Π
 
 n
 +
 1
 
 
 0
 
 
 
 
 {\displaystyle \Pi _{n+1}^{0}}
 
 complete.

<h2 id="notes">Notes</h2>

<ul><li>Peter Hinman, 2005, Fundamentals of Mathematical Logic, A K Peters. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-56881-262-5</li>
<li>Stephen Cole Kleene (Jan 1943). <a href="https://www.ams.org/journals/tran/1943-053-01/S0002-9947-1943-0007371-8/S0002-9947-1943-0007371-8.pdf">"Recursive predicates and quantifiers"</a> (PDF). Transactions of the American Mathematical Society. 53 (1): 41–73. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0002-9947-1943-0007371-8">10.1090/S0002-9947-1943-0007371-8</a>. Reprinted in The Undecidable, Martin Davis, ed., 1965, pp. 255–287.</li>
<li>—, 1952, Introduction to Metamathematics, North-Holland. Reprinted by Ishi press, 2009, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-923891-57-9.</li>
<li>—, 1967. Mathematical Logic, John Wiley. Reprinted by Dover, 2001, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-486-42533-9.</li>
<li><a href="/facts/Robert_I._Soare/RWzYmGPa">Robert I. Soare</a>, 1987, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-15299-7</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">The predicate described here was presented in (Kleene 1943) and (Kleene 1952), and this is what is usually called "Kleene's T predicate". (Kleene 1967) uses the letter T to describe a different predicate related to computable functions, but which cannot be used to obtain Kleene's normal form theorem. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
</ol>

Kleene's T predicate open-in-new

Kleene's T predicate