halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: julio on 10 Aug 2008 09:05 On 10 Aug, 12:44, David C. Ullrich <dullr...(a)sprynet.com> wrote: > On Sat, 9 Aug 2008 18:42:50 -0700 (PDT), ju...(a)diegidio.name wrote: > >On 9 Aug, 23:30, Barb Knox <s...(a)sig.below> wrote: > >> In article > >> <7c07f984-0a79-4248-9078-6bf6c8398...(a)c58g2000hsc.googlegroups.com>, > >> ju...(a)diegidio.name wrote: > >> > On 9 Aug, 07:20, Barb Knox <s...(a)sig.below> wrote: > >> > > In article > >> > > <371eb05c-831d-435d-8dea-966887ca4...(a)e39g2000hsf.googlegroups.com>, > >> > > ju...(a)diegidio.name wrote: > >> > > > On 8 Aug, 19:00, Chris Menzel <cmen...(a)remove-this.tamu.edu> wrote: > >> [snip] > >> > > > > Let me guess: You also think that an infinite set of numbers must > >> > > > > contain an infinitely large number. > > >> > > > Easy guess. That number is called infinity, or otherwise "omega" ('w', > >> > > > or even 'oo'). > > >> > > > With my construction I don't get higher order infinite ordinals, but > >> > > > instead I get that 'oo' is representable, as is 'oo-1' and so on.. That > >> > > > is, we can enumerate from zero as well as enumerate back from > >> > > > infinity. > > >> > > So then do you reject mathematical induction? > > >> > Absolutely not. I rather "double it". Informally speaking, I have two > >> > end-points, zero and its mirror, infinity. Maybe keep in mind there is > >> > no uncomputables in this realm. > > >> > > If not, then one can > >> > > easily prove that oo < oo, which does not look healthy. > > >> > I'd be interested in seeing it, thanks. Mine is still mostly an > >> > exploration. > > >> OK, I'll bite, since "exploration" does imply that you might under some > >> circumstances reconsider your current position. > > >Very well appreciated. > > >> Here's a mathematical induction proof that oo < oo, using simple > >> induction on N* (which is hereby defined as N augmented by the single > >> limit point "oo"). > > >> Lemma: For all n in N*, n < oo. > >> Base case: clearly 0 < oo. > >> Induction step: Assume k < oo. Then clearly k+1 < oo also. > > >> Applying the lemma to n = oo, we get oo < oo. > >> QED. > > >> Thus mathematical induction does not work for N*. > > >> (Note: There is a form of induction that DOES work for "transfinite > >> ordinals" -- see for example > >> <http://en.wikipedia.org/wiki/Transfinite_induction>.) > > >Indeed, I have been using transfinite induction explicitly in my > >recent posts on the argument. > > No, you haven't. You may think that's what you've been > doing, but in fact you argument has been based on _exactly_ > the sort of incorrect quasi-induction as in Barb's example. That is? What are you babbling about? > >Here I have dropped it, first because my > >account was very fast and very informal, second because mentioning the > >"transfinite" just led me reiterated accusations of being pompous with > >no content and no understanding. > > Here's a hint: Any time you claim that you can show that R is > countable or that there is an error in the standard proof of > the uncountability of R people will conclude you have > no understanding. Exactly as if you claimed to have a proof > that 2 + 2 is not 4; then people would _correctly_ claim > you didn't understand arithmetic. The usual hint, the usual analogy, the usual reitereted ad hominem nonsense. Will you ever give any contribution but noise and denial? Never mind. -LV > >So I thank you for bringing this up. > > >Is now my argument safe? To be true: I think so, as I have in the > >meantime discovered the "subcountables", so that I cannot be that off- > >road after all... > > >-LV > > >> -- > >> --------------------------- > >> | BBB b \ Barbara at LivingHistory stop co stop uk > >> | B B aa rrr b | > >> | BBB a a r bbb | Quidquid latine dictum sit, > >> | B B a a r b b | altum viditur. > >> | BBB aa a r bbb | > >> ------------------------------ > > David C. Ullrich > > "Understanding Godel isn't about following his formal proof. > That would make a mockery of everything Godel was up to." > (John Jones, "My talk about Godel to the post-grads." > in sci.logic.)
From: Daryl McCullough on 10 Aug 2008 10:04 julio(a)diegidio.name says... >No no, no limits of ratios and similar stuff involved. > >I were just hinting at the common notion of n->oo over a sequence. > >That is the kind of "limit" I was hinting at, and, again, talking >about such limit and the limit of a difference was informal and mostly >analogical Well, for something to be actual mathematics, as opposed to idle chatter, you have to be able to go beyond "informal and mostly analogical" reasoning. Of course, idle chatter can be fun, too, but it's not mathematics. -- Daryl McCullough Ithaca, NY
From: Daryl McCullough on 10 Aug 2008 10:12 julio(a)diegidio.name says... >> (1) [a] a b b a a b a ... >> (2) a [a] a a a a b b ... >> (3) b b [b] b a a b a ... >> (4) a b b [b] a b b b ... >> : ... >> >> (Note, I put a [] around each symbol of the diagonal.) >> >> In this case we get the anti-diagonal by replacing /a/ with /b/ and vice >> versa. Hence we get the sequence >> >> b b a a ... >> >> Now this sequence differs from any sequence in the list by at least one >> symbol. (See below.) With other words, it differs from every entry in >> the list. > > >That is Cantor thesis, and you just make it the usual non-sequitur. > >__It just does not hold as such for infinite sequences, unless one >proves otherwise.__ I am not convinced that you know what a "non-sequiter" is, nor what an "infinite sequence" is, nor what it means to prove a mathematical statement. It appears to me that you are just engaging in idle chatter, not mathematics. -- Daryl McCullough Ithaca, NY >> Slightly more formal approach: >> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ >> >> Claim: If (l_i) is an infinite sequence such that its members l_i are >> infinite sequences of the symbols /a/ and /b/, then there is an infinite >> sequence d (of the symbols /a/ and /b/) such that d is not a member of >> (l_i) (i.e. for all n e N: d =/= l_n). >> >> Proof: Let [l_i]_j be the j-th members of the sequence l_i. We define a >> sequence d = (d_i) with: >> >> / /a/ if [l_i]_i = /b/ >> d_i = { >> \ /b/ if [l_i]_i = /a/ . >> >> Then for every natural number n: d =/= l_n, because for any natural >> number n, the n-th member of d differs from the n-th member of l_n. > > >Ditto: we are talking about infinite sequences, and that is at best a >non sequitur... > >In fact, you keep "proving Cantor with Cantor". Over and over. > >-LV > > >> 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: Daryl McCullough on 10 Aug 2008 10:16 julio(a)diegidio.name says... >Hmm, maybe I get it. It's that I am a "post-cantorian >constructivist" ;) More specifically, you are a mathematical incompetent. >That there are more reals than naturals is not a fact, but a >consequence of the "cantorian" line of reasoning via the diagonal >argument. "cantorian" line of reasoning is just reasoning. What you are replacing it with is not reasoning of any kind. >That very argument is in question, It is only "in question" by mathematical incompetents. >Indeed, from the naturals and (transf.) induction only, I quite don't >get anything like that, and *that* is the toolset you are supposed to >start from. Oh, come on. You don't actually know what transfinite induction is. -- Daryl McCullough Ithaca, NY
From: Aatu Koskensilta on 10 Aug 2008 10:54
julio(a)diegidio.name writes: > How do you dismiss constructive theories? I'd be very interested in > learning what eventually there is to lose. Sadly, the diagonal argument is constructively valid. You will need look elsewhere for vindication. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechen kann, darüber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus |