Proofs of Church's Theorem for FOL: Philosophy Forums

Philosophy Forums » Logic and Philosophy of Math » Proofs of Church's Theorem for FOL » Proofs of Church's Theorem for FOL

Proofs of Church's Theorem for FOL

Page: 1 2

Proofs of Church's Theorem for FOL

moonlight
Lunatic

Usergroup: Members
Joined: Oct 09, 2005
Location: stuck on earth
Total Topics: 17
Total Posts: 535

Posted 03/28/08 - 03:17 PM:	#26
If the row existed: the Oracle wouldn't: it contradicts the assumption that the table is done. Oracle stands for: completed table. Does it not? moonlight.
All are lunatics, but he who can analyze his delusion is called a philosopher. - Ambrose Bierce -

7
Graduate

Usergroup: Members
Joined: Mar 23, 2008
Total Topics: 3
Total Posts: 160

Posted 03/28/08 - 03:26 PM:	#27
Well, the row has to exist. You will always be able to diagonalize, thereby creating a new row distinct from every preceding row. I think the way to describe this is to say that the new row is a 'throw-away' that doesn't denote a machine. There must be throw-away strings or every string could be coupled with a distinct machine, which would contradict the fact that the machines are countable and the strings aren't.

moonlight
Lunatic

Usergroup: Members
Joined: Oct 09, 2005
Location: stuck on earth
Total Topics: 17
Total Posts: 535

Posted 03/28/08 - 03:34 PM:	#28
7 wrote: Well, the row has to exist. You will always be able to diagonalize, thereby creating a new row Exactly: which means, the table can't be completed. So there is no Oracle. So the assumption was false. You are instead trying to maintain that the assumption is true. To do so, you say: the new rows don't denote Turing machines. If that is the case: the table doesn't denote the Oracle. Well, at least not the one we started out with. Take some time to think about it. I'm off to bed... been awake too long. Good night, moonlight.
All are lunatics, but he who can analyze his delusion is called a philosopher. - Ambrose Bierce -

7
Graduate

Usergroup: Members
Joined: Mar 23, 2008
Total Topics: 3
Total Posts: 160

Posted 03/28/08 - 03:45 PM:	#29
You are instead trying to maintain that the assumption is true. To do so, you say: the new rows don't denote Turing machines. If that is the case: the table doesn't denote the Oracle. Well, at least not the one we started out with. The oracle isn't intended to list every infinite string. All it's supposed to do is decide the halting problem for every TM. If there exist rows that do not denote machines (and I maintain that there are such rows), the oracle does not have to deal with them. Take some time to think about it. I'm off to bed... been awake too long. Good night, moonlight. Take it easy. I'll try to think of another way to move this discussion forward. I'll ask the smartest comp sci and math professor I know about this issue next week.

moonlight
Lunatic

Usergroup: Members
Joined: Oct 09, 2005
Location: stuck on earth
Total Topics: 17
Total Posts: 535

Posted 03/28/08 - 03:57 PM:	#30
7 wrote: All it's supposed to do is decide the halting problem for every TM. And how does it do that? By listing for each of the infinitely many machines, an infinitely long string. 'Infinitely' = countable infinity in both occurences here. So obviously it can never finish the job, since you can always derive new rows. So the assumption is false: the Oracle doesn't exist. 7 wrote: If there exist rows that do not denote machines You are changing the definition of the table, i.e. the Oracle. Each row is by definition a Turing machine. That's how we defined the table in the first place. If you want to say some rows aren't machines, then tell me: where do these rows begin? m=1000? m=1000 Googol? How do you choose this value? 7 wrote: Take it easy. I'll try to think of another way to move this discussion forward. I'll ask the smartest comp sci and math professor I know about this issue next week. Yes, good idea. Do let the thread know what the response was. moonlight. P.S: I couldn't help myself but to come back, check and answer.
All are lunatics, but he who can analyze his delusion is called a philosopher. - Ambrose Bierce -

7
Graduate

Usergroup: Members
Joined: Mar 23, 2008
Total Topics: 3
Total Posts: 160

