Talk:Machine that always halts

From Wikipedia, the free encyclopedia

This article is either very badly written, or wrong, or both. This is not a recognised classification in the computational heirarchy in standard computer science text books. It doesn't appear to be a decidable class of machines, so its entirely abstract in nature (which doesn't really make it an automata at all). Of course, these may just be misunderstandings because the article wanders around a bit, never really reaching either a point or a statement. Even after all that, the page heading seems to not match the content.--NeilMitchell 15:21, 10 March 2006 (UTC)

I agree, there are a couple of problems with it. Mainly they come down to, while the primitive recursive functions do give rise to a class of "machines" (models of computation) that always halt, and while PL-{GOTO} is one such "machine", not all machines which can be proven to always halt represent primitive recursive functions (for example, you can, using a reduction order on its arguments, prove that the Ackermann function always halts.)

It's also a pity that the terminology is not used consistently. I haven't been able to get my hands on a copy of Sipser, so I don't know if "decider" means "(Turing) machine which represents a primitive recursive function" or "(Turing) machine which (we assert) always halts". Kozen uses the term "total Turing machine" (in analogy with "total function", I suppose) for the latter. He doesn't talk about the former (most textbooks on computability that I've seen leave the PR functions as functions, and don't try to build machines for them.) I don't think it matters much that the class of total Turing machines is only semi-decidable - it's still a valuable term for talking about things in computability theory.

I also agree that the article comes across as a badly-written pastische, but what doesn't on Wikipedia?  :) I'd maybe suggest that the article be merged or related somehow to total function - except that currently redirects to partial function, which is also in need of cleanup. --Chris Pressey 06:08, 18 April 2006 (UTC)

[edit] This article needs serious revision

The following claim is false in the ordinary meanings of the words:

There are (Turing-)computable total functions that are not computable by any machine that always halts.

The problem is that the article needs a formal definition of what a machine that always halts is. It is not a Turing machine that is guaranteed to halt (because that is just the same as saying that it always halts — a proof that a machine always halts is certainly a guarantee that is halts). The point is that a decider has some mechanical guarantee to ensure that it always halts. A reader would have to know that this is what is intended in order to get the meaning of the article. It would be better, among other things, to use the phrase decider throughout instead of machine that always halts.

The article as it stands wavers between ordinary Turing machines that happen to be total, and special machines with a mechanical guarantee that they always halt. Since the class of primitive recursive functions is certainly a class that is mechanically guaranteed to be total, the claim that

The class of languages which can be decided by such machines is exactly the set of recursive languages.

is also false as it stands. This, again, would be fixed by includig the actual definition of a machine that always halts. CMummert 18:40, 16 July 2006 (UTC)

[edit] Edit on 2006-10-01

I looked at Sipser's book and Kozen's book. Both define a total Turing machine (decider) to be a regular Turing machine that happens to halt on every input. Thus they are not a different model of computation; the total Turing machines are a subclass of the class of all Turing machines. I edited the article to remove some false or confusing parts (for example: the claim that there is a total computable function not computable by a total Turing machine, which was bogus). I added the theorem that there are partial computable functions not computable by any total Turing machine, which is a correct theorem showing that the total machines are weaker than partial machines. Please feel free to edit and clean up the article. CMummert 00:05, 2 October 2006 (UTC)

To CMummert: I think you missed the point of this article. And your edit removed the essence of the article which was the theorem (supposedly bogus claim) you were complaining about. However, the theorem was wrong as stated (but it could have been fixed).

You have turned this article into an article on total recursive functions (which is redundant since we already have that covered in other articles). It was supposed to be an article on models of computation (other than Turing machines and less powerful) which only include total recursive functions. That is a very subtle distinction, I admit. Especially, because such a model can be reduced to a single total recursive function by adding the "program" as another input.

The central theorem said "There are (Turing-)computable total functions that are not computable by any machine that always halts.". What it SHOULD have said is "Given a model of computation which includes only total recursive functions, there is a total recursive function which is not included in that model.". This is true and an important result. JRSpriggs 07:47, 2 October 2006 (UTC)

Thanks for the comments. I had posed several questions higher on this page, but got no response. So I checked both Sipser and Kozen (with my own two eyes), which were already cited in the first sentence, and neither of them was talking about a model of computation that always halts; they were both talking about total Turing machines. In particular, a decider according to Sipser is just a regular Turing machine that happens to be total, not a special kind of machine. The point of the changes was to bring the article into agreement with the actual claims made by the references. I agree that more could be said about models of computation that only compute total functions. Feel free to add more content about models of computation that only compute total functions. I'll add the theorem you suggest later, since it is a good point. As to the previous claim, see the section this article needs serious revision above, although when I wrote that I didn't know what Sipser meant by decider. CMummert 10:25, 2 October 2006 (UTC)

Thanks. Your addition covers it. JRSpriggs 09:37, 3 October 2006 (UTC)

[edit] http://www.youtube.com/watch?v=slOWroJlmbs -- george bush

why does this page no longer have a disambiguating link to The Decider or Bushism? really the chances of someone looking up 'decider' with the intent to find a page about a 'machine that always halts' rather than a hugely popular political buzzword are quite slim, imo. Dyukanon 02:46, 25 December 2006 (UTC)

User 81.65.244.31 (talk · contribs) removed "{{dablink|"Decider" redirects here. For the [[George W. Bush]] remark, see [[The Decider]].}}" on 29 November 2006. I did not choose to revert him because I am not sufficiently familiar with the political buzzword stuff to know whether it is worth having a link to it or not. If you want to revert him, go ahead and do so. See Help:Reverting. JRSpriggs 04:03, 25 December 2006 (UTC)

done, thanksDyukanon 04:34, 25 December 2006 (UTC)