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 11:24 On 10 Aug, 15:54, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > ju...(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. I'll get it when someone points out the flaw in _my_ argument. I know that Cantor's result is usually accepted even in the constructive domain (though I wouldn't say it is "constructively valid" tout court). That's why I have said "post-cantorian" along with "constructivist". BTW, and in case you really wander: I am looking for no vindication. All that fuzz seems rather the official rule of the house - so to say. As a matter of fact, I am learning my mathematical language here in the groups. -LV > -- > Aatu Koskensilta (aatu.koskensi...(a)uta.fi) > > "Wovon man nicht sprechen kann, darüber muss man schweigen" > - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Aatu Koskensilta on 10 Aug 2008 12:22 julio(a)diegidio.name writes: > No, it doesn't hold for finite as well as infinite index sets. That is > Cantor's result, not a premise. Quite so. Cantor won the Fields Medal in 1987 for his revolutionary proof of what is now known as Cantor's theorem Given two infinite sequences I: N --> O and J: N --> O, I =/= J iff there is an n such that I(n) =/= J(n). Incidentally, before the epochal paper /On extensional equality of infinite sequences in an inner model with a proper class of wooden cardinals/ (Journal of Pointless Twaddle, 34 (I), p. 456 - 324, 1978) it had even been suggested this longstanding open problem might be undecidable in Quine's system ML. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechen kann, darüber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Ben Bacarisse on 10 Aug 2008 12:34 julio(a)diegidio.name writes: > On 10 Aug, 05:28, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: >> ju...(a)diegidio.name writes: >> > On 9 Aug, 16:53, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: >> <snip> >> >> It would be best for me to say >> >> no more unless you define "computable real" and the ordering rule. >> >> > As I can see it, all ordering rules are equivalent modulo the >> > appropriate mapping. The "natural ordering" here I'd say is the usual >> > ordering for the permutations of the digits. With the period after the >> > diagonal element, just for reading purposes: >> >> > 0:0(0) >> > 1:10(0) >> > 2:010(0) >> > 3:1100(0) >> > 4:00100(0) >> > ... >> >> > Given, if I am not mistaken, that all ordering rules are equivalent >> > modulo mapping, interesting results follow, trivially. For instance, >> > the anti-diagonal here is simply the sequence: oo:(1). >> >> > And we can enumerate backwards (again with the period after the >> > diagonal element): >> >> > oo :1(1) >> > oo-1:01(1) >> > oo-2:101(1) >> > oo-3:0011(1) >> > oo-4:11011(1) >> > And, simmetrically, the "inverse" anti-diagonal we get is: 0:(0). >> >> Well I see what you are doing, but i don't see why you think it is >> interesting. You have a representation where every number can be >> written two ways (take the final 1 and replace with 01(1)). With such >> a representation the anti-diagonal can only be constructed if both >> representations are present. > > > I don't know what taking such expansions as -- say -- 0.(9) and 1.(0) > to be equal brings to this argument, and actually if it is pertinent > at all. That is for you to decide. You have two choices either 0.01(1) is equal to 0.10(0) or it is not. I took the usual mathematical definition that they are. You can't then form the anti-diagonal using plain symbol switching because some infinite digits strings are numerically equal to others. The simple solution it to combine the lists. If you go the other way, then your two lists are disjoint and don't enumerate the same set. This seems to be a bigger problem. > The point remains: the list is indeed and already _complete_. It is > the infinite list of all the permutations of the digits in the > infinite decimal expansion. It seems to be missing lots of rationals. All your digit strings by definition have a finite number of 1s (in the first list) or 0s (the second). An digit string with a pattern like 0.10101010(10) can't be on either. >> For example, if you alternate elements from your two lists the >> anti-diagonal is 0.101010101 = 2/3. It illustrates one of a vast >> family of rationals that are not on ether list > > No, you have just given another enumeration order, and again the list > is complete and the anti-diagonal corresponds to the oo-th entry, etc. > etc. Namely, in your example, 2/3, the anti-diagonal, is the oo-th > entry. And we can again enumerate back. The list is still the same and > complete: you have just changed the order. (The actual construction is > maybe slightly subtler, in that for different enumeration rules > (orders) and for each base of representation, there is a *class* (in > the generic sense) of anti-diagonal sequences.) So for any one number I say can't be there (like 0.10(10)) you will say is the oo-th in some other order? Are saying that no single ordering has all the numbers in [0,1] on it? If so, I agree, of course since that is the conventional view. If not, why did you not show me that definitive list? If you are saying that no one finite rule can express such a list, than we agree again (and there is nothing more to discuss). >> : 1/3, 1/5, 1/6... Of >> course pi-3 is missing too, along with all the other transcendentals >> and irrationals in [0, 1]. >> >> Where does defining this countable subset of the rationals get you? > > > It's meant to be the set of (all) the computable reals, surely a > superset of the rationals. Actually a very significant set because of > the importance of computability. Yes, but we'd have to agree on how many interesting numbers are on it first. It looks to be very thin at the moment -- it includes only finite binary fractions. -- Ben.
From: Aatu Koskensilta on 10 Aug 2008 12:33 julio(a)diegidio.name writes: > I'll try, later, to repost the whole thing in the form of some > questions, because I am genuinely and basically asking questions here. Aren't you rather engaged in a noble quest, of unearthing the basic rottenness of Cantorian pseudo-mathematics? -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechen kann, darüber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Balthasar on 10 Aug 2008 12:35
On Sun, 10 Aug 2008 18:10:18 +0200, Balthasar <nomail(a)invalid> wrote: A reply from our resident crank. :-) >> >> If A = (a_i) and B = (b_i) are two sequences with index set I, then >> >> A = B iff for all i e I: a_i = b_i. (*) >> >> This means >> >> A =/= B iff there is an i e I: a_i =/= b_i. (**) >> >> With other words, sequences differ from each other iff they have different >> members for at least one index. (Note that in our case I = IN.) >> >> This holds for finite index sets as well as for infinite index sets >> (i.e. for finite sequences as well as for infinite sequences). >> > No, it doesn't hold for finite as well as infinite index sets. [Crank] > Oh, oh, so the "argument" of our crank boils down to the rejection of (*) and/or (**). (!?) So it seems he must object against extensionality too: If A and B are two sets, then A = B iff for all x: x in A iff x in B. Which in turn means A =/= B iff there is an x: x in A, but x not in B or x in B, but x not in A. @Crank: Note that this holds for finite sets as well as for infinite sets. Oh right, we ARE arguing in the context (i.e. framework) of set theory. Something invented/introduced by CANTOR - to be able to deal with finite as well as _infinite_ sets. Right. :-) 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) |