Posted 03/28/08 - 04:58 PM:	#31
And how does it do that? By listing for each of the infinitely many machines, an infinitely long string. 'Infinitely' = countable infinity in both occurences here. So obviously it can never finish the job, since you can always derive new rows. So the assumption is false: the Oracle doesn't exist. Right, the list contains each of the countably infinitely many machines. What I'm suggesting is that when we start diagonalizing, these new rows don't correspond to machines because if they did, it would violate the assumption that we have an enumeration of the machines. I don't see why we're disagreeing. We both agree that infinite strings of 1s and 0s are uncountable and TMs are countable, so we should be able to agree that there can't be a machine for every string of 1s and 0s that we can create. You are changing the definition of the table, i.e. the Oracle. Each row is by definition a Turing machine. That's how we defined the table in the first place. If you want to say some rows aren't machines, then tell me: where do these rows begin? m=1000? m=1000 Googol? How do you choose this value? It's the same as asking: since the reals can't be put into a bijection with N, but some subset of them can be, at exactly what point does a subset of the reals become 'too big' to be placed into a bijection with N? I don't know how to answer the question except to say that this happens when we pick a subset that's uncountable. In any event, I know some subset of the reals can't be put into the bijection. And I know that the set of infinite binary strings is larger than the set of TMs, so we can't pair them off(this has been proved in this thread). Yes, good idea. Do let the thread know what the response was. Sure, will do.

7
Graduate

Usergroup: Members
Joined: Mar 23, 2008
Total Topics: 3
Total Posts: 160

Posted 03/29/08 - 12:14 AM:	#32
There's a Turing-style proof of Church's Theorem in Cutland's text that is a lot smoother than the one I recall. I'll try to find it in google books or, if I can't and someone really wants to see it, I can reproduce it in a post. Looking at the Cutland reminds me of how abysmal the Boolos, Burgess, and Jeffrey is.

7
Graduate

Usergroup: Members
Joined: Mar 23, 2008
Total Topics: 3
Total Posts: 160

Posted 03/29/08 - 01:16 AM: Subject: Here we are....	#33
http://books.google.com/books?id=wAstOUE36kcC&pri...

Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81

Posted 03/29/08 - 11:56 AM:	#34
Thanks for the link (plus.maths.org) moonlight. I've read the explanation of the halting problem but there's something I can't clearly understand. In the end , the author states something like this : So D (the new machine we've created by diagonalizing) must belong to the set of the other machines (meaning D € {Td} for some d}. But we defined it to give a different answer from Td with input d. Does this mean that if D were to belong to the {Td} then it wouldn't have given this new string of inputs we've just created by diagonalizing? That actually if D were to belong to the Td's then it would have given something that would have alredy been in the table itself. So D (the new "machine" from the diagonalization) cannot be a machine because if it were we would have seen it in the table but it is not there.Am I understanding it correctly? 7: are you looking at Church's indecidability theorem in the Boolos/Jeffrey book?Are you looking at the proof which uses the gödel numbers of theorems of Q? If you're looking at that same thing, could you please explain to me why Boolos writes that f(n)=1(q(399(n2)))? He says that f(n) is the gödel number of (C->A). How does the coding work? I unfortunatly don't have the whole book only some copies of some chapters of this book. If I remember well they explain all that stuff and turing machines in the beginning of the book.

moonlight
Lunatic

Usergroup: Members
Joined: Oct 09, 2005
Location: stuck on earth
Total Topics: 17
Total Posts: 535

