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 8 Aug 2008 12:54 On Aug 8, 9:47 am, ju...(a)diegidio.name wrote: > The "limit" is of course induction. Please state EXACTLY what induction schema you have in mind. MoeBlee
From: Aatu Koskensilta on 8 Aug 2008 12:53 julio(a)diegidio.name writes: > The "limit" is of course induction. Alas, that makes no sense whatsoever. But I see someone has already rushed in to the rescue, asking "WHAT limit?" so you're in safe hands. I'll make a hasty retreat myself. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechen kann, darüber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: julio on 8 Aug 2008 13:03 On 8 Aug, 17:53, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > ju...(a)diegidio.name writes: > > The "limit" is of course induction. > > Alas, that makes no sense whatsoever. Doesn't it? Thanks for the moral support... -LV > But I see someone has already > rushed in to the rescue, asking "WHAT limit?" so you're in safe > hands. I'll make a hasty retreat myself. > > -- > Aatu Koskensilta (aatu.koskensi...(a)uta.fi) > > "Wovon man nicht sprechen kann, darüber muss man schweigen" > - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Balthasar on 8 Aug 2008 13:12 On Fri, 8 Aug 2008 09:44:09 -0700 (PDT), MoeBlee <jazzmobe(a)hotmail.com> 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. >> > WHAT limit? You need to DEFINE "limit" in terms of some topology, > metric, ordering, or whatever. We don't just use the word "limit" > without the context of the EXACT sense of a limit as it has been > DEFINED. > > Moreover, the anti-diagonal differes from every entry in the list. > That's all that is required to show that the anti-diagonal is not on > the list. > To make a long story short: we are not interested in the "limit entry" (whatever that may be), but in the fact that the diagonal differs from each and any entry in the list. Of course there's still a loophole mentioned by WM, see signature below. 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 8 Aug 2008 13:18
On 08 Aug 2008 19:44:59 +0300, Aatu Koskensilta <aatu.koskensilta(a)uta.fi> 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. >> > Wonderful. I wonder how many people will rush in to the rescue, asking > "What limit entry?" or exclaiming most ferociously "There is no limit > entry!" > Right. I just wrote: "To make a long story short: we are not interested in the "limit entry" (whatever that may be), but in the fact that the diagonal differs from each and any entry in the list." Not though that there's still a loophole mentioned by WM! (See signature below.) 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) |