<story><title>The zombie misconception of theoretical computer science</title><url>https://scottaaronson.blog/?p=8106</url></story><parent_chain><item><author>Xcelerate</author><text>It can be sort of unintuitive how the concept of computability necessarily involves infinity.&lt;p&gt;For example: does there exist an algorithm that computes the Kolmogorov complexity, K(s), of string s for arbitrary s? It is well-known that the answer is &amp;quot;no&amp;quot; — there is no Turing machine that takes as input a string of arbitrary length and computes K(s). The proof is quite brief and involves the halting problem.&lt;p&gt;But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length &amp;lt; n? The answer is yes! And there exists such an algorithm for any value of n.&lt;p&gt;How is that possible? Think about it for a second, because the answer is going to disappoint you: simply create a Turing machine that consists of a giant lookup table for all 2^n possible strings that prints the value of K(s) for each one.&lt;p&gt;But wait, that&amp;#x27;s cheating! Maybe so, but any specific implementation of the algorithm has a finite description. And by definition, K(s) is also finite for all s. While it&amp;#x27;s true that I haven&amp;#x27;t provided any particular method for determining the value of K(s) for all 2^n strings in order to actually create the lookup table, that doesn&amp;#x27;t matter. Such an algorithm nevertheless exists, regardless of whether you can find it or prove that it does what you want it to.&lt;p&gt;So in a sense, finite questions about a finite number of things are sort of uninteresting from the perspective of computability, because you can always write a program that just prints the answer for all of those things (how quickly it does this is another matter). But when you extend the question to an infinite number of things, computability becomes much more interesting, because you don&amp;#x27;t know whether something finite can provide answers to questions about an infinite number of things.</text></item></parent_chain><comment><author>gowld</author><text>This description makes it sounds like large areas of computer science are just goofy, meaningless, games.&lt;p&gt;But what&amp;#x27;s really happening is that &amp;quot;infinity&amp;quot; is standing in for &amp;quot;approximate, eventual, steady state behavior for sufficiently large N,  larger than any specific one-off gimmick you might think of&amp;quot;.&lt;p&gt;In the real world, though, those gimmicks are important, and the constants and low-order terms ignored in a Big-O comparison are important to real world performance.&lt;p&gt;There is constant tension between &amp;quot;big enough problem that the contant factors don&amp;#x27;t matter&amp;quot;, and &amp;quot;small enough problem that it conforms to the (often implicit)  of what &amp;#x27;constant&amp;#x27; means (example: 32bit ints masquerading as integers)&amp;quot;</text></comment>
<story><title>The zombie misconception of theoretical computer science</title><url>https://scottaaronson.blog/?p=8106</url></story><parent_chain><item><author>Xcelerate</author><text>It can be sort of unintuitive how the concept of computability necessarily involves infinity.&lt;p&gt;For example: does there exist an algorithm that computes the Kolmogorov complexity, K(s), of string s for arbitrary s? It is well-known that the answer is &amp;quot;no&amp;quot; — there is no Turing machine that takes as input a string of arbitrary length and computes K(s). The proof is quite brief and involves the halting problem.&lt;p&gt;But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length &amp;lt; n? The answer is yes! And there exists such an algorithm for any value of n.&lt;p&gt;How is that possible? Think about it for a second, because the answer is going to disappoint you: simply create a Turing machine that consists of a giant lookup table for all 2^n possible strings that prints the value of K(s) for each one.&lt;p&gt;But wait, that&amp;#x27;s cheating! Maybe so, but any specific implementation of the algorithm has a finite description. And by definition, K(s) is also finite for all s. While it&amp;#x27;s true that I haven&amp;#x27;t provided any particular method for determining the value of K(s) for all 2^n strings in order to actually create the lookup table, that doesn&amp;#x27;t matter. Such an algorithm nevertheless exists, regardless of whether you can find it or prove that it does what you want it to.&lt;p&gt;So in a sense, finite questions about a finite number of things are sort of uninteresting from the perspective of computability, because you can always write a program that just prints the answer for all of those things (how quickly it does this is another matter). But when you extend the question to an infinite number of things, computability becomes much more interesting, because you don&amp;#x27;t know whether something finite can provide answers to questions about an infinite number of things.</text></item></parent_chain><comment><author>paulmd</author><text>&amp;gt; But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length &amp;lt; n? The answer is yes! And there exists such an algorithm for any value of n.&lt;p&gt;of course - n is by definition a finite number!&lt;p&gt;and in fact at infinity, all finite numbers are quite small, actually.  A mile might as well be a millimeter, from your chair at the end of the universe.&lt;p&gt;And your scenario is basically just &amp;quot;hilbert&amp;#x27;s infinite hotel, on a computer&amp;quot; - we can of course add another program simply by moving all the existing programs 1 spot over... and it remains the exact same size of table needed to compute it!&lt;p&gt;I would actually generalize this and just say that most people have poor intuition of how infinities (alephs, etc) and transfinite mathematics work in general.  it&amp;#x27;s not a common subject, it&amp;#x27;s not a subject with everyday relevance, and it&amp;#x27;s deeply steeped in the emergent properties of mathematics and category&amp;#x2F;set theory.  Like not only are infinities bigger than any finite number, but some infinities can nevertheless be bigger than other infinities etc - these are not things that are immediately obvious to the 3rd-grade concept of &amp;quot;infinity&amp;quot; that most people stop at.&lt;p&gt;the much more interesting question would be if there exists an n &amp;lt; infinity such that the algorithm can be computed, and of course the answer is no (darn, there goes my turing prize).</text></comment>