Posted 03/29/08 - 01:57 PM:	#35
Hi Beeboo, Beeboo wrote: Thanks for the link (plus.maths.org) moonlight. My pleasure. Beeboo wrote: Does this mean that if D were to belong to the {Td} then it wouldn't have given this new string of inputs we've just created by diagonalizing? That actually if D were to belong to the Td's then it would have given something that would have alredy been in the table itself. Yes, exactly. If D was in the table, well then... it would have been in the table. The string created for D would have been in the table. But obviously this isn't the case, since D is by definition, different in at least one cell to every other row in the table. Beeboo wrote: So D (the new "machine" from the diagonalization) cannot be a machine because if it were we would have seen it in the table but it is not there. Am I understanding it correctly? No, it doesn't mean that D cannot be a machine. D can perfectly well be a machine. Why not? In fact: simply presume that you forgot to write D in the table: we are humans after all and sometimes make mistakes. It's not a crime to correct them right? So just add D to the table, and start all over again. The problem is that now, you will generate a new D, once again. So to answer your question: no, it doesn't mean D isn't a machine. It can be perfectly well be a machine: we added it to the table just now didn't we? But that doesn't change the argument. So, what it means instead, is that the table {Td} cannot exist as described. Remember that the author originally posits, assumes, supposes, that he has a finished chart {Td}, sitting on his desk. Well I'm adding the "sitting on his desk" bit for emphasis obviously. He doesn't actually, in reality, have anything on his desk. He is just assuming, considering the possibility, of having a finished chart on his desk, while sitting in his chair, looking at the ceiling, having a smoke, with his legs - not the chart - on his desk. And he goes on to do some reasoning. This reasoning ends up contradicting the original assumption: that he has a finished chart on his desk. So he jumps out of his chair and exclaims: "the assumption must be incorrect. I can't have such a chart on my desk! {Td} cannot exist. Not even in my dreams can it be a completed chart, and sit on my desk, if my dreams are to be rational ones. Not even if my desk was as big the universe, or denumerably infinitely large!!". His boss passes by, hears him, sees him and nothing on the desk, gets mad, and fires him. So it means: - The table cannot be drawn. - The table cannot be completed. - The table cannot be computed. - So: the Halting Problem, is undecidable. - and it can get you fired. (note to readers: I'm just joking on this line). The contradiction, must result from the assumption because there is nothing wrong with the reasoning, and there definitely is a contradiction. So the assumption must be false. The argument is therefore a reduction to the absurd. Reductio ad absurdum in latin, and proof by contradiction in proper English. I hope it helps, Cordially, moonlight. Edited by moonlight on 03/29/08 - 02:04 PM. Reason: spilling mistake
All are lunatics, but he who can analyze his delusion is called a philosopher. - Ambrose Bierce -

Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81

Posted 03/29/08 - 02:36 PM:	#36
Thank you for your answer and for correcting me moonlight. Exactly, D has no reason not to be a machine. Our problem here is that we have a countable set of Td's but if we were to add this machine D it will just prove that our set of Td's is uncountable which is contradicting our hypothesis. Nice metaphore by the way

moonlight
Lunatic

Usergroup: Members
Joined: Oct 09, 2005
Location: stuck on earth
Total Topics: 17
Total Posts: 535

Posted 03/29/08 - 02:48 PM:	#37
Hi Beeboo, No problem. Glad I could help. Cordially, moonlight.
All are lunatics, but he who can analyze his delusion is called a philosopher. - Ambrose Bierce -

7
Graduate

Usergroup: Members
Joined: Mar 23, 2008
Total Topics: 3
Total Posts: 160

Posted 03/29/08 - 05:30 PM:	#38
Beeboo wrote: 7: are you looking at Church's indecidability theorem in the Boolos/Jeffrey book?Are you looking at the proof which uses the gödel numbers of theorems of Q? If you're looking at that same thing, could you please explain to me why Boolos writes that f(n)=1(q(399(n2)))? He says that f(n) is the gödel number of (C->A). How does the coding work? I unfortunatly don't have the whole book only some copies of some chapters of this book. If I remember well they explain all that stuff and turing machines in the beginning of the book. I know the section of the book that you mean, but I don't know where you're getting the numbers. What they're saying is that that Q's axioms can be coded (because they're just a finite set of sentences), negation can be coded, and so on. The formula is (~C v A) where C is the conjunction of Q's axioms and A is an arbitrary sentence of Q's language. To give you an idea, we assign a number to every symbol in the language. If seq is a sequence of symbols a, b, c, ... then we can code it by taking 2 to the power of a . 3 to the power of b . 5 to the power of c,... So we can code (~C v ) in this way, although it is not a wff. The function f the authors describe decodes the number of (~C v ) by finding the exponents of prime factors, then plugs in the sentence A before the right parenthesis, then it recodes the formula. The conclusion of the argument is that if the set of valid sentences were decidable, then the (~C v A) sentences would recursively decidable. Then we could recursively decide any Q sentence A by checking if (~C v A) is valid.

