halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: herbzet on 11 Aug 2008 18:14 herbzet wrote: > julio(a)diegidio.name wrote: > > herbzet wrote: > > > > > Such is the degree of my confusion. > > > > And you keep insisting with your confusion while disregarding my > > explanations. How will we get out of such empasse? > > Well, I'm not that bright. > > > 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? > > > Then there is the formal definition and construction, which you have > > up to here ignored, although that that should be the reference point > > for any serious debate, that too I have repeated over and over and > > over. Ignored from you up to now. > > Well, I wasn't sure that you didn't mean "the limit point of the list" > which was my best guess at what you meant (though Daryl beat me > to making this interpretation). > > Now that I know that the limit entry is the oo-th entry of the list, > I'll look again at your previous posts to other people to find out > exactly what the oo-th entry is. I must say though, that I doubt > that I'm going to find that the difference between the diagonal of > a list and the oo-th entry of the list tends to zero, not least > because we can construct different diagonal numbers off the same > list. Will they all tend to the oo-th entry? > > > Why should I rewrite it again, which would be maybe the 10-th time in > > less than a week? Will you eventually just "read"? > > Well, I'll give it a try. Stand by. I've read over your posts of the last week and considerably farther back. I see nothing that I can understand as a definition or construction of the oo-th member of a list of reals in [0, 1], except a vague suggestion that it is formed by (transfinite?) induction on the members of the list. So I doubt that this conversation is worth pursuing for either of us. I still wonder, though, how this putative oo-th entry can approximate all the various anti-diagonal numbers we could construct from a given list of reals in [0, 1]. It must be a rather magical real number. If there's a simple answer, I'd be interested in hearing it. Otherwise, it's probably best that we just drop the matter. -- hz
From: Ben Bacarisse on 11 Aug 2008 20:57 julio(a)diegidio.name writes: > On 10 Aug, 17:46, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: >> ju...(a)diegidio.name writes: >> > On 10 Aug, 05:42, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: >> >> ju...(a)diegidio.name writes: >> >> <snip> >> >> >> > In fact, you keep "proving Cantor with Cantor". Over and over. >> >> >> I have not see anyone make a proof that starts by assuming that the >> >> set is uncountable or even that uncountable sets exist. I certainly >> >> have not seen anything from you to explain the circularity you claim >> >> to see. >> >> > You might be confused between my objections to Balthasar and my >> > objections to Cantor's argument. >> >> I may well be. I was hoping you'd address the questions I asked >> seeking clarification. > > But you have not clarified if you are after my objections to Blathasar > and co. or to Cantor's argument. The circularity and misunderstanding > is in Blathasar and co's, the problem with Cantor is much more > subtle. All of my questions asking for clarification are dealt with below... >> Something, somewhere, in that chain of >> reasoning leading to the cardinality of the power set is something >> that you do not accept. <snip> >> I don't see the problem, but equally I don't see the point in batting >> this back and forth in a plain text medium. If you have an alternate >> axiom set you prefer > > So you too now after an axiomatization? The naturals plus transfinite > induction is the asnwer I have repeatedly given. It does not hurt to repeat oneself a bit. "The naturals plus transfinite induction" is not so very much to type. I can't see how adding transfinite induction leads you to reject the proofs that have been offered. I asked for axioms to try to understand what it was about these proofs that you reject. -- Ben.
From: Ben Bacarisse on 11 Aug 2008 21:16 julio(a)diegidio.name writes: > On 10 Aug, 18:46, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: <snip> >> I am at a loss to know what is missing but I have a suspicion from >> another sub-thread. The binary digits example he posted has a >> problem: the conventional anti-diagonal construction (by symbol >> manipulation only) yields a string with value already on the list >> (because values on the list have duplicate representations as finite >> binary strings). I suspect he has been thrown by this apparently >> miraculous "hole" in the conventional construction. > > I frankly don't know which hole you are refering to in the > conventional construction. I have the slight feeling that you may > still be a bit confused as to what's in "my" list, because your > remarks do not apply. > > The list, as I have defined it, is just "complete": it is the list of > all the permutations of the digits over the infinite decimal > expansion. There is no "duplicates": duplicates come out from a > further definition about some equalities, defiition and equalities > that are absolutely irrelevant here (someone has pointed out, although > of course attributing the error to me, that we are manipulating > symbols, not really "numbers"). You have to decide for yourself (since you are the one defining this list) whether the bit strings are just symbols or if they are numbers. You must make that call. If you say they are numbers then 0.1 = 0.01(1) and the anti-diagonal must be made from a list that contains both these strings. If you say they are symbol strings and that 0.1 =/= 0.01(1) then your two lists are disjoint and can't enumerate the same interval from opposite ends. > The list is complete of all the possible decimal expansions: that is, > it is the list off all the _computable reals_, includind the rationals > and all computable irrationals. Every one of your numbers (or bit strings -- you get to decide) has a finite number of ones or zeros (depending on which list it is from). Thus a repeating pattern like 0.10(10) can't be there. You can say that the oo-th element is this pattern, but 0.10(10) is only one of a vast number of repeating patterns that are missing (there are other non-repeating patters that are missing too, but that can wait). The oo-th element can't be all of the missing items at once. You have a particularly simple way to refute this if I have got it wrong, because your lists follow such a simple pattern. You should be able to give a formula for the n such that L(n) = 0.10(10). You can have a list item l(oo), and for that reason you need to tell be where on you list at least two such patterns are. I'll take 0.10(10) and, say, 0.01(01). If you interpret you bit strings as numbers (you certainly initially claimed to do this) then you can blow my argument out of the water with a formula for the position in your list of, say, 1/3k for k = 1, 2, 3... and so on. -- Ben.
From: David C. Ullrich on 12 Aug 2008 05:29 On Mon, 11 Aug 2008 02:40:03 -0700 (PDT), julio(a)diegidio.name wrote: >On 11 Aug, 09:26, David C. Ullrich <dullr...(a)sprynet.com> wrote: >> On Sun, 10 Aug 2008 08:24:40 -0700 (PDT), ju...(a)diegidio.name wrote: > >> >I'll get it when someone points out the flaw in _my_ argument. >> >> Maybe you didn't notice, but many people have pointed >> out many flaws. > >Not only I noticed, I have exactly noticed who has been saying what. You have? Good. Tell us - who has been saying that your argument showing that P(N) is countable is correct? Or close to correct? >> These "post-cantorians" only exist in your imagination. > >That's just your permanent war, get lost with it. Right. Name one "post-cantorian", other than people you've seen here on sci.math or sci.logic. >> What you _seem_ to be learning is two techniques, which >> work very well together: (i) simply ignore careful explanations >> of your errors (ii) complain that there's no explanation given >> in posts that don't repeat the explanations. > >That you are intellectually dishonesty and void I have learnt. Right. Give one example of something I've said that's not universally accepted by mathematicians. >-LV 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 12 Aug 2008 09:37
herbzet says... >I've read over your posts of the last week and considerably farther >back. I see nothing that I can understand as a definition or >construction of the oo-th member of a list of reals in [0, 1], >except a vague suggestion that it is formed by (transfinite?) >induction on the members of the list. It doesn't actually matter what the oo-th member of the list is. Diagonalization can produce as many new numbers as you like (as long as you only like countably many). So we can alter Cantor's diagonization procedure to produce two (or however many) new reals. For example, in base-10, if you have an infinite list of decimal expansions of reals between 0 and 1, you can produce two new reals d1 and d2 that are not on the list: Let r(n)[m] = decimal place number m of real number n in the list. Let d1[m] = decimal place number m of d1. Let d2[m] = decimal place number m of d2. Then define d1 and d2 as follows: If r[n][n] < 5, then d1[n] = 6 d2[n] = 7 If r[n][n] > 5, then d1[n] = 2 d2[n] = 3 Then d1 and d2 will be two *different* reals that are not on the list. If d1 happens to be r(oo) (whatever that is), it will certainly *not* be the case that d2 is equal to r(oo), since d1 is unequal to d2. -- Daryl McCullough Ithaca, NY |