Fork me on GitHub
Math for the people, by the people.

User login

Turing computable

Synonym: 
Turing-computable
Type of Math Object: 
Definition
Major Section: 
Reference

Mathematics Subject Classification

03D10 no label found68Q05 no label found

Comments

``Turing computable'' functions are also called ``recursive'' functions. (The confusion stems from the pre-Church-Turing days, when the concept of recursive function was defined by adding minimization to primitive recursive functions, and it was not clear that Turing machines had exactly the same power).

Could this synonym be added?

I've changed the entry to mention that recursive means basically the same thing, but I'm not making it a formal synonym. This is because I think there should be a separate ``recursive function'' entry with that synonym, which should recieve the linking.

Alternatively this entry could be greatly expanded so that it covers recursive function theory, but I'm not the guy to write that (I'll orphan the entry if you want it though.)

apk

Subscribe to Comments for "Turing computable"