7
Graduate

Usergroup: Members
Joined: Mar 23, 2008
Total Topics: 3
Total Posts: 160

Posted 03/29/08 - 06:02 PM:	#39
Beeboo wrote: Thank you for your answer and for correcting me moonlight. Exactly, D has no reason not to be a machine. Our problem here is that we have a countable set of Td's but if we were to add this machine D it will just prove that our set of Td's is uncountable which is contradicting our hypothesis. Nice metaphore by the way The part of your post starting with "Our..." is the point I was making earlier. The proof doesn't seem to go anywhere if you can't add the new machine D.

Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81

Posted 03/29/08 - 06:12 PM:	#40
Thank you for your explanation 7. I see the process now. It is based on the fundamental theorem of algebra, meaning that every integer can be written as a product of primes powered by integers. What I don't see is that you say that f(n)=1(q(399(n2))) codes only (~C v ), but it seems like f(n) is coding the whole (C->A), with q the gödel number of C and n the gödel number of A (with A a theorem of Q. Is there any consequences if A is only an arbitrary sentence in the language of Q? It seems like A has to be a theorem of Q otherwise C->A is not valid.) Yes it's true, the end of the argument says that the set of gödel number of theorems of Q is not recursive so L is not decidable( with p the set of gödel numbers of theorems of L, and if this set is recursive so is the set of gödel numbers of theorems of Q (page 176)

Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81

Posted 03/29/08 - 06:17 PM:	#41
7 wrote: The part of your post starting with "Our..." is the point I was making earlier. The proof doesn't seem to go anywhere if you can't add the new machine D. Yes 7, that's what it seems like I've seen. But actually you always can add a new machine D, as the construction of the cantorian argument is made in such a way that it allows you to do so as many times as you want(edit:as many times as you want if D turns out to be inside the table!). You lay out your table. And then you built your diagonale, and this diagonale is constructible from the table. Or maybe there's something I'm not seeing here...Why do you think we wouldn't be able to add the new machine D? added: to go back to your original question, maybe we can prove church undecidability theorem with Turing machines by choosing a function f that takes theorems of Q as inputs and gives you their godel numbers as outputs, create the table and demonstrate with cantorian arguments that it is not recursive or something like that. How could we do? Edited by Beeboo on 03/29/08 - 06:36 PM

moonlight
Lunatic

Usergroup: Members
Joined: Oct 09, 2005
Location: stuck on earth
Total Topics: 17
Total Posts: 535

Posted 03/29/08 - 09:34 PM:	#42
Hi Beeboo, 7, Let me try to explain this one more time. - Suppose I show up with a countably infinite list of integers: 1, 2, 3, 4, 5, 6... up to infinity. - Next I tell you that each integer denotes a machine. - Then I say: "oops! I forgot a machine". So I add it to the list. Simple enough. - And keep doing this on and on and on, because I'm a forgetful fool. Clearly, I can keep on forever, I will never have an uncountably infinity of machines (or integers, if you prefer). The total number of machines remains infinitely countable. I am counting by adding them, one by one, after all, so what else could it be? So by adding machines to the list T1, T2, T3, etc.. in this way we are not getting an uncountable number of machines: it is still a countable number of machines. However, what we are getting is an uncountable number of (machine-input) pairs. As bizzare as it may sound: the table, if it actually existed would have countably infinite long sides, but an uncountably infinite number of cells. This is what needs to be understood here. Let me try to explain further. Let countable infinity be denoted 'inf_0' and uncountable infinity be denoted 'inf_1'. Intuitively, one would think that the area of the table is (inf_0 x inf_0) = (inf_0)^2, which is still... inf_0. But that would only be the case if every cell is empty. Or if every cell in the table is filled with a single same symbol, like '£' for instance. But when you start allowing 2 symbols to appear in a cell, just consider what happens to the first row: ROW 1: Every cell has 2 possibilities, and there are inf_0 cells, so that gives you (2^inf_0) configurations, which is exactly the definition of inf_1: uncountable infinity. ...which means that if you wanted to list every possible row, you would need an uncountable infinity of rows. Even though you only have a countable infinity of rows in the beginning! So what this is saying is that if you force every cell to be filled with the same symbol, then the table is still countably infinite in size. As soon as you allow more than one symbol, then the table becomes uncountably infinite in size. Hope it helps in clearing this little issue we're having here. Cordially, moonlight.
All are lunatics, but he who can analyze his delusion is called a philosopher. - Ambrose Bierce -

7
Graduate

Usergroup: Members
Joined: Mar 23, 2008
Total Topics: 3
Total Posts: 160

Posted 03/29/08 - 11:13 PM:	#43
Beeboo wrote: Thank you for your explanation 7. I see the process now. It is based on the fundamental theorem of algebra, meaning that every integer can be written as a product of primes powered by integers. What I don't see is that you say that f(n)=1(q(399(n2))) codes only (~C v ), but it seems like f(n) is coding the whole (C->A), with q the gödel number of C and n the gödel number of A (with A a theorem of Q. Is there any consequences if A is only an arbitrary sentence in the language of Q? It seems like A has to be a theorem of Q otherwise C->A is not valid.) Yes it's true, the end of the argument says that the set of gödel number of theorems of Q is not recursive so L is not decidable( with p the set of gödel numbers of theorems of L, and if this set is recursive so is the set of gödel numbers of theorems of Q (page 176) First, we have different editions. In mine, page 176 is part of the completeness theorem. The reason I had asked you about the numbers is that in my book, I don't see "1(q(399(n2)))" in the proof of Church's Theorem that we're discussing. There aren't any numbers in that section of the book at all, which is why I didn't and still don't know what they mean. Second, let's move from the question of whether (C -> A) where A is arbitrary is FOL decidable to the question of whether A is decidable in Q, that is, (Q l- A). Well, Q is semi-decidable(as is the predicate calculus). If A is a theorem of Q, then we can decide this in a finite amount of time. All of the proofs are finite sequences of formulas, so we can start enumerating the proofs, and eventually we will find one of A, if it is there to be found. On the other hand, if A is not a theorem, we can go through this process forever without coming to a halt. The point is that (C l- A) is decidable, if A is a Q-theorem. But if A is arbitrary, then it's not. For the same reason, it is essential that A is arbitrary in (C -> A) because if A is a Q theorem, then (C -> A) will be decidable, too.

7
Graduate

Usergroup: Members
Joined: Mar 23, 2008
Total Topics: 3
Total Posts: 160

Posted 03/29/08 - 11:42 PM:	#44
moonlight wrote: Hi Beeboo, 7, Let me try to explain this one more time. - Suppose I show up with a countably infinite list of integers: 1, 2, 3, 4, 5, 6... up to infinity. - Next I tell you that each integer denotes a machine. - Then I say: "oops! I forgot a machine". So I add it to the list. Simple enough. - And keep doing this on and on and on, because I'm a forgetful fool. Clearly, I can keep on forever, I will never have an uncountably infinity of machines (or integers, if you prefer). The total number of machines remains infinitely countable. I am counting by adding them, one by one, after all, so what else could it be? So by adding machines to the list T1, T2, T3, etc.. in this way we are not getting an uncountable number of machines: it is still a countable number of machines. However, what we are getting is an uncountable number of (machine-input) pairs. As bizzare as it may sound: the table, if it actually existed would have countably infinite long sides, but an uncountably infinite number of cells. This is what needs to be understood here. Let me try to explain further. Let countable infinity be denoted 'inf_0' and uncountable infinity be denoted 'inf_1'. Intuitively, one would think that the area of the table is (inf_0 x inf_0) = (inf_0)^2, which is still... inf_0. But that would only be the case if every cell is empty. Or if every cell in the table is filled with a single same symbol, like '£' for instance. But when you start allowing 2 symbols to appear in a cell, just consider what happens to the first row: ROW 1: Every cell has 2 possibilities, and there are inf_0 cells, so that gives you (2^inf_0) configurations, which is exactly the definition of inf_1: uncountable infinity. ...which means that if you wanted to list every possible row, you would need an uncountable infinity of rows. Even though you only have a countable infinity of rows in the beginning! So what this is saying is that if you force every cell to be filled with the same symbol, then the table is still countably infinite in size. As soon as you allow more than one symbol, then the table becomes uncountably infinite in size. Hope it helps in clearing this little issue we're having here. Cordially, moonlight. I agree with most of what you've said, but the point I'm making has to do with listing every possible row. Our argument started because you said that we can have a chart with the sides being countably infinite, the cells being occupied by 1s and 0s, and when we diagonalize the cells to produce another, unique string of 1s and 0s, we can add another Turing Machine to our list. You also said that we can always do this; that for every such row there is a machine. But that is equivalent to saying that there's a machine for every possible row, which is impossible.

moonlight
Lunatic

Usergroup: Members
Joined: Oct 09, 2005
Location: stuck on earth
Total Topics: 17
Total Posts: 535

Posted 03/30/08 - 12:20 AM:	#45
7 wrote: Our argument started because you said that we can have a chart with the sides being countably infinite, the cells being occupied by 1s and 0s, and when we diagonalize the cells to produce another, unique string of 1s and 0s, we can add another Turing Machine to our list. You also said that we can always do this; that for every such row there is a machine. Yes, all of this, I did say. And I add: they were assumptions. The table itself was an assumption. The contradiction leads to the dismissal of the assumption: there is no such table. It is a proof by contradiction. 7 wrote: But that is equivalent to saying that there's a machine for every possible row, which is impossible. Exactly. Thus contradiction. Thus the assumption is wrong: there is no table. Cordially, moonlight.
All are lunatics, but he who can analyze his delusion is called a philosopher. - Ambrose Bierce -

Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81

Posted 03/30/08 - 06:34 AM:	#46
Thank you for this clear explanation moonlight. It is true, we would have 2^aleph0 choices for the first row because there are two possibilities for each cells, etc...

7
Graduate

Usergroup: Members
Joined: Mar 23, 2008
Total Topics: 3
Total Posts: 160

Posted 03/30/08 - 10:27 AM:	#47
moonlight wrote: Yes, all of this, I did say. And I add: they were assumptions. The table itself was an assumption. The contradiction leads to the dismissal of the assumption: there is no such table. It is a proof by contradiction. Exactly. Thus contradiction. Thus the assumption is wrong: there is no table. Cordially, moonlight. Here is your argument as I understand it: 1) We have a chart with an enumeration of the TMs on one side and an enumeration of the inputs on the other. 2) We have a function f(x,y) which computes for all machines x whether or not they halt for all inputs y. If m halts on input n, f puts 1 in the m/n cell and if it does not, it puts 0 in that cell. 3) We can use a diagonal argument to create another row of 1s and 0s, and crucially, this corresponds to a unique TM that was not on the list. 4) Therefore, f does not compute the halting information for the new machine. My objection comes in at step 3. Let me explain how the case we are considering differs from Cantor's diagonal argument. In the Cantor argument, we know that the new string is relevant. It counts as a new row because the only requirement for a string to be added to the list is that it is an infinite string of 1s and 0s. On the other hand, in our case, there is a built-in assumption that the string is relevant. We are presuming that the string corresponds to a TM. Without that assumption, the proof does not work. I am questioning that assumption. It seems reasonable for me to question it because I know that there are more strings than machines, so I know that all of the strings cannot possibly correspond to a unique Turing machine.

