tildedave · December 10, 2015 20:38
diff --git a/gistfile1.txt b/gistfile1.txt
 dave@isis:~/workspace/reach/reach$ howdoi show halting problem undecidable
 In other words, is there an important difference between saying H = M and the following description from the proof? The H machine is called Universal Turing Machine (UTM) and is able to simulate any other Turing Machine, including itself. If M is an Universal Turing Machine like H, it is ok to say H = M, otherwise this would be weird. I thought the halting problem was the problem of deciding if a given machine will halt regardless of its output(accept/reject). If a solution exists for a halting problem, it has to be something that analyses source code like a compiler/decompiler/disassembler instead of actually running it. If it needed to run it, obviously it would never determine on a "no" answer. That is why the proof works based on contradiction and it is kind hard to understand.
 Basically it assumes first that exists such a machine that answers "yes" or "no" to any given input. [Hypothesis] Let's call this machine Q.
 Assuming Q is valid and it is an UTM, it can simulate another machine S that works following the steps below: S reads an input (a program and its input) S duplicates the input it just read S calls Q passing the copied input S waits for Q to answer (and based on our hypothesis it always will) Let's imagine now the input Q(S, S). Q will receive the program S and the argument of S is S itself. This input will make S call Q indefinitely and will never stop. Since Q and S were legal programs but there is a kind of input that makes Q never stop, Q is a machine impossible to built and therefore it is impossible to decide if a program S stops or not.
 Therefore we have the proof that the halting problem is undecidable. Sipser explains it well. Read it again now and see if you catch the idea :) Now, on to your question again. The Turing Machine is our most powerful machine for representing problems. As a recognition machine, it has to go through the input and run the algorithm to determine if it is valid or not. It is impossible to know the output of an algorithm without running it. The compiler is just a translator of syntax and little semantics. It cannot foresee how one will use the program and what the output will be.
diff --git a/gistfile2.txt b/gistfile2.txt
 dave@isis:~/workspace/reach/reach$ howdoi prove pumping lemma -p2
 The pumping lemma says:
 If a language A is regular => there is a number p (pumping length) where, if s is any string in L such that |s| >= p, then s may be divided into three pieces s=xyz, satisfying the following condition: xy i z is in L for each i>=0 |y|>=0 p>=|xy| The right way to show that a certain language L is not regular is to suppose L regular and try to reach a contradiction. Lets try to demonstrate that L = {0 n 1 n }|n>=0} is not regular. 
 We start assuming to the contrary that L is regular. You can think about this kind of demonstration as a game: Challenger: He choose the pumping length p. You cannot do any presumption on it. You : Now it is your turn: choose the "kind" of string that represents the irregularity of the language. Lets say that the string is in the form 0 p 1 p . A good tip in this step is to try to limit the adversary next move. Challenger: He presents to you a string s in the form 0 p 1 p . You: It's time to pump! If you chose correctly the form of the string in your previous move, you can do some assumption. In our case, for example, we know that the substring y consists only of 0s (at least one 0 because |y|>0), because |xy|<=p and first p-elements are 0s. Now we show that it exists i>=0 such that xy i z is not in L. For example, for i=2 the string xyyz has more 0s than 1s and so is not a member of L. This case is a contradiction. => L is not regular. Never forget to demonstrate why the pumped string cannot be a member of L. If you have any doubt, feel free to ask :) Cheers.
	dave@isis:~/workspace/reach/reach$ howdoi show halting problem undecidable
	In other words, is there an important difference between saying H = M and the following description from the proof? The H machine is called Universal Turing Machine (UTM) and is able to simulate any other Turing Machine, including itself. If M is an Universal Turing Machine like H, it is ok to say H = M, otherwise this would be weird. I thought the halting problem was the problem of deciding if a given machine will halt regardless of its output(accept/reject). If a solution exists for a halting problem, it has to be something that analyses source code like a compiler/decompiler/disassembler instead of actually running it. If it needed to run it, obviously it would never determine on a "no" answer. That is why the proof works based on contradiction and it is kind hard to understand.
	Basically it assumes first that exists such a machine that answers "yes" or "no" to any given input. [Hypothesis] Let's call this machine Q.
	Assuming Q is valid and it is an UTM, it can simulate another machine S that works following the steps below: S reads an input (a program and its input) S duplicates the input it just read S calls Q passing the copied input S waits for Q to answer (and based on our hypothesis it always will) Let's imagine now the input Q(S, S). Q will receive the program S and the argument of S is S itself. This input will make S call Q indefinitely and will never stop. Since Q and S were legal programs but there is a kind of input that makes Q never stop, Q is a machine impossible to built and therefore it is impossible to decide if a program S stops or not.
	Therefore we have the proof that the halting problem is undecidable. Sipser explains it well. Read it again now and see if you catch the idea :) Now, on to your question again. The Turing Machine is our most powerful machine for representing problems. As a recognition machine, it has to go through the input and run the algorithm to determine if it is valid or not. It is impossible to know the output of an algorithm without running it. The compiler is just a translator of syntax and little semantics. It cannot foresee how one will use the program and what the output will be.
	dave@isis:~/workspace/reach/reach$ howdoi prove pumping lemma -p2
	The pumping lemma says:
	If a language A is regular => there is a number p (pumping length) where, if s is any string in L such that \|s\| >= p, then s may be divided into three pieces s=xyz, satisfying the following condition: xy i z is in L for each i>=0 \|y\|>=0 p>=\|xy\| The right way to show that a certain language L is not regular is to suppose L regular and try to reach a contradiction. Lets try to demonstrate that L = {0 n 1 n }\|n>=0} is not regular.
	We start assuming to the contrary that L is regular. You can think about this kind of demonstration as a game: Challenger: He choose the pumping length p. You cannot do any presumption on it. You : Now it is your turn: choose the "kind" of string that represents the irregularity of the language. Lets say that the string is in the form 0 p 1 p . A good tip in this step is to try to limit the adversary next move. Challenger: He presents to you a string s in the form 0 p 1 p . You: It's time to pump! If you chose correctly the form of the string in your previous move, you can do some assumption. In our case, for example, we know that the substring y consists only of 0s (at least one 0 because \|y\|>0), because \|xy\|<=p and first p-elements are 0s. Now we show that it exists i>=0 such that xy i z is not in L. For example, for i=2 the string xyyz has more 0s than 1s and so is not a member of L. This case is a contradiction. => L is not regular. Never forget to demonstrate why the pumped string cannot be a member of L. If you have any doubt, feel free to ask :) Cheers.