halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: Daryl McCullough on 9 Aug 2008 08:28 julio(a)diegidio.name says... >Shall I point you too to some article on the diagonal argument? Uh, *your* the one who doesn't understand it. So people should be pointing *you* to relevant articles. For example: http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument http://mathworld.wolfram.com/CantorDiagonalMethod.html http://www.mathpages.com/home/kmath371.htm Cantor also gave, before his diagonal proof, an alternative proof of the uncountability of the reals: http://en.wikipedia.org/wiki/Cantor%27s_first_uncountability_proof -- Daryl McCullough Ithaca, NY
From: jacko on 9 Aug 2008 08:39 On 8 Aug, 10:09, RichD <r_delaney2...(a)yahoo.com> wrote: > I heard someone say recently, "The proof of the Turing > machine halting problem is an example of diagonalization." I'm sure i saw a 'proof'' using the set of all programs example.. > I don't see that. As I recall, it's proof by contradiction; > assume a program which accomplishes the goal, feed > the code of this program to itself, etc., ad absurdum. QED > > Whereas diagonalization consists of constructing a list, > then constructing a new object not in the list, etc. This is very logically flawed, because the thing constructed i the next element of such a lst, therefore it is always possible to construct something extra which is in the list, as well as show something is not in the list yet. order of reals is same as rationals :i.e. z^2. proof: place all Zintegers in a list. do this again. Then place a mirror with a little black spot point in fromt of one set. Now all reals are the sum f an element from one list and an element from the other. Z*Z = Z^2. Now this is obvoius, and requires no proof by negation, so the flaws of such negation proofs discovered via godel can not be seen in it. In relation to turing halting. I can say no more than DO'T use diagonalization and proof by negation if there are oher options. cheers jacko
From: jacko on 9 Aug 2008 08:55 nd just for the record pi is an infinite rational. proof: cos pi is defined as an infinite summation of rationals. summing rationals ALWAYS produces a rational.
From: Ben Bacarisse on 9 Aug 2008 09:36 julio(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? -- Ben.
From: cplxphil on 9 Aug 2008 10:16
> nd just for the record pi is an infinite rational. > > proof: cos pi is defined as an infinite summation of rationals. > summing rationals ALWAYS produces a rational. Pi is irrational. A finite sum of rationals is rational, but an infinite sum need not be. How would you express pi as the quotient of two integers (the definition of a rational)? |