On Friday, November 2, 2018 at 3:45:53 AM UTC-5, Bruno Marchal wrote: > > > On 1 Nov 2018, at 19:43, John Clark <[email protected] <javascript:>> > wrote: > > > On Thu, Nov 1, 2018 at 2:27 PM Philip Thrift <[email protected] > <javascript:>> wrote: > > *> infinite time Turing machines are more powerful than ordinary Turing >> machines* > > > That is true, it is also true that if dragons existed they would be > dangerous and if I had some cream I could have strawberries and cream, if I > had some strawberries. > > *> How "real" you think this is depends on whether you are a Platonist or >> a fictionalist.* >> > > No, it depends on if you think logical contradictions can exist, if they > can then there is no point in reading any mathematical proof and logic is > no longer a useful tool for anything. > > > > No Turing machine can solve the halting problem. You are right on this. > But an oracle can, or a machine with infinite speed can. > > Now, such machine have only be introduced (by Turing) to show that even > such “Turing machine with magical power making them able to solve the > halting problem” are still limited and cannot solve, for example the > totality problem (also an arithmetical). > > Turing showed that there is a hierarchy of problem in arithmetic, where > adding magic (his “oracle”) never make any machine complete. It is a way to > show how complex the arithmetical reality is. Adding more and more magical > power does not lead to completeness. > > Post and Kleene have related such hierarchies with the number of > alternating quantifiers used in the arithmetical expression. P is a sigma_0 > = pi_0 formula, without quantifier. > > ExP(x, y). Sigma_1 (negation = AxP(x,y) = Pi_1, more complex than sigma_1, > already not computable). > ExAyP(x, y, z) = Sigma_2 (beyond today’s math!) (negation = Pi_2). > Etc. > > More and more “infinite task” are needed. > > Note that such magic does not change the “theology”. It remains the same > variants of the Gödel-Löb-Solovay self-reference logics (G and G*). > > Bruno > > > > There are other "Turing machine" models other than infinite-time ones people have "invented", e.g.* inductive* Turing machines:
*Algorithmic complexity as a criterion of unsolvability* https://pdfs.semanticscholar.org/cd8f/442a9f7667891fff6f276a1bc638dd59b937.pdf : Let us take an *inductive Turing machine M *that given a description of the Turing machine T and first n + 1 words x0, x1, . . . , xn from the list x0, x1, . . . , xn, . . ., produces the (n + 1)th partial output. This output is equal to 1 when the machine T halts for all words x0, x1, . . . , xn given as its input, and is equal to 0 when the machine T does not halt for, at least, one of these words. In such a way, *the machine M solves the totality problem for Turing machines*. ? cf. https://en.wikipedia.org/wiki/Super-recursive_algorithm#Inductive_Turing_machines https://bitrumagora.wordpress.com/about/marl-burgin/ *Nothing is settled in computing.* - pt -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