moonlight
Lunatic

Usergroup: Members
Joined: Oct 09, 2005
Location: stuck on earth
Total Topics: 17
Total Posts: 535

Posted 03/30/08 - 07:25 PM:	#48
Hi 7, No, again you're laying down the argument wrong. So I will repeat again. Point 2) is a supposition. We don't have anything. We only suppose we do. Now if 2) is True, then we have a completed table. Point 3) contradicts this, therefore the supposition 2) must be false, which you have stated in point 4), well sort of: it's more like: f is uncomputable, full stop. That's how the argument is going really. 7 wrote: We are presuming that the string corresponds to a TM. Without that assumption, the proof does not work. I am questioning that assumption. It seems reasonable for me to question it because I know that there are more strings than machines, so I know that all of the strings cannot possibly correspond to a unique Turing machine. If 'f' could computed, then every string would correspond to a TM, and there would be a countable number of strings. Obviously you don't discuss that I guess. So in effect, you are arguying that the supposition that 'f is computable' is not valid. Obviously the assumption is false, as the proof shows, and you are right: the Halting Problem is uncomputable as everyone knows today. But how do you know that before doing the proof? This is the story of the chicken & the egg really. Suppose Turing was the first to come up with this type of proof, not Cantor. Could anyone have said: "no Alan, you are supposing that the strings correspond to TMs, but this isn't the case", before he finished presenting his proof? Obviously not: anyone would need to know first that the infinite strings are uncountable, before being able to go wise on Turing and tell him that his assumption is false. We know it is false precisely because of the proof (this type of diagonalization proof I mean). Moreover, you seem to set aside the fact that TMs are denoted by integers, not strings. A string denotes a combination, between one given TM, and an infinity of inputs. It doesn't just denote one TM. If you only allowed 100 inputs to exist, then you would not be having this problem. Clearly, this must show that the strings do not denote TMs, but combinations of TMs and strings instead. Without inputs, there is no point to even try and assign a string to a TM. So really again, your objection comes down to saying: "why is Turing assuming that the Halting Problem is solvable?", in other words: "Why is Turing assuming that the set of infinite strings can be countable, like TMs?". Well obviously, we know that's not true, but then again, the result is due to Alan Turing, and his proof by contradiction of the assumption, is it not? Cordially, moonlight.
All are lunatics, but he who can analyze his delusion is called a philosopher. - Ambrose Bierce -

