Talk:Decider (Turing machine)

Untitled Section

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)

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 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)

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)

partial Turing machine

What is a "partial Turing machine"? This article introduces that term without explanation or even a link to some other article to explain it. The Turing machine article currently never mentions the terms "partial Turing machine" or "total Turing machine". Is this article alluding to the Turing machines mentioned in the partial function article? Is "partial Turing machine" merely a synonym for "Turing machine", a superset that, as a small subset, includes "total Turing machines"? --68.0.124.33 (talk) 15:15, 6 March 2009 (UTC)

Since a Turing machine calculates an output from its input it can be seen as a function. If it halts for every possible input, then each input corresponds to a definite output and the machine corresponds to a function that is defined on the totality of the input. However when there is some input for which the machine does not halt, then the function to which it corresponds is not defined for that particular input and is thus a partial function on the input domain. Turing machines can be partitioned into two groups, those that halt on every input and those that do not. The first ones could be called total Turing machines while the latter could be called partial Turing machines. Whether this is actually the standard terminology I do not know. HTH MarSch (talk) 10:00, 29 December 2011 (UTC)

Recursive functions always halt?

"there exists no programming language which captures exactly the recursive functions, i.e. the functions which can be computed by a Turing machine that always halts.". I'm pretty sure you mean _total_ recursive functions. If it were true that recursive functions always halt, then that highly non-trivial statement would require a citation, or a wikilink, or a proof (bearing in mind the rule of 'no original research'), or some combination of those.

Remember, 'show me the money'. Any non-trivial statement needs to be backed up by something. Remembering that rule will help keep false statements from entering an article. And I'm pretty sure that statement about recursive functions is false. In fact I'm not even 100% sure it applies to _total_ recursive functions. There are functions that are total but not recursive, aren't there? And it's especially hard to answer that question when you've already stipulated that there's no way to characterize the recursive functions. You are confusing the reader at a deep level. _Total_ functions are functions that halt. Recursive functions are functions that call themselves (directly or indirectly? i.e. mutual recursion?). If there is some kind of provable rationship between the two, then it should be spelled out explicitly and fully cited. It's hard to see how there would be though, since Alan Turing proved that it is _impossible_ to characterize the set of all total functions, i.e. functions that always halt, because if such a thing were possible then it would solve the halting problem. So change 'recursive' to 'total recursive' or just 'total', or else provide a citation. And if you change it to 'total recursive' then it will of course require a citation.

The primitive recursive functions are functions that can be expressed either using well-behaved loops or well-behaved (recursive) functions - as long as 'well behaved' means 'terminating'. They're all total, but it looks to me like any of them could be viewed as recursive or non-recursive equally well. How the more general notion of 'recursive' functions behaves is a mystery to me. But the notion of 'total' is well defined. Total functions halt. Rely on that. Don't speak of 'recursive' functions unless someone knows what the heck that means. And if someone does, then please tell us who that is. And I will definitely be skeptical of the phrase 'recursive function' if it's just a synonym for 'total function', because we already have a phrase that means 'total function' - it's called 'total function'. We don't need another one. Comiscuous (talk) 05:39, 7 April 2021 (UTC)

 Done I agree with you. In fact, most programming languages "capture exactly the (partial) recursive functions", but none can capture exactly the total recursive functions. I guess, the latter was meant, but expressed sloppily. I inserted a "total" to fix that. - Jochen Burghardt (talk) 09:51, 7 April 2021 (UTC)

Name

Why is this page called "Machine that always halts"? There are many types of machines, not only Turing machines.

It seems like at some point in the past, this was called "Total Turing Machine", the page may have been renamed? "Total Turing Machine" or "Decider Turing Machine" are much better names. Caleb Stanford (talk) 19:56, 4 July 2022 (UTC)

No response and WP:BOLD so I went ahead and picked a new name. Caleb Stanford (talk) 22:13, 17 July 2022 (UTC)

Thanks! I adapted the redirect Total Turing machine. - Jochen Burghardt (talk) 08:31, 18 July 2022 (UTC)

The term "Decider Turing machine" isn't used in the sources I know. Sipser calls it just a "Decider". I would prefer to use what WP:NCDAB calls "parenthetical disambiguation" and move the article to Decider (Turing machine) or something like that. – Tea2min (talk) 13:24, 20 July 2022 (UTC)

Decider (Turing machine) sounds good. Done. Caleb Stanford (talk) 19:48, 20 July 2022 (UTC)

Thanks! – Tea2min (talk) 04:47, 21 July 2022 (UTC)