Talk:Turing-complete
From Esolang
[edit] Computing the Ackermann function doesn't ensure Turing-completeness
I've removed the following incorrect statements from the article:
- "In order to compute the Ackermann function for any values of m and n, however, a Turing-complete system is required. It is this meaning of Turing-complete which is more significant; if some computational system that can solve problems of size n can also always solve the same problems for size n+1, that system is Turing-complete."
One counterexample is the existence of languages in which all programs halt — so the language cannot be Turing-complete — yet can compute the Ackermann function (which is total). E.g., see Functions computable by total Turing machines.
Other counterexamples are languages constructed by modifying a Turing-complete language so it can only compute functions that never exceed some selected very-fast-growing computable function that everywhere exceeds the Ackermann function. Then it can compute Ackermann's function, but is not Turing-complete (because there are recursive functions, growing faster than the selected one, that it can't compute). --r.e.s. (Talk) 08:49, 17 November 2007 (UTC)
- Or, of course, HQ9+ modified to add an Ackermann command. --ais523 13:13, 19 November 2007 (UTC)
- Since HQ9+ is a joke language, I suppose you meant that as a joke (in the same sense as "add an Omega command" to magically compute Chaitin's Omega, for example. OTOH, it does suggest trivial counterexamples (which is what you might have intended); e.g., just take any language that has an Ack program in it, and restrict the language to that program alone — a one-program language. --r.e.s. (Talk) 19:54, 20 November 2007 (UTC)
- I was trying to bring up the point of trivial counterexamples. HQ9+ is a joke, but it is quite mathematically interesting as a model for trivial counterexamples. Likewise, that sort of program gives a trivial proof that there are an infinite number of computational classes (some of which are more interesting than others). --ais523 10:35, 21 November 2007 (UTC)
- Since HQ9+ is a joke language, I suppose you meant that as a joke (in the same sense as "add an Omega command" to magically compute Chaitin's Omega, for example. OTOH, it does suggest trivial counterexamples (which is what you might have intended); e.g., just take any language that has an Ack program in it, and restrict the language to that program alone — a one-program language. --r.e.s. (Talk) 19:54, 20 November 2007 (UTC)
