Content deleted Content added
Line 140:
:However, <s>not every algorithm is boundable with a Big-O limit (see [[run-time analysis]])</s> (''I might be wrong about that, too''), and there are undecidable algorithms (see [[halting problem]]). Unfortunately, I do not know if there are algorithms that are decidable for small inputs but undecidable for large inputs – but I can tell you that there are algorithms whose run-times grow extraordinarily rapidly as n increases, such that the fastest supercomputers in existence would take until the end of the universe to solve problems for sufficiently large inputs (see [[Ackermann function]] and [[busy beaver]] for examples). See [[Computational complexity theory#intractability|intractability]] for more info. [[User:Groupthink|Groupthink]] 00:03, 8 July 2007 (UTC)
:I have in fact heard of problems that are undecidable for sufficiently large values of the parameter, but decidable for smaller values. Just do a Google search for the phrase "becomes undecidable". My personal favourite is the [[Post correspondence problem]]: if the number of tiles is at most 2, it is decidable. If the number of tiles is at least 7, it is undecidable. For values between 2 and 7, we don't know if it's decidable or not. [[User:Dcoetzee|Dcoetzee]] 20:24, 18 December 2007 (UTC)
== History ==
| |||