Articles

图灵谁如何定义“可计算性”的？

  I. How did Turing define the computability? Turing's 1936 paper, as its title suggests:  On Computable Numbers, with an Application to the Entscheidungsproblem , aimed to solve the  Entscheidungsproblem  proposed by Hilbert based on c omputable numbers .   Turing answered the Entscheidungsproblem negatively, Turing said: I propose, therefore, to show that there can be no general process for determining whether a given formula A of the functional calculus K is provable (Note: K refers to the first-order predicate), i.e. that there can be no machine which, supplied with any one A of these formulae, will eventually say whether A is provable. Therefore, Turing gave a definition of  decision problem  such that «  there is a general process for determining . . . ».   1. Decision problem     Turing said ([ 1], Section 8) : The expression ''there is a general process for determining . . .'' has been used throughout this section ...
Enregistrer un commentaire
Lire la suite

停机问题（3）- 证明溯源

  There are two versions of the popular proof of the "haling problem": one based on the liar's paradox and the other based on the Cantor’s diagonisation. The academic claims that the halting problem and its proofs are originated from Turing's 1936 paper, which is highly questionable, … Roger Penrose gave an accessible presentation of the proof of the halting problem based on the Cantor’s diagonisation in  The Emperor's New Mind , and I excerpt the relevant content as follows (p.59-64) : A natural question arises: how are we to decide whether or not any particular Turing machine (when fed with some specific input) will ever stop?  … So, is there some algorithmic procedure for answering the general question - the halting problem - completely automatically?  Turing showed that indeed there is not. His argument was essentially the following.  We first suppose that, on the contrary, there is such an algorithm. Then there must be some Turing machine H which 'decides...
Enregistrer un commentaire
Lire la suite