The graph of Ackermman function is primitive recursive

685 Views Asked by At

For a relation $ R ⊆ ℕ^n $, define the characteristic function $ χ :ℕ^n → ℕ $ such that $ χ(x_1, x_2,..., x_n)=1 $, if $ (x_1,...,x_n) ∈R, χ(x_1,...,x_n)=0 $ otherwise. Say a relation is premitive recursive if its characteristic function is premitive recursive. I know that the Ackermann function is not primitive recursive,but I have no idea about how to show that the graph is premitive recursive.