Talk:Deterministic algorithm

Latest comment: 10 years ago by Wikiedit738 in topic German Determinismus/Determiniertheit

German Determinismus/Determiniertheit

edit

In German you have to distinguish between de:Determinismus (Algorithmus) and de:Determiniertheit (Algorithmus). After reading the definition of "deterministic algorithm" in this article, I would say "deterministic algorithm" is equivalent to German Determinismus. But how would you say Determiniertheit in English? --Abdull 22:01, 27 October 2005 (UTC)Reply

If I understand your question correctly, Abdull, then this is related: the article does not properly distinguish different senses of determinism:

  • algorithms which always give the same output for each input
  • algorithms which always pass through the same states for each input
  • algorithms which always run in the same amount of time for each input

I got here via a link on the page Real-time operating system which seems to take the third view, but this is not justified based on the page's contents.

Not sure how to proceed. --Wikiedit738 (talk) 09:50, 13 June 2014 (UTC)Reply

Imaginary?

edit
 can be quickly solved using an imaginary massively parallel machine
 called a nondeterministic Turing machine, but efficient practical
 algorithms have never been found for any of them.

For a machine to be a nondeterministic Turing machine there is no requirement that it be massively parallel nor are they imaginary. The only thing different is that there is a chance that the algorithm will accept (or find) in polynomial time via incorporating some indeterminate aspect into the algorithm/machine. --ANONYMOUS COWARD0xC0DE 02:54, 10 January 2007 (UTC)Reply

Lack of references

edit

For example, if you are playing an on-line game of blackjack that shuffles its deck using a pseudorandom number generator, a clever gambler might guess precisely the numbers the generator will choose and so determine the entire contents of the deck ahead of time, allowing him to cheat (this has actually happened!)

What's the reference for 'this has actually happened'? I do remember this being a plot device in the TV series Numbers, except this was for an electronic card shuffler, but can't find a record of an real case with an on-line shuffler of this. 131.217.6.9 09:06, 4 June 2007 (UTC)Reply

what is a non-determinstic algorithm? (notes for future editing)

edit

This section should be suppressed, and the article non-deterministic algorithm linked instead. (The discussion in the current section points out some reasons that cause an algorithm to appear to behave non-deterministically, but not in the common Theroetical Computer Science sense; if at all, such a discussion should appear in the related article.) AmirOnWiki (talk) 13:14, 18 March 2011 (UTC)Reply

Non-deterministic turing machines don't belong in this article

edit

I just deleted some text in "disadvantages" which seemed to suggest that nondeterministic algorithms can solve NP hard problems more efficiently than deterministic algorithms. If nondeterministic turing machines are mentioned at all in this article, it should be to clarify to the reader that such machines are not related to the topic of the article. — Preceding unsigned comment added by 2001:470:8B2D:827:14CA:27F1:4678:B842 (talk) 20:12, 6 May 2014 (UTC)Reply

I rewrote this section based on the above observation (it appears the text that was "deleted" was added back at some point). The conflation of nondeterministic turing machines and programs with nondeterministic output is a serious mistake on the part of the original authors of that section. Please do not revert or add back that argument without first explaining your perspective on a talk page.-Tim Kaler 21:57, 7 October 2014 (UTC)