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 9 Aug 2008 21:47 On 9 Aug, 21:27, herbzet <herb...(a)gmail.com> wrote: > ju...(a)diegidio.name wrote: > > 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. > > One problem here is that there may not be a unique limit point to > the sequence enumerated by the list. Sorry, I don't get it. Could you be more specific? I also suppose this is the same objection as Balthasar's and Mr McCullough's. But I don't know what you are hinting at here. > Example: Enumerate in some fashion the rational numbers in [0, 1]: > > q1, q2, q3, ... > > Then each rational qi is a limit point of the sequence, as is > each irrational number in [0, 1]. (A Cantorian might remark > that there are more limit points than entries in the list ...) I don't know what that means, for each qi to be a limit point of the sequence. -LV > Certainly in this case the diagonal number will be a limit > point of the sequence, though different from (unequal to) > every member of the sequence. > > (It is of course a theorem of analysis that a bounded sequence > of real numbers will have a limit point.) > > -- > hz
From: julio on 9 Aug 2008 21:59 On 9 Aug, 16:53, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: > Ben Bacarisse <ben.use...(a)bsb.me.uk> writes: > > ju...(a)diegidio.name writes: > > <snip> > >> 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. And I mean we can enumerate forwards or backwards the > >> infinite list of the computable reals, say in [0, 1], where 1 is the > >> usual diagonal at 0 and viceversa, 0 is the inverse diagonal at 1. > >> Actually, given an ordering rule over the list, we can enumerate > >> forwards or backwards at some specific points, but I'll leave the > >> details out. > > > So order the list of "computable reals" in [0, 1] (I use quotes > > because I am quoting you -- I don't know what these things are yet) to > > get r1, r2, r3... and consider the list of numbers r(n): > > > r1+(r2-r1)/2, r1+(r2-r1)/3, r1+(r2-r1)/4,... r1+(r2-r1)/(n+1),... > > > All of these look computable to me so this list is simply a > > permutation of r1, r2, r3... Which one is equal to r1 and which one > > is equal to r2? What follows from r(x) = r1 and/or r(y) = r2? > > I now see that "permutation" is not correct. In fact, in trying to > repair this argument, I now suspect that you define "computable" so > you are actually enumerating the rationals in [0, 1] (or at least some > other countable subset of the reals). Yes, I am definitely enumerating a computable set, what I have called "the computable reals". > 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). -LV > A > reference would be fine. > > -- > Ben.
From: julio on 9 Aug 2008 22:29 On 10 Aug, 02:59, ju...(a)diegidio.name wrote: > On 9 Aug, 16:53, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: > > > > > > > Ben Bacarisse <ben.use...(a)bsb.me.uk> writes: > > > ju...(a)diegidio.name writes: > > > <snip> > > >> 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. And I mean we can enumerate forwards or backwards the > > >> infinite list of the computable reals, say in [0, 1], where 1 is the > > >> usual diagonal at 0 and viceversa, 0 is the inverse diagonal at 1. > > >> Actually, given an ordering rule over the list, we can enumerate > > >> forwards or backwards at some specific points, but I'll leave the > > >> details out. > > > > So order the list of "computable reals" in [0, 1] (I use quotes > > > because I am quoting you -- I don't know what these things are yet) to > > > get r1, r2, r3... and consider the list of numbers r(n): > > > > r1+(r2-r1)/2, r1+(r2-r1)/3, r1+(r2-r1)/4,... r1+(r2-r1)/(n+1),... > > > > All of these look computable to me so this list is simply a > > > permutation of r1, r2, r3... Which one is equal to r1 and which one > > > is equal to r2? What follows from r(x) = r1 and/or r(y) = r2? > > > I now see that "permutation" is not correct. In fact, in trying to > > repair this argument, I now suspect that you define "computable" so > > you are actually enumerating the rationals in [0, 1] (or at least some > > other countable subset of the reals). > > Yes, I am definitely enumerating a computable set, what I have called > "the computable reals". > > > 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). > > -LV That is actually an enumeration of all the computable reals in: [0.(0), 1.(1)] -LV > > A > > reference would be fine. > > > -- > > Ben.
From: julio on 9 Aug 2008 22:35 On 10 Aug, 03:29, ju...(a)diegidio.name wrote: > That is actually an enumeration of all the computable reals in: > > [0.(0), 1.(1)] Sorry, should read: [0.(0), 0.(1)] -LV
From: julio on 9 Aug 2008 23:13
On 10 Aug, 02:47, ju...(a)diegidio.name wrote: > On 9 Aug, 21:27, herbzet <herb...(a)gmail.com> wrote: > > > ju...(a)diegidio.name wrote: > > > 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. > > > One problem here is that there may not be a unique limit point to > > the sequence enumerated by the list. > > Sorry, I don't get it. Could you be more specific? > > I also suppose this is the same objection as Balthasar's and Mr > McCullough's. But I don't know what you are hinting at here. > > > Example: Enumerate in some fashion the rational numbers in [0, 1]: > > > q1, q2, q3, ... > > > Then each rational qi is a limit point of the sequence, as is > > each irrational number in [0, 1]. (A Cantorian might remark > > that there are more limit points than entries in the list ...) > > I don't know what that means, for each qi to be a limit point of the > sequence. Hmm, maybe I get it. It's that I am a "post-cantorian constructivist" ;) That there are more reals than naturals is not a fact, but a consequence of the "cantorian" line of reasoning via the diagonal argument. That very argument is in question, then the rest is a consequence, just as true as its premise. 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. -LV > -LV > > > Certainly in this case the diagonal number will be a limit > > point of the sequence, though different from (unequal to) > > every member of the sequence. > > > (It is of course a theorem of analysis that a bounded sequence > > of real numbers will have a limit point.) > > > -- > > hz |