On Monday, November 5, 2018 at 3:36:59 AM UTC-6, Bruno Marchal wrote:
>
>
> On 2 Nov 2018, at 15:02, Philip Thrift <[email protected] <javascript:>>
> wrote:
>
>
>
> 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]> wrote:
>>
>>
>> On Thu, Nov 1, 2018 at 2:27 PM Philip Thrift <[email protected]> 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.*
>
>
>
> But this does not clearly violate Church-Thesis. Inference inductive is
> not the same as computing. We know that there are many different Turing
> machine, which are not equivalent for proving or inducting, etc. All humans
> are like that. We are still the same *as* Turing machine (combinators,
> etc.). Universality is with respect to computing, and is false with
> everything else. Now, if you add magical, or actual infinities, or oracles,
> or infinite speed, then you get machine which are no more digital finite
> machine, and so cannot violate the Church-Turing thesis either.
>
> Bruno
>
>
>
>From all the super-Turing math and CS news (I've followed over the years),
there seems to be a consensus forming:
*There are no super-Turing computers!* (that can be found in nature or
manufactured by us)
cf.
https://phys.org/news/2015-09-limit-church-turing-thesis-accounts-noisy.html
The only ones are *fictional* ones (the infinite-time and super-recursive
ones above).
So that seems to be the consensus.
But I claim an experience-processing computer (like our brain) is not
super-Turing, but is non-Turing: All *information* it can process is
Turing-computable, but it also processes *experience*.
- 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.
