You are wrong. Primitive recursive functions alone are able to recognize formal languages: https://en.wikipedia.org/wiki/PR_(complexity) https://en.wikipedia.o

You are wrong. Primitive recursive functions alone are able to recognize formal languages: https://en.wikipedia.org/wiki/PR_(complexity) https://en.wikipedia.org/wiki/PR_(complexity) PR is the complexity class of all primitive recursive functions—or, equivalently, the set of all formal languages that can be decided by such a function.