StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You did not mention anything about a character can be used only once - so without this restriction is problem of "Can we generate k (or more) different words?" is <strong>undecideable</strong>.<sup>1</sup>.</p> <p>(With a constraint on the number of "visites" per element there are finite number of possibilities and the claim and proof does not hold of course).</p> <p><strong>Proof:</strong> <br>It is known that there is no algorithm <code>A</code> that can decide if a terminating algorithm <code>B</code> returns <code>true</code> for <code>k</code> or more different inputs. (will look for citation for this claim later if needed, trust me for now).</p> <p>We will show that given an algorithm <code>A</code> that says if there are <code>k</code> or more generated words - we can decide if there are <code>k</code> or more different inputs that yield "true":</p> <ol> <li><p>Let the (terminating) algorithm that decides if there are <code>k</code> or more generated words be <code>M</code>.</p></li> <li><p>Without loss of generality - assume binary alphabet (we can represent everything with it).</p></li> <li><p>Let:</p> <pre><code> array = 0 1 0 1 </code></pre> <p>Note we can generate any binary word while walking on this array.</p></li> </ol> <p><strong>Algorithm A:</strong> <br><strong>input:</strong> algorithm B, natural number n <br>output: true if and only if algorithm B answers "true" for n or more different inputs. <br><strong>The algorithm</strong>: <br>(1) use <code>B(word)</code> as the black box dictionary - if the answer is true, then <code>word</code> is in dictionary. <br>(2) use <code>array</code> as the array. <br>(3) Run M on (array,dictionary,n), and answer like it.</p> <p>Note that if M answered true -> there are <code>n</code> or more accepted words -> there are <code>n</code> or more different inputs to B that yields true (definition of dictionary and since we can generate every input with array) -> the answer to the problem is true. <br>(if the algorithm answered false the proof is similar).</p> <p><strong>QED</strong></p> <p><strong>Conclusion:</strong> <br>If we can repeat a character in the array more then a once (or to be exact - unbounded number of times) - then <strong>the problem is unsolveable without any information on the dictionary.</strong></p> <hr> <p>(1) An undecideble problem is a problem where there is no algorithm that can answer TRUE/FALSE correctly in 100% of the cases - For every algorithm, there is some case where the algorithm will get "stuck" in an infinite loop (or give a wrong answer). The most common of "undecideable" problems is the <a href="http://en.wikipedia.org/wiki/Halting_problem" rel="nofollow">Halting Problem</a> - which says - there is no algorithm <code>A</code> that can take any algorithm <code>B</code> and answer if <code>B</code> stops for some input <code>w</code>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload