Does Not Computehttp://blogs.msdn.com/b/ericlippert/archive/2012/10/10/does-not-compute.aspxOne of the most basic ways to think about a computer program is that it is a device which takes in integers as inputs and spits out integers as outputs. The C# compiler, for example, takes in source code strings, and those source code strings are essentiallyen-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)re: Does Not Computehttp://blogs.msdn.com/b/ericlippert/archive/2012/10/10/does-not-compute.aspx#10373226Thu, 29 Nov 2012 19:59:42 GMT91d46819-8472-40ad-a661-2c78acb4018c:10373226William Payne<p>So what is the big-Oh notation for the computational complexity of the busiest beaver? O(beaver)?</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10373226" width="1" height="1">re: Does Not Computehttp://blogs.msdn.com/b/ericlippert/archive/2012/10/10/does-not-compute.aspx#10359352Sat, 13 Oct 2012 11:34:40 GMT91d46819-8472-40ad-a661-2c78acb4018c:10359352rjcox<p>@ Oded</p>
<p>That's hardly surprising, both Turing and Gödel's work is the development towards a proof that arithmetic is consistent (free of any internal contradictions) as posed by Hilbert (second of his 23 problems posed in 1900).</p>
<p>The answer was that, for a sufficiently interesting arithmetic – our normal qualifies – cannot be proven to be consistent /and/ cannot be proven to be inconsistent. Hence "incompleteness".</p>
<div class="yellowbox">
<p>To clarify: Godel's proof shows that every logical system has at least one of these three properties: either (1) it is possible to prove both a theorem and its opposite, making the system <i>inconsistent</i>, (2) there exist well-formed statements in the system that have no proof, and their negations have no proof either, and therefore the system is <i>incomplete</i>, or (3) the system is not sufficiently powerful enough to implement integer arithmetic, and therefore the system is <i>weak</i>. There are no complete, consistent, strong logical systems. -- Eric</p>
</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10359352" width="1" height="1">re: Does Not Computehttp://blogs.msdn.com/b/ericlippert/archive/2012/10/10/does-not-compute.aspx#10359217Fri, 12 Oct 2012 18:40:22 GMT91d46819-8472-40ad-a661-2c78acb4018c:10359217Dan Sutton<p>So basically, what you're saying is that there no limit to how inefficiently a program can be written... I thought we knew this already!</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10359217" width="1" height="1">re: Does Not Computehttp://blogs.msdn.com/b/ericlippert/archive/2012/10/10/does-not-compute.aspx#10359146Fri, 12 Oct 2012 14:49:18 GMT91d46819-8472-40ad-a661-2c78acb4018c:10359146Kalle Olavi Niemitalo<p>If your Turing machines consist of 2^(n+1) state transition rules, and each rule has 2 * 2^n * 3 possibilities, then the total number of possible machines is not (2 * 2^n * 3) * (2^(n+1)) = 3 * 2^(2n+2). It is (2 * 2^n * 3)^(2^(n+1)). For n=2 (i.e. 4 internal states), that makes 24^8 = 110075314176 machines, rather than 24*8 = 192. For five internal states, the handful would be larger yet.</p>
<div class="yellowbox">
<p>Whoops, you are of course correct. I was typing faster than I was thinking. I'll fix the text. -- Eric</p>
</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10359146" width="1" height="1">re: Does Not Computehttp://blogs.msdn.com/b/ericlippert/archive/2012/10/10/does-not-compute.aspx#10358756Thu, 11 Oct 2012 14:17:02 GMT91d46819-8472-40ad-a661-2c78acb4018c:10358756Necroman<p>Actually I've used this same argument during my Masters degree exams two years ago - that we cannot create program for solving the Busy Beaver problem. If we have had such program, we would be able to solve the halting problem and that is a conflict.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10358756" width="1" height="1">re: Does Not Computehttp://blogs.msdn.com/b/ericlippert/archive/2012/10/10/does-not-compute.aspx#10358668Thu, 11 Oct 2012 08:38:50 GMT91d46819-8472-40ad-a661-2c78acb4018c:10358668Oded<p>This immediately reminded me of many themes of Douglas Hofstadter's book GEB and Godel's incompleteness theorem.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10358668" width="1" height="1">re: Does Not Computehttp://blogs.msdn.com/b/ericlippert/archive/2012/10/10/does-not-compute.aspx#10358461Wed, 10 Oct 2012 21:34:51 GMT91d46819-8472-40ad-a661-2c78acb4018c:10358461Ted<p>Pi and the square root of 2 are irrational numbers. Irrational numbers cannot be represented by A / B where A and B are integers, B <> 0 and also not represented by a terminating or repeating decimal. </p>
<div class="yellowbox">
<p>That is correct. And yet *you* have managed to represent both pi and root two in finitely many bits in this very comment. What explains this apparent paradox? And if *you* can do it, then why can't a Turing Machine do the same? -- Eric</p>
</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10358461" width="1" height="1">re: Does Not Computehttp://blogs.msdn.com/b/ericlippert/archive/2012/10/10/does-not-compute.aspx#10358449Wed, 10 Oct 2012 20:18:50 GMT91d46819-8472-40ad-a661-2c78acb4018c:10358449Jeroen Mostert<p>@Gabe: sure. The computers we use are what's technically known as linear bounded automata -- just like a Turing machine, but with finite storage. Those machines have finite state, and therefore, in principle, the halting problem is decidable for programs running on real computers. Just run the program and track the distinct states you've seen (where "state" is the contents of all memory of the machine). If a state ever repeats, you know the program will never terminate (because, barring hardware failure, the computer is deterministic and one state will always lead to the same next state). Otherwise, you will surely eventually run out of unique states to see, and then the program must stop if it hasn't done so already.</p>
<p>The problem is, of course, the "in principle", as Eric pointed out. It's absurdly impractical to solve the halting problem this way for any non-trivial program -- the number of possible states isn't just astronomical, it's far beyond even that. However, the basic approach (try to show that we will never visit the exact same state twice) is used in various techniques to prove that programs terminate. Those just don't rely on naive enumeration, but on proving more involved properties over all possible states.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10358449" width="1" height="1">re: Does Not Computehttp://blogs.msdn.com/b/ericlippert/archive/2012/10/10/does-not-compute.aspx#10358418Wed, 10 Oct 2012 18:47:42 GMT91d46819-8472-40ad-a661-2c78acb4018c:10358418Daniel Brückner<p>If there were a computable upper bound for the busy beaver function, we could just run the a Turing machine for this number of steps to decide whether it halts or not.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10358418" width="1" height="1">re: Does Not Computehttp://blogs.msdn.com/b/ericlippert/archive/2012/10/10/does-not-compute.aspx#10358341Wed, 10 Oct 2012 16:24:27 GMT91d46819-8472-40ad-a661-2c78acb4018c:10358341Ted<p>Computing any infinitely long number, such as the square root of 2, will not halt.</p>
<div class="yellowbox">
<p>What characterizes an "infinitely long number"? The number 1.0000... is "infinitely long" as well, but it can be computed, right? I see no reason why the square root of two is any more special than any other number. -- Eric</p>
</div>
<p>Q: Can you cover why a local variable to a property cannot be declared within the scope of a property and before the GET? This would be quite helpful for all of the XAML /WPF propeties with backing variables and onPropertyChanged? Auto properties could be greatly enhanced by syntax similar to</p>
<p>public bool proprtyA { get; set; when_modified { code snippit } }</p>
<div class="yellowbox">
<p>The same reason why every unimplemented feature is not implemented: features are unimplemented by default. In order to become implemented a feature must be (1) thought of, (2) designed, (3) specified, (4) implemented, (5) tested, (6) documented and (7) shipped. Of those seven things, only the first has happened for your proposed feature. Therefore, no such feature. -- Eric</p>
</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10358341" width="1" height="1">re: Does Not Computehttp://blogs.msdn.com/b/ericlippert/archive/2012/10/10/does-not-compute.aspx#10358312Wed, 10 Oct 2012 15:25:42 GMT91d46819-8472-40ad-a661-2c78acb4018c:10358312Gabe<p>So you CAN solve the Halting Problem!</p>
<p>Just for only really small computers.</p>
<div class="yellowbox">
<p>Correct! The Halting Problem is solvable for Turing Machines that have five internal states or fewer. But as we've seen, that's only a small handful of possible machines, so it is tractable to analyze all of them. -- Eric</p>
</div><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10358312" width="1" height="1">