> On 1 Nov 2018, at 19:43, John Clark <johnkcl...@gmail.com> wrote:
> 
> 
> On Thu, Nov 1, 2018 at 2:27 PM Philip Thrift <cloudver...@gmail.com 
> <mailto:cloudver...@gmail.com>> 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








> John K Clark
> 
> 
> 
>  
> 
> -- 
> 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 everything-list+unsubscr...@googlegroups.com 
> <mailto:everything-list+unsubscr...@googlegroups.com>.
> To post to this group, send email to everything-list@googlegroups.com 
> <mailto:everything-list@googlegroups.com>.
> Visit this group at https://groups.google.com/group/everything-list 
> <https://groups.google.com/group/everything-list>.
> For more options, visit https://groups.google.com/d/optout 
> <https://groups.google.com/d/optout>.
> 
> -- 
> 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 everything-list+unsubscr...@googlegroups.com 
> <mailto:everything-list+unsubscr...@googlegroups.com>.
> To post to this group, send email to everything-list@googlegroups.com 
> <mailto:everything-list@googlegroups.com>.
> Visit this group at https://groups.google.com/group/everything-list 
> <https://groups.google.com/group/everything-list>.
> For more options, visit https://groups.google.com/d/optout 
> <https://groups.google.com/d/optout>.

-- 
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 everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.

Reply via email to