7
Graduate

Usergroup: Members
Joined: Mar 23, 2008
Total Topics: 3
Total Posts: 160

Posted 03/31/08 - 03:29 PM:	#49
Hi 7, No, again you're laying down the argument wrong. So I will repeat again. Point 2) is a supposition. We don't have anything. We only suppose we do. Now if 2) is True, then we have a completed table. Point 3) contradicts this, therefore the supposition 2) must be false, which you have stated in point 4), well sort of: it's more like: f is uncomputable, full stop. That's how the argument is going really. I understand that it is a supposition and there is no such function as f. The point I am making is that the proof only contradicts the supposition that there is such a function because we take it for granted that we can keep on adding to the list ad infinitum, for every binary string. The cardinality of the strings is R, the cardinality of the TMs is N. If I could pair a TM with every possible string, then I would have a bijection f: N -> R, which is, of course, not possible. If 'f' could computed, then every string would correspond to a TM, and there would be a countable number of strings. Obviously you don't discuss that I guess. So in effect, you are arguying that the supposition that 'f is computable' is not valid. I will discuss it. If f could be computed, then it would not follow that every string would correspond to a TM. That only follows on the assumption that you can create a TM for every possible string. It is coherent to suppose: 1) f is computable and 2) there exist strings that do not correspond to any machines. Obviously the assumption is false, as the proof shows, and you are right: the Halting Problem is uncomputable as everyone knows today. But how do you know that before doing the proof? Let f(x,y) be a two-place function that computes for any machine x (x is its number in the enumeration of TMs) and any input y whether or not x halts for y. We're assuming that f is a recursively computable function, so there is some TM that computes it. Call this TM H. If a machine halts for an input, H outputs 1 and if it does not, H outputs 0. Consider a machine C, which is a composite of H and a looping machine L. L takes as input the output of H. If H outputs 1, L loops infinitely and if H outputs 0, then L halts immediately. Try to compute using H whether or not C halts with c (its own number) as input. Keep in mind that H is a part of C. When C takes c as input, first it feeds c into H, then the output goes to L. Say that H tells us that f(c,c) = 1. Well, then the H part of C outputs 1, and L loops infinitely. So, if H computes that f(c,c) halts, then C doesn't halt. Now do the other case: H tells us that f(c,c,) = 0. Then the H part of the composite outputs 0 and feeds 0 to L which halts immediately. If H computes that f(c,c) doesn't halt, then it halts. Since there is a contradiction either way, the machine H cannot exist. There is no function f that that can compute for all machines whether or not they halt for each input. Hence, I consider the halting problem a closed issue. I believe that the original proof bears a resemblance to the one I have just presented, although mine is somewhat streamlined. This is the story of the chicken & the egg really. Suppose Turing was the first to come up with this type of proof, not Cantor. Could anyone have said: "no Alan, you are supposing that the strings correspond to TMs, but this isn't the case", before he finished presenting his proof? Obviously not: anyone would need to know first that the infinite strings are uncountable, before being able to go wise on Turing and tell him that his assumption is false. We know it is false precisely because of the proof (this type of diagonalization proof I mean). Here is what someone could have said: "You're proving that there can be no computable function that enumerates all infinite binary strings, but in order to prove that there is no computable function that decides the halting problem, you can't assume that all of those infinite binary strings are relevant to Turing machines. That is, you can't take it for granted that you have a TM for every possible string." I don't think this proof is actually Turing's, though, but that's beside the point. Moreover, you seem to set aside the fact that TMs are denoted by integers, not strings. A string denotes a combination, between one given TM, and an infinity of inputs. It doesn't just denote one TM. If you only allowed 100 inputs to exist, then you would not be having this problem. Clearly, this must show that the strings do not denote TMs, but combinations of TMs and strings instead. Without inputs, there is no point to even try and assign a string to a TM. So really again, your objection comes down to saying: "why is Turing assuming that the Halting Problem is solvable?", in other words: "Why is Turing assuming that the set of infinite strings can be countable, like TMs?". Well obviously, we know that's not true, but then again, the result is due to Alan Turing, and his proof by contradiction of the assumption, is it not? I'm not pretending that TMs are enumerated by the strings. They are enumerated by the natural numbers. However, by the construction of the proof, there is a TM for every string. That is all I really need for this objection. Finally, as you believe that I've mischaracterized your argument, so I think that you've misstated by point. I'm not asking why the argument assumes the Halting problem is solvable. My own proof given above assumes that it is solvable and derives a contradiction; I am familiar with this type of demonstration. What I'm asking is why does your argument assume that you can add a Turing machine to the left column for every infinite string that you can formulate using diagonalization? Why doesn't your argument consider the possibility that some are throwaways? How does your argument explain the coherency of its assumption that you can add a new TM to the left column for every possible unique row of binary digits with the fact that the set of strings is larger, so there have to be throwaways?

moonlight
Lunatic

Usergroup: Members
Joined: Oct 09, 2005
Location: stuck on earth
Total Topics: 17
Total Posts: 535

Posted 04/01/08 - 01:19 AM:	#50
Hi 7, 7 wrote: ...but in order to prove that there is no computable function that decides the halting problem, you can't assume that all of those infinite binary strings are relevant to Turing machines. That is, you can't take it for granted that you have a TM for every possible string."..." I don't see why not. You make an assumption that it is true, and then you prove it to be wrong. 'f' after all is talking about binary strings, i.e. the combination of machines and input, not just machines on their own. Anyway, it looks like our positions on this issue seem to be irreconciliable for the time being. I'll give it some more thought as time permits, discuss with some friends, and post back if there's any change in my understanding of the problem. Cordially, moonlight.
All are lunatics, but he who can analyze his delusion is called a philosopher. - Ambrose Bierce -

Page: 1 2

You don't have permission to post.

Please login or register.