0

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.

user118494
  • 5,837
  • Apparently, there are various slightly different functions all called "the Ackermann function." Could you give the definition of the specific one you're referring to? – David Jan 15 '16 at 06:59
  • 1
    See Joel David Hamkin's answer to a similar question on Mathoverflow:http://mathoverflow.net/questions/76037/inverse-ackermann-primitive-recursive-or-not/76054#76054 – Noah Schweber Jan 15 '16 at 07:01

0 Answers0