halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: MoeBlee on 11 Aug 2008 12:43 On Aug 8, 11:49 pm, ju...(a)diegidio.name wrote: > And again I'll notice that what you are assuming holds thanks to > Cantor, so that your proof is just irrelevant to the present and > related discussions. No, the proof is by formal axioms and rules of inference in the present or at anytime. Disagree with the axioms or rules, okay. But there's no basis to disagree that there exists the finite object that is a proof (a finite sequence of finite sequences) of the theorem from those axioms and rules. I keep reminding you of that, and you keep ignoring it. MoeBlee .
From: MoeBlee on 11 Aug 2008 12:48 On Aug 9, 10:17 pm, ju...(a)diegidio.name wrote: > The culprit is on the free usage of > "all/any". No culprit. The axioms/rules for the universal quantifier ("for all") are PRECISE. It can be checked by ALGORITHM whether universal generalization or universal instantation have been applied correctly or not. MoeBlee
From: LauLuna on 11 Aug 2008 13:46 On Aug 8, 6:39 pm, ju...(a)diegidio.name wrote: > On 8 Aug, 16:30, LauLuna <laureanol...(a)yahoo.es> wrote: > > > > > > > On Aug 8, 11:09 am, RichD <r_delaney2...(a)yahoo.com> wrote: > > > > I heard someone say recently, "The proof of the Turing > > > machine halting problem is an example of diagonalization." > > > > I don't see that. As I recall, it's proof by contradiction; > > > assume a program which accomplishes the goal, feed > > > the code of this program to itself, etc., ad absurdum. QED > > > > Whereas diagonalization consists of constructing a list, > > > then constructing a new object not in the list, etc. > > > > Can anyone reconcile this? > > > > -- > > > Rich > > > Diagonalization is a very general tecnique aiming at showing thet a > > certain set S does not exist: e.g. a countable set of all reals > > (Cantor), a bijection between A and P(A) (Cantor), a recursively > > enumerable set of all arithmetical truths (Gödel), an arithmetically > > definable set of all arithmetical truths (Tarski), etc. > > > The tecnique can be seen as a reductio of the assumption that S exists > > and it typically proceeds by constructing a diagonal object D that > > should be in S if S existed but that, by construction, cannot be in > > S. > > And this is where there are most of the objections. > > Below again a simple argument to show that from the very same > construction we could induce the exact opposite result: > > 1: The diagonal differs from the 1st entry in the 1st place; > 2: The diagonal differs from the 2nd entry in the 2nd place; > ... > n: The diagonal differs from the n-th entry in the n-th place; > > It seems straightforward to induce that, at the limit, the difference > between the diagonal and the limit entry tends to zero. > > -LV > > > > > This is sometimes put as the indefinite extensibility of any set T > > 'purporting' to be S; then it's shown that there is a (diagonal) > > function f that for any T gives an object d such that d is in T if T=S > > and it's shown that d is actually not in T. You may or may not require > > that f be computable. > > > Now consider the usual proof of Turing's theorem. Assume there is a > > Turing machine H that computes the halting problem for any Turing > > machine. Then we can use H to construct a double input matrix M that > > for any pair (m, n), where m is a code (a Gödel number) of a Turing > > machine and n is a natural, displays 1 if m terminates on n and 0 > > otherwise. > > > Now H must be in M coded (say) by h. We give h to H (h acting as a > > code for (h, h)) in order to fill in the corresponding square in M. To > > decide the halting problem for this specific input, H has to compute > > what H does when fed h, that is, it has to compute whether its current > > computation terminates; the ensuing circularity prevents H from giving > > an output and forces us to leave the corresponding square in M blank. > > > So, under the assumption that H exists, we've produced a computation > > (h, h) whose behavior is not represented in M, which contradicts the > > assumption. > > > Since M can be regarded as a set, (h, h) is an object that should be a > > member of M (if H existed) but is not such; thus the procedure fits > > with the general diagonal procedure described above. > > > Regards- Hide quoted text - > > - Show quoted text -- Hide quoted text - > > - Show quoted text - Letting aside questions about the existence of such a limit, there is no tendency in the sequence: the diagonal simply differs from every entry, it does not differ in 100%, then 50%, then 25%, etc. I can't see your point.
From: Balthasar on 11 Aug 2008 14:26 On Mon, 11 Aug 2008 09:48:48 -0700 (PDT), MoeBlee <jazzmobe(a)hotmail.com> wrote: > On Aug 9, 10:17�pm, ju...(a)diegidio.name wrote: >> >> The culprit is on the free usage of "all/any". >> > No culprit. The axioms/rules for the universal quantifier ("for all") > are PRECISE. It can be checked by ALGORITHM whether universal > generalization or universal instantation have been applied correctly > or not. > It's funny that this idiotic claim caught your attention too. Actually, I started a new thread for addressing this idioticy (which is rather typical for cranks). See: "@Crank: the free usage of 'all/any'" B. -- "For every line of Cantor's list it is true that this line does not contain the diagonal number. Nevertheless the diagonal number may be in the infinite list." (WM, sci.logic)
From: Balthasar on 11 Aug 2008 14:34
On Mon, 11 Aug 2008 09:36:38 -0400, herbzet <herbzet(a)gmail.com> wrote: >> >> The "limit entry" is indeed the "last" entry in the _list_, that is, >> the oo-th entry. This I have stated over and over and over. >> > OK, it's the oo-th entry of the list. That wasn't so hard to say, > was it? > Though (then) the question arises: since d (the "anti-diagonal") _by construction_ differs from the oo-th entry in the list by the oo-th digit, how can it be identical with the oo-th entry? (Let alone the problem that in "Cantor's" infinite lists -i.e. the lists which we are talking about in this context- there IS NO _last_ entry; since there is no _last_ natural number.) I guess we might ask WM for some hints. B. -- "For every line of Cantor's list it is true that this line does not contain the diagonal number. Nevertheless the diagonal number may be in the infinite list." (WM, sci.logic) |