To prove the existence of incomputable entities, Turing introduces a set C that contains *all* computable series of 0s and 1s; he then shows how a new series can be constructed from the elements of C, which *differs* from every element in C. It is assumed that C contains all computable series of 0s and 1s; therefore, the new series is (by definition) *not* computable. But this sounds to me as a contradictory discourse, because the "incomputable" series was actually *computed* (from C), so that it is strange to call it incomputable.
In brief, the "incomputable" series was computed in the following way. Let us assume that the computable series in C are ordered in a form of matrix, one series of 0s and 1s below the other. Now, let us move along the diagonal of this matrix, from the upper left corner downwards and produce a new series in the following way. If the first (top) series has "1" at the first position, we put "0" at the first position of our new series; if the first series has "0" at the first position, we put "1" at the first position of our new series. We perform the same process with the second position of the second series, with the third position of the third series, and so infinitely on.
The series we produced in this way differs from each series contained in the set C at least at one position: it differs from the first series at the first position; from the second series at the second position; from the third series at the third position; and so infinitely on. The set C contains *all* computable series of 0s and 1s (by definition); therefore, the new series we produced in the described way is *not* one of the computable ones (which are all in C). And yet, this series is obviously *computed* in a very simple and precise way we described above.
It has been assumed that the above procedure demonstrates (proves) the existence of non-computable entities. Contrary to this, I hold that the above procedure shows that the assumption that there exists the "set of all computable series of 0s and 1s" leads to contradiction. This means that *this concept is inconsistent* and hence meaning-less, and that such set cannot exist.
It is difficult to assume that the brilliant Turing was wrong; but I do not see anything wrong in my interpretation (given above) of his discourse either, on the basis of which I must hold his discourse wrong.
Since nobody told me (why) I am wrong, the best I can do is to assume that I am not wrong. This is a sort of "pragmatic logic".
The problem is in that some (even though they are countable) sets can't be computably printed, that is, there is no Turing Machine that will produce a list of elements of this set. What the diagonalization argument shows is that the set of computable sequences can't be computed. Turing didn't show that the set of computable sequences is contradictory; rather that the set of computable sequences is not computable. The construction of uncomputable sequence crucially depends on this aspect: it requires knowledge of nth bit of nth element of the list. To know this, an ordering is required, which in turn requires an algorithm to output all computable sequences - and this algorithm is what Turing showed is contradictory, not the set of computable sequences.
This may solve the problem (misunderstanding).
My understanding was that Turing *assumed* that there exists a set of all computable series, and he then *computed* a new series which is not in that set. Such computation would contradict the assumption. (That is what I say.)
On the other hand, if Turing wanted to show that the *set* of all computable series *cannot be computed*, then Turing's argument seems ok. Namely, from the assumption that such a set exists, it is possible to compute a new series which is not in that set. Therefore, such a set can never be computed.
I hope this may solves the problems. But I am not sure because I did not read the original Turing's argument (if it exists), but a presentation of this story, given by others.
Anyway, the problem is not (or should not be) whether something can be computed in reality, but only whether it could be done in principle.
Yes, he only showed that C can't be computed (it must exist as a set if set theory is sound, by using the axiom of comprehension from set theory together with the existence of the set of natural numbers).
I don't know what Turing's original proof (of unsolvability of halting problem) looked like, but I know he used the same general idea that you presented. It can be shown that C can be computed (printed by dovetailing) if function check-if-halts(program_description) was computable. It would suffice to list all valid Turing Machines and call the check-if-halts function (and use dovetailing for printing).
By the way, the existence of noncomputable infinite binary sequences follows from even much simpler arguments. There are "more" (in Cantor's sense, uncountable) infinite binary sequences than there are natural numbers (which is a countable set). And there are exactly as many Turing Machines as there are natural numbers. Thus in a certain strong sense, almost all sequences can't be computed (more precisely: a randomly selected infinite binary sequence is noncomputable with probability 1).
Turing's (and Church's) arguments show more, that we in general can't know whether even a finitely described TM will halt (or, in the language of sequences, not-produce an infinite sequence). Of course, their arguments don't hold if their formalisms don't capture the whole space of computable functions (Church-Turing thesis), although (as I think you already know) there are very good arguments that their formalism perfectly capture our intuitions on computability.
I assume that my original question has been answered. The problem was that I did not understand (interpret) the argument properly.
I encountered this argument when I was writing about mind & machines. In that context, I tried to understand the Church-Turing thesis, and (even more) what consequences this thesis actually has on the relationship between human cognitive abilities and computation. At that time, I encountered the argument about (in)computability from my question. My critical note about this argument remained in my "working notes", and so it ended on the RG.
I will return to the Church-Turing thesis (I hope), but at this moment I am very busy with a text about time. For the last time, I hope! Because time is an endless story, even worse than mind & machines is.
- Badges
- Science topic
- Similar topics
- Computer Science
- Computing