Re: A Church-Turing-Thesis for Infinitary Computations

[Bruno Marchal]

> On 26 Mar 2020, at 10:23, Philip Thrift  wrote:
> 
> 
> 
> On Thursday, March 26, 2020 at 4:02:18 AM UTC-5, Philip Thrift wrote:
> 
> 
> On Wednesday, March 25, 2020 at 4:57:41 AM UTC-5, Bruno Marchal wrote:
> 
> 
> With Mechanism, a priori, nature does not compute at all, but emerge from a 
> non computable sum on all computations (in the relative way). This must be 
> “observable” when we look below our substitution level. That this sum can be 
> Turing universal can be explained, but is still astonishing.
> 
> 
> Bruno
> 
> 
> Mathematical logicians like Hamkins have gone beyond Gödel and Cohen: There 
> is a "multiverse" of mathematical "truths"  - in effect, there are machines 
> at different computing levels ("Turing jumps") that return different results 
> (different answers to questions).
> 
> What nature does relative to this mathematics - who knows.
> 
> (If nature is finite - composed of a finite number of "states" - then it 
> would obviously be computable -since then nature could be modeled - at least 
> stochastically -  by a finite collection of lookup probability tables.)
> 
> @philipthrift
> 
> 
> 
> In religious terms:
> 
> There once was a Platonic Eden of numbers and pure mathematics where we once 
> lived as numerical-spiritual beings.


Nice!

I parody often de Chardin on this, by saying that we are not, in your term, 
human being dreaming about numerical-spiritual beings, but we are 
numerical-spiritual being dreaming about humans beings.



> 
> But God cursed us

That is “the fall”. That happens when we communicate, without precautions, like 
interrogation marks, something belonging to G* \ G, through some intensional 
variants or not. Eventually this is the base of a theory of pain/pleasure. It 
is a sub theory of the theory of qualia. 





> and evicted us from that world to exist in a world of matter.

With Mechanism, it is more God itself who becomes sleepy, and forgets who 
he/she/it is or was, and becomes unable to recognise itself in the others. He 
lost itself in the garden brought by his Mother! (If we want a semi-fairy tale 
type of description). 




> 
> That is the only world we can deal with.

Yes. At first it is the entire arithmetical truth (God’s Mother), then it is 
the same intensionally, (p) together with the brain-filter ([]p).



> Anything else is just a lost dream.


Some sharable dreams can be very long, and very stable. I would not dismiss 
them as unreal, because then physics would be unreal, and that is pretty absurd.

Bruno



> 
> @philipthrift
> 
> -- 
> 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 view this discussion on the web visit 
> https://groups.google.com/d/msgid/everything-list/0a0c23b3-df12-4724-ab97-9f1c0f5ae87f%40googlegroups.com
>  
> .

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/C4B9208F-E6D3-4934-984A-35A36A9679A9%40ulb.ac.be.

Re: A Church-Turing-Thesis for Infinitary Computations

[Bruno Marchal]

> On 26 Mar 2020, at 10:02, Philip Thrift  wrote:
> 
> 
> 
> On Wednesday, March 25, 2020 at 4:57:41 AM UTC-5, Bruno Marchal wrote:
> 
> 
> With Mechanism, a priori, nature does not compute at all, but emerge from a 
> non computable sum on all computations (in the relative way). This must be 
> “observable” when we look below our substitution level. That this sum can be 
> Turing universal can be explained, but is still astonishing.
> 
> 
> Bruno
> 
> 
> Mathematical logicians like Hamkins have gone beyond Gödel and Cohen:


Hamkins propose a theory which does not seem to fit with Mechanism. It is OK, 
but *very* speculative. He seems also not to address the mind-body problem. It 
is nice mathematics, but rather out of the scope of my working hypothesis. His 
work might have application in some foreseeable future, but as such, it has no 
direct implications that I can see right now.



> There is a "multiverse" of mathematical "truths"  - in effect, there are 
> machines at different computing levels ("Turing jumps”) that return different 
> results (different answers to questions).

The theology of the machine is invariant for those jump. I have explained how 
to add a type of Turing quadruplet to the the Turing machine to handle them. 
That plays some role for the first person, because its indeterminacy relies on 
the sigma_1 + oracle geometry/topology (and the phenomenological measure is 
handled by descriptive set theory, but that is new, not in my published 
papers). 
It is not really “hyper-computation”: it is relative computation, and the 
theology remains the same, unless a particular oracle is in play (but without 
evidence that is free speculation).






> 
> What nature does relative to this mathematics - who knows.

I am not sure you have studied the argument I have given: but the appearance of 
nature belongs to the phenomenology of the machine/number. The material reality 
is better explained by the number dreams, than by “the number’s dream + a 
physical reality”. It is up to the materialist to explain how matter brings the 
mind, without using the Mechanist explanation, and up to now, no such theory 
exist, where mechanism not only explain consciousness, but it explains the 
relation between consciousness and the physical appearances, why they last, 
etc. The explanation is constructive, and the inference of the 
many-superposed-histories and their quantum logic structure is already 
explained and somehow a posteriori confirmed. 



> 
> (If nature is finite - composed of a finite number of "states" - then it 
> would obviously be computable -since then nature could be modeled - at least 
> stochastically -  by a finite collection of lookup probability tables.)


Yes, that is why nature has to have an infinite component.  Nature (actually 
its appearance)  is only the boundary of the universal machine “arithmetical" 
ignorance, as seen "from inside” (where the “inside” notion is obtained from 
the Kleene’s usual notion of self-reference mixed with Tarski conception of 
truth (in the manner already explained informally in Plato’s Theaetetus).

Nature is infinite, but the infinite is something phenomenological, not 
ontological. Mechanism is a finitisme. That is already well explained by Judson 
Webb’s book, that I have often referred to. 

There is no axiom of infinity in the ontology, indeed, there are no induction 
axioms either. 

As long as we don’t find a discrepancy between the physics in the head of all 
universal number and what we inferred from observation, adding something to the 
ontology on

Kxy =x
Sxyz = xz(yz)

seems to me rather premature. (Except the few inference rules, and the axiom S 
≠ K to avoid the trivial model, but even that axioms might still be eventually 
purely phenomenological (Open Individulism might be true).

Bruno



> 
> @philipthrift
> 
> 
> 
> 
> -- 
> 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 view this discussion on the web visit 
> https://groups.google.com/d/msgid/everything-list/8832a5c1-a605-43ed-8dcb-4673d64e8908%40googlegroups.com
>  
> .

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/EF0AE772-090C-483F-AAF2-457C43591EA0%40ulb.ac.be.

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

On Thursday, March 26, 2020 at 4:02:18 AM UTC-5, Philip Thrift wrote:
>
>
>
> On Wednesday, March 25, 2020 at 4:57:41 AM UTC-5, Bruno Marchal wrote:
>>
>>
>>
>> With Mechanism, a priori, nature does not compute at all, but emerge from 
>> a non computable sum on all computations (in the relative way). This must 
>> be “observable” when we look below our substitution level. That this sum 
>> can be Turing universal can be explained, but is still astonishing.
>>
>>
>> Bruno
>>
>>
>> Mathematical logicians like Hamkins have gone beyond Gödel and Cohen: 
> There is a "multiverse" of mathematical "truths"  - in effect, there are 
> machines at different computing levels ("Turing jumps") that return 
> *different 
> results* (different answers to questions).
>
> What nature does relative to this mathematics - who knows.
>
> (If nature is finite - composed of a finite number of "states" - then it 
> would obviously be computable -since then nature could be modeled - at 
> least stochastically -  by a finite collection of lookup probability 
> tables.)
>
> @philipthrift
>
>
>
In religious terms:

There once was a Platonic Eden of numbers and pure mathematics where we 
once lived as numerical-spiritual beings.

But God cursed us and evicted us from that world to exist in a world of 
matter.

That is the only world we can deal with. Anything else is just a lost dream.

@philipthrift

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/0a0c23b3-df12-4724-ab97-9f1c0f5ae87f%40googlegroups.com.

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

On Wednesday, March 25, 2020 at 4:57:41 AM UTC-5, Bruno Marchal wrote:
>
>
>
> With Mechanism, a priori, nature does not compute at all, but emerge from 
> a non computable sum on all computations (in the relative way). This must 
> be “observable” when we look below our substitution level. That this sum 
> can be Turing universal can be explained, but is still astonishing.
>
>
> Bruno
>
>
> Mathematical logicians like Hamkins have gone beyond Gödel and Cohen: 
There is a "multiverse" of mathematical "truths"  - in effect, there are 
machines at different computing levels ("Turing jumps") that return *different 
results* (different answers to questions).

What nature does relative to this mathematics - who knows.

(If nature is finite - composed of a finite number of "states" - then it 
would obviously be computable -since then nature could be modeled - at 
least stochastically -  by a finite collection of lookup probability 
tables.)

@philipthrift



-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/8832a5c1-a605-43ed-8dcb-4673d64e8908%40googlegroups.com.

Re: A Church-Turing-Thesis for Infinitary Computations

[Bruno Marchal]

> On 21 Mar 2020, at 23:57, 'Brent Meeker' via Everything List 
>  wrote:
> 
> 
> 
> On 3/21/2020 9:52 AM, Bruno Marchal wrote:
>> 
>> With mechanism, we have to get rid of the infinite for the ontological 
>> assumption, although a potential infinite remains necessary at the 
>> semantical level.
>> 
>> We believe only in finite things, like 0, s0, ss0, sss0, 0, ..;, but we 
>> know that in the intended model, thy are all there,
> 
> Who says that's the "intended model”. 

Everybody in the field, by definition.




> That's your leap of faith, or mysticism.


I like this. It makes the whole higher order logic into mysticism. But it not 
my faith, but the faith of all sicentists.

This makes mysticism the base of mathematics, which is an idea sympatic to a 
(Neo)Pythagorean. Now, our faith is arithmetic is basically instinctive, and 
very few people are aware that their belief in 2+2=4 has a mystical root. So I 
don’t insist too much on this. (To be sure, the belief in a physical reality 
“out there” is as much mystical).

Bruno




> 
> Brent
> 
>> but, like In Plotinus in its “Number” chapter, the number of numbers is not 
>> a number, and all object in the terrestrial plane are finite. Same for the 
>> combinatory algebra. They possess K, S, KK, KS, …, but unless K = S, they is 
>> an infinity of combinators/programs.
> 
> 
> -- 
> 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 view this discussion on the web visit 
> https://groups.google.com/d/msgid/everything-list/ef90c13e-2115-529d-12dd-15c5055fa404%40verizon.net.

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/8A464C31-F2BF-4C57-A31A-34EBF7A46C13%40ulb.ac.be.

Re: A Church-Turing-Thesis for Infinitary Computations

[Bruno Marchal]

> On 21 Mar 2020, at 17:04, Philip Thrift  wrote:
> 
> 
> 
> The paper brought up by someone on
> http://backreaction.blogspot.com/2020/03/unpredictability-undecidability-and.html
>  
> 
> 
> 
> Computability and Physical Theories
> Robert Geroch, James B. Hartle
> arXiv:1806.09237
> 
> "We suggest that [a theory having measurable numbers that are not computable] 
> should be no more unsettling to physics than has the existence of well-posed 
> problems unsolvable by any algorithm been to mathematics."
> 
> says they (and apparently many physicists) already think nature hypercomputes.

With Mechanism, a priori, nature does not compute at all, but emerge from a non 
computable sum on all computations (in the relative way). This must be 
“observable” when we look below our substitution level. That this sum can be 
Turing universal can be explained, but is still astonishing.



>  
> Maybe it does, but again physicists confuse nature and mathematics.

Some does. Of course(?)  that is just logically impossible when we assume 
Digital Mechanism. Nature becomes the first person sharable (plural) reality. 
It is not a human construct, but a universal machine construct (in arithmetic).

Bruno




> 
> @philipthrift
> 
> 
> On Saturday, March 21, 2020 at 9:09:46 AM UTC-5, Lawrence Crowell wrote:
> Todd Brun found [ https://arxiv.org/pdf/gr-qc/0209061v1.pdf 
>  ] that P = NP is true for closed 
> timelike curves. This is a short, readable and decent paper. The extension to 
> all PSPACE and undecidable propositions is of course difficult to prove 
> explicitly. However, a spacetime that permits CTCs will present Cauchy 
> horizons, and in principle an observer can in a finite time verify whether a 
> Turing machine halts or does not halt, even if the proper time of that TM is 
> infinite. This is of course an in principle argument. 
> 
> It is potentially interesting in the context of P = NP vs P ≠ NP whether this 
> result really does mean this is undecidable proposition. P = NP appears true 
> in a spacetime with CTCs, such as AdS or wormholes and so forth. We have no 
> knowledge whether P = NP can hold in our more normal dS-like spacetime with 
> positive vacuum energy.
> 
> Aaronson and Watrous found [ https://arxiv.org/pdf/0808.2669.pdf 
>  ] that classical systems on closed 
> timelike curves can perform some BQP algorithms quantum computers execute. 
> This emboldens my hypothesis that quantum physics and spacetime physics are 
> categorically equivalent, or that spacetime is an epiphenomenon of large 
> N-entanglements. On the top of page 5 of this paper is an interesting 
> diagram. This illustrates a register or memory system with two parts, one 
> part for a spacetime such as what we observe with open timelike curves and 
> another with part with closed timelike curves. Aaronson and Watrous argue the 
> Deutsche self-consistency condition on CTCs should hold and that a quantum 
> wave corresponding to the causality respecting must also constructively 
> interfere with the CTC wave function. The argument then is it is possible to 
> emulate all PSPACE this way.
> 
> Spacetimes such as Gödel’s universe, the global metric on AdS or the timelike 
> interior of a Kerr black hole have CTCs. BTW, it appears that Gödel had some 
> mental obsession with closed loopy systems! The question might be raised, 
> what is the separation or distinction between causal respecting CR and closed 
> timelike curve CTC spaces? The diagram on the AW paper suggests there is some 
> quantum wave interference between a wave function associated with the CR and 
> CTC spacetimes. The de Sitter and anti-de Sitter spaces respectively fit as a 
> single sheet hyperboloid surrounding a light cone and two hyperboloids 
> bounded within the conical openings. These meet at I^{±∞}, which means they 
> share the same quantum information as defined by the AdS/CFT correspondence 
> of Maldacena et al. . In the setting of holography we have something similar, 
> and there are arguments of AdS black hole correspondence as well. 
> 
> This according to A. Almheiri1, R. Mahajan, J. Maldacena, and Y. Zhao (AMMZ) 
> [ arXiv:1908.10996v1  [hep-th] ] also has some correspondence with the 
> interior state of a black hole. This paper is rather qualitative and 
> speculative. The idea is the interior of a black hole has “islands” of states 
> defined by a dimension difference of one. We might compare this to how the 
> Reisner-Nordstrom metric, and by extension the Kerr metric, has a near 
> horizon condition for an accelerated observer equivalent to AdS_2×S^2. The 
> AdS globally has CTCs, and locally we consider conformal patches that 
> restrict away from CTCs and respects CR. What I am working on now is to 
> illustrate how the AMMZ islands correspond to local AdS regions or conformal 
> 

Re: A Church-Turing-Thesis for Infinitary Computations

['Brent Meeker' via Everything List]

On 3/21/2020 9:52 AM, Bruno Marchal wrote:


With mechanism, we have to get rid of the infinite for the ontological 
assumption, although a potential infinite remains necessary at the 
semantical level.


We believe only in finite things, like 0, s0, ss0, sss0, 0, ..;, 
but we know that in the intended model, thy are all there,


Who says that's the "intended model".  That's your leap of faith, or 
mysticism.


Brent

but, like In Plotinus in its “Number” chapter, the number of numbers 
is not a number, and all object in the terrestrial plane are finite. 
Same for the combinatory algebra. They possess K, S, KK, KS, …, but 
unless K = S, they is an infinity of combinators/programs.



--
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/ef90c13e-2115-529d-12dd-15c5055fa404%40verizon.net.

Re: A Church-Turing-Thesis for Infinitary Computations

['Brent Meeker' via Everything List]

On 3/21/2020 2:35 AM, Philip Thrift wrote:



Gregory Chaitin's /The Limits of Reason/

http://www.cs.virginia.edu/~robins/The_Limits_of_Reason_Chaitin_2006.pdf

shows math as a jungle only small, isolated pockets of which are ever 
explored.


That humans may feel that they need :proofs" maybe on a few pages 
long  is merely an unfounded bias. Maybe the "interesting" and 
"important" things to be proved require 100,000 pages or 1,000,000 
pages to print out.


Or even the unimportant ones, like the four-color theorem.



Or maybe the desire for proofs themselves is just are a human failing.


People who don't know mathematics and physics think they are about 
certainty.  But as Matt Carmill quipped, "As an adolescent I aspired to 
lasting fame, I craved factual certainty, and I thirsted for a 
meaningful vision of human life-- so I became a scientist.  This is like 
becoming an archbishop so you can meet girls."


Brent

--
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/1202694a-cb7f-1968-bd72-9bcec7af36a6%40verizon.net.

Re: A Church-Turing-Thesis for Infinitary Computations

[Bruno Marchal]

> On 20 Mar 2020, at 20:10, Lawrence Crowell  
> wrote:
> 
> On Thursday, March 19, 2020 at 11:48:00 PM UTC-5, Philip Thrift wrote:
> 
> 
> On Thursday, March 19, 2020 at 7:13:10 PM UTC-5, Lawrence Crowell wrote:
> 
> 
> On Thursday, March 19, 2020 at 9:54:58 AM UTC-5, Bruno Marchal wrote:
> 
>> On 18 Mar 2020, at 14:42, Lawrence Crowell > 
>> wrote:
>> 
>> On Wednesday, March 18, 2020 at 4:13:36 AM UTC-5, Bruno Marchal wrote:
>> 
>>> On 17 Mar 2020, at 16:14, Lawrence Crowell > 
>>> wrote:
>>> 
>>> I pretty seriously doubt these things will enter into physics. Computations 
>>> with Cantor's aleph hierarchy of transfinite numbers seems pretty far 
>>> removed from anything really physical.
>> 
>> 
>> OK. It is just abstract recursion theory, has been with Turing, and it 
>> concerns divine creatures, and the goal is to show that even those “divine” 
>> (infinite being) cannot effectively recover the arithmetical truth/reality. 
>> I doubt too that such machine can be brought to Earth, and they do play some 
>> role in the internal phenomenology of the “terrestrial machine”, a bit like 
>> infinite sums can play a role in physics, like the zeta renormalisation in 
>> superstring theory.
>> Note that most of those divine (infinite) machine are still obeying to the 
>> same self-reference logics (G and G*), and would not change much in the 
>> mathematical derivation of physics from arithmetic. Note also that the first 
>> person indeterminacy is connected to the machine + random oracle, so that 
>> the “sigma_1” predicate is really sigma_1 in all oracles, and this makes it 
>> possible to use some strong set axiom (like “projective determinacy”) to 
>> assure the existence of the measure, and probably of the needed 
>> generalisation of Feynman integral in arithmetic. (This needs indeed a 
>> generalisation of the Church’s thesis, called the hyperarihmetical church’s 
>> thesis in the classical  textbook by Rogers).
>> 
>> Bruno
>> 
>> 
>> 
>> When we get into subtleties of ZF set theory we get into the application of 
>> axioms, eg the axiom of replacement, axiom of infinity, axiom of choice etc, 
>> that have a limited bearing on most standard mathematics.
> 
> 
> I am not sure why you say this. Most mathematician would say that ZF is just 
> the usual intuition of sets made precise. Most people understand the need 
> (and the power) of the infinity axiom, so that we can talk about infinite set 
> like N, Q, R, C etc., and the functions in between those sets of numbers, 
> matrices, etc. The axiom of choice is just obvious, and the fact that it 
> cannot be proved is no more astonishing than the fact that we cannot prove 
> any axiom of Robinson Arithmetic from any of its other axioms.
> 
> 
> 
> In the field of physics mathematics is regarded as a tool or language. I 
> think that Feynman put it best with his talk about Greek mathematics vs 
> Babylonian mathematics. Greek mathematics with its precise ε - δ 
> theorem-proof system is "hard" in that you know within any system its results 
> are absolute. However, the Babylonians tended to do practical math, what 
> sometimes is called "maths," which has a certain quick utility to it. I tend 
> to have a foot in both camps, though I have to admit more weight is placed on 
> the Babylonian side. For this reason few physicists give much consideration 
> of ZF axiomatic models. I have to admit I generally give these things much 
> consideration.
> 
> LC
>  
> 
> 
> I guess I am not sure why you say there is actual damage done. It see the two 
> approaches as worthy in their own right.

Totally OK.



> What might be called Greek mathematics has lead us into a field where proofs 
> of the great unknown problems are huge affairs with hundreds of pages. Wiles' 
> result with the Fermat Theorem is 200 some pages of detailed work with 
> algebraic varieties. Perelman's result on the Poincare conjecture for 
> homotopy of the 3-sphere relies on the Hamilton equation of Ricci evolution. 
> In both of these cases I read these and followed the key results and ideas, 
> though there were a lot of details I tended to run over. Proofs seem likely 
> to press into ever more complex and lengthy things. A more empirical stance 
> on mathematics has taken off, where many people just do not have the patience 
> for working out massive proofs. 
> 
> I can imagine GH Hardy, A Mathematician's Apology, is rolling in his grave.


Yes.

A part of my problem, with a part of the Academy, comes from the fact that 
“mathematical logic” has been put in the “pure mathematic” category. I choose 
“pure mathematics” because I discovered *application* of mathematical logic, 
very well known now, but those were denied at my time. (Application in computer 
science, biology, I did not mentioned “theology”!).

Mathematicians are super-susceptible beings, often quite conservative. 

I love GH Hardy for its ultra clear realist claim, and I took from him the idea 
that a natural number is the 

Re: A Church-Turing-Thesis for Infinitary Computations

[Bruno Marchal]

and Robinson arithmetic is consistent with the existence 
> of a greatest integer.
> 
> 
> 
> 
>> 
>> In any case: 
>> 
>> Mathematics (at least Applied Math, and its twin sister, Computing) have 
>> only to do with what one can do, not with what is true.
> 
> Theoretical computer science has a lot to do with the things that we, the 
> machines, cannot do, indeed, even with what we cannot do despite the use of 
> powerful oracle. Recursion theory is the study of the degree of 
> unsolvability, and the while truth has something to say for theology and the 
> origin of the physical laws.
> 
> Bruno
> 
> 
> 
> What a theory (a linguistic expression we make up and hope turns out to me 
> useful) permits or does not permit is irrelevant to whether nature permits it 
> or not.
> 
> 
> Max Tegmark's dictum:
> 
> "Not only do we lack evidence for the infinite

Hmm… In the ontology, mechanism forbid it, but phenomenologically I would say 
that there are many evidence of a very important role of the infinite and the 
infinities, and it is obvious that it plays an important role in the physical 
theories, from the use of calculus, distributions, Hilbert space to even weird 
infinite sum justified by the weirdness, or lack of weirdness, of the behaviour 
of the prime number (zeta-regulation, 1+2+3+4+… = -1/12).







> but we don’t need the infinite to do physics.


Hmm… 




> Our best computer simulations, accurately describing everything from the 
> formation of galaxies to tomorrow’s weather to the masses of elementary 
> particles, use only finite computer resources by treating everything as 
> finite.


That’s true, and this implies Mechanism, but the problem is that with 
Mechanism, we cannot know which computations supports us. We know there is an 
infinity of them, and that we survive on an infinity of them, or at least, that 
our most plausible consciousness state follows a Gaussian on an infinities of 
“close” consistent histories, and coherent too in sense formally close to the 
quantum formal sense, through a proximity relation.





> So if we can do without infinity to figure out what happens next,


Yes, Nature exploits this all the time. It is what happen next, and next that, 
and next that, and next that … which is more challenging.
Who are we? Where do we come from? Where are we going?




> surely nature can, too—in a way that’s more deep and elegant than the hacks 
> we use for our computer simulations. Our challenge as physicists is to 
> discover this elegant way and the infinity-free equations describing it—the 
> true laws of physics. To start this search in earnest, we need to question 
> infinity. I’m betting that we also need to let go of it.”


With mechanism, we have to get rid of the infinite for the ontological 
assumption, although a potential infinite remains necessary at the semantical 
level.

We believe only in finite things, like 0, s0, ss0, sss0, 0, ..;, but we 
know that in the intended model, thy are all there, but, like In Plotinus in 
its “Number” chapter, the number of numbers is not a number, and all object in 
the terrestrial plane are finite. Same for the combinatory algebra. They 
possess K, S, KK, KS, …, but unless K = S, they is an infinity of 
combinators/programs.

Like we can define the universal Turing machine in any such system, and we get 
the existence of all Turiing machine. Each are finite, but their task can be 
infinite, and their numbers (of Turing machines) is infinite (aleph_0).

True/false. Finite/infinite, computable/non-computable, are all a bit like 
in-the-Mandelbrot-set/out-of-the-Manderbrot set.
They are clear cases of points in the M set, and out of the M set, but for some 
points, it is no so easy if they are in or out, and it is in those fuzzy region 
that the interesting things happen, like life, though, and possibly very long 
and deep first person plural sharable dreams.




> 
> 
> Now suppose some part of nature does go outside these boundaries. 
> 
> In programming, it would be like including promises
> 
> https://en.wikipedia.org/wiki/Futures_and_promises 
> <https://en.wikipedia.org/wiki/Futures_and_promises>
> 
> (in this case a promise of an infinite phenomenon that may or may not be 
> realized).


I doubt that there are actual infinities in nature, but there are indispensable 
infinities for studying the finite realms, and the first person experience is 
already directly related to the infinite “random” oracle of the dispersion in 
the universal dovetailing (aka sigma_1 arithmetic).

The infinities are important in theology, as Cantor was well aware of.

It concerns more the Vertical dimension of theology. To extract physics, we are 
concerned with a more horizontal measure. 

Yet, I got evidence (based on some conjecture about the quantisations though) 
t

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

*Computability and Complexity of Unconventional Computing Devices*
Hajo Broersma, Susan Stepney, Goran Wendin
(Submitted on 9 Feb 2017 (v1), last revised 23 Mar 2017 (this version, v2))
https://arxiv.org/abs/1702.02980

We discuss some claims that certain UCOMP devices can perform 
hypercomputation (compute Turing-uncomputable functions) or perform 
super-Turing computation (*solve NP-complete problems in polynomial time*). 
We discover that all these claims *rely on the provision of one or more 
unphysical resources*.

@philipthrift

On Saturday, March 21, 2020 at 11:04:57 AM UTC-5, Philip Thrift wrote:
>
>
>
> The paper brought up by someone on
>
> http://backreaction.blogspot.com/2020/03/unpredictability-undecidability-and.html
>
>
> *Computability and Physical Theories*
> Robert Geroch, James B. Hartle
> arXiv:1806.09237
>
> "We suggest that [a theory having measurable numbers that *are not 
> computable*] should be no more unsettling to physics than has the 
> existence of well-posed problems unsolvable by any algorithm been to 
> mathematics."
>
> says they (and apparently many physicists) already think* nature 
> hypercomputes.*
>  
> Maybe it does, but again *physicists confuse nature and mathematics*.
>
> @philipthrift
>
>
> On Saturday, March 21, 2020 at 9:09:46 AM UTC-5, Lawrence Crowell wrote:
>>
>> Todd Brun found [ https://arxiv.org/pdf/gr-qc/0209061v1.pdf ] that P = 
>> NP is true for closed timelike curves. This is a short, readable and decent 
>> paper. The extension to all PSPACE and undecidable propositions is of 
>> course difficult to prove explicitly. However, a spacetime that permits 
>> CTCs will present Cauchy horizons, and in principle an observer can in a 
>> finite time verify whether a Turing machine halts or does not halt, even if 
>> the proper time of that TM is infinite. This is of course an in principle 
>> argument. 
>>
>> It is potentially interesting in the context of P = NP vs P ≠ NP whether 
>> this result really does mean this is undecidable proposition. P = NP 
>> appears true in a spacetime with CTCs, such as AdS or wormholes and so 
>> forth. We have no knowledge whether P = NP can hold in our more normal 
>> dS-like spacetime with positive vacuum energy.
>>
>> Aaronson and Watrous found [ https://arxiv.org/pdf/0808.2669.pdf ] that 
>> classical systems on closed timelike curves can perform some BQP algorithms 
>> quantum computers execute. This emboldens my hypothesis that quantum 
>> physics and spacetime physics are categorically equivalent, or that 
>> spacetime is an epiphenomenon of large N-entanglements. On the top of page 
>> 5 of this paper is an interesting diagram. This illustrates a register or 
>> memory system with two parts, one part for a spacetime such as what we 
>> observe with open timelike curves and another with part with closed 
>> timelike curves. Aaronson and Watrous argue the Deutsche self-consistency 
>> condition on CTCs should hold and that a quantum wave corresponding to the 
>> causality respecting must also constructively interfere with the CTC wave 
>> function. The argument then is it is possible to emulate all PSPACE this 
>> way.
>>
>> Spacetimes such as Gödel’s universe, the global metric on AdS or the 
>> timelike interior of a Kerr black hole have CTCs. BTW, it appears that 
>> Gödel had some mental obsession with closed loopy systems! The question 
>> might be raised, what is the separation or distinction between causal 
>> respecting CR and closed timelike curve CTC spaces? The diagram on the AW 
>> paper suggests there is some quantum wave interference between a wave 
>> function associated with the CR and CTC spacetimes. The de Sitter and 
>> anti-de Sitter spaces respectively fit as a single sheet hyperboloid 
>> surrounding a light cone and two hyperboloids bounded within the conical 
>> openings. These meet at I^{±∞}, which means they share the same quantum 
>> information as defined by the AdS/CFT correspondence of Maldacena et al. . 
>> In the setting of holography we have something similar, and there are 
>> arguments of AdS black hole correspondence as well. 
>>
>> This according to A. Almheiri1, R. Mahajan, J. Maldacena, and Y. Zhao 
>> (AMMZ) [ arXiv:1908.10996v1  [hep-th] ] also has some correspondence with 
>> the interior state of a black hole. This paper is rather qualitative and 
>> speculative. The idea is the interior of a black hole has “islands” of 
>> states defined by a dimension difference of one. We might compare this to 
>> how the Reisner-Nordstrom metric, and by extension the Kerr metric, has a 
>> near horizon condition for an accelerated observer equivalent to AdS_2×
>> *S*^2. The AdS globally has CTCs, and locally we consider conformal 
>> patches that restrict away from CTCs and respects CR. What I am working on 
>> now is to illustrate how the AMMZ islands correspond to local AdS regions 
>> or conformal patches. This would imply event horizons or boundaries imposes 
>> restrictions away 

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

The paper brought up by someone on
http://backreaction.blogspot.com/2020/03/unpredictability-undecidability-and.html


*Computability and Physical Theories*
Robert Geroch, James B. Hartle
arXiv:1806.09237

"We suggest that [a theory having measurable numbers that *are not 
computable*] should be no more unsettling to physics than has the existence 
of well-posed problems unsolvable by any algorithm been to mathematics."

says they (and apparently many physicists) already think* nature 
hypercomputes.*
 
Maybe it does, but again *physicists confuse nature and mathematics*.

@philipthrift


On Saturday, March 21, 2020 at 9:09:46 AM UTC-5, Lawrence Crowell wrote:
>
> Todd Brun found [ https://arxiv.org/pdf/gr-qc/0209061v1.pdf ] that P = NP 
> is true for closed timelike curves. This is a short, readable and decent 
> paper. The extension to all PSPACE and undecidable propositions is of 
> course difficult to prove explicitly. However, a spacetime that permits 
> CTCs will present Cauchy horizons, and in principle an observer can in a 
> finite time verify whether a Turing machine halts or does not halt, even if 
> the proper time of that TM is infinite. This is of course an in principle 
> argument. 
>
> It is potentially interesting in the context of P = NP vs P ≠ NP whether 
> this result really does mean this is undecidable proposition. P = NP 
> appears true in a spacetime with CTCs, such as AdS or wormholes and so 
> forth. We have no knowledge whether P = NP can hold in our more normal 
> dS-like spacetime with positive vacuum energy.
>
> Aaronson and Watrous found [ https://arxiv.org/pdf/0808.2669.pdf ] that 
> classical systems on closed timelike curves can perform some BQP algorithms 
> quantum computers execute. This emboldens my hypothesis that quantum 
> physics and spacetime physics are categorically equivalent, or that 
> spacetime is an epiphenomenon of large N-entanglements. On the top of page 
> 5 of this paper is an interesting diagram. This illustrates a register or 
> memory system with two parts, one part for a spacetime such as what we 
> observe with open timelike curves and another with part with closed 
> timelike curves. Aaronson and Watrous argue the Deutsche self-consistency 
> condition on CTCs should hold and that a quantum wave corresponding to the 
> causality respecting must also constructively interfere with the CTC wave 
> function. The argument then is it is possible to emulate all PSPACE this 
> way.
>
> Spacetimes such as Gödel’s universe, the global metric on AdS or the 
> timelike interior of a Kerr black hole have CTCs. BTW, it appears that 
> Gödel had some mental obsession with closed loopy systems! The question 
> might be raised, what is the separation or distinction between causal 
> respecting CR and closed timelike curve CTC spaces? The diagram on the AW 
> paper suggests there is some quantum wave interference between a wave 
> function associated with the CR and CTC spacetimes. The de Sitter and 
> anti-de Sitter spaces respectively fit as a single sheet hyperboloid 
> surrounding a light cone and two hyperboloids bounded within the conical 
> openings. These meet at I^{±∞}, which means they share the same quantum 
> information as defined by the AdS/CFT correspondence of Maldacena et al. . 
> In the setting of holography we have something similar, and there are 
> arguments of AdS black hole correspondence as well. 
>
> This according to A. Almheiri1, R. Mahajan, J. Maldacena, and Y. Zhao 
> (AMMZ) [ arXiv:1908.10996v1  [hep-th] ] also has some correspondence with 
> the interior state of a black hole. This paper is rather qualitative and 
> speculative. The idea is the interior of a black hole has “islands” of 
> states defined by a dimension difference of one. We might compare this to 
> how the Reisner-Nordstrom metric, and by extension the Kerr metric, has a 
> near horizon condition for an accelerated observer equivalent to AdS_2×*S*^2. 
> The AdS globally has CTCs, and locally we consider conformal patches that 
> restrict away from CTCs and respects CR. What I am working on now is to 
> illustrate how the AMMZ islands correspond to local AdS regions or 
> conformal patches. This would imply event horizons or boundaries imposes 
> restrictions away from a complete correspondence. This is in line with my 
> FQXi paper on topological restrictions between entanglement types and their 
> correspondence with Szangolies’ concept of the epistemic horizon. 
>
> The issue with P = NP vs P ≠ NP is then still open. As I approach this 
> with p-adic numbers and the Gödel undecidability of these sets, a complex 
> number version corresponds to problems in algebraic geometry. Mulmuley has 
> devoted much work on the algebraic geometry of computation. This leads to 
> interesting issues with the Riemann ζ-function.
>
> LC
>
>
> On Saturday, March 21, 2020 at 4:35:51 AM UTC-5, Philip Thrift wrote:
>>
>>
>>
>> Gregory Chaitin's *The Limits of Reason*
>>
>>
>> 

Re: A Church-Turing-Thesis for Infinitary Computations

[Bruno Marchal]

> On 20 Mar 2020, at 14:56, Philip Thrift  wrote:
> 
> 
> 
> On Friday, March 20, 2020 at 4:03:36 AM UTC-5, Bruno Marchal wrote:
> 
>> On 19 Mar 2020, at 20:05, Philip Thrift > 
>> wrote:
>> 
>> 
>> 
>> On Thursday, March 19, 2020 at 9:34:36 AM UTC-5, Bruno Marchal wrote:
>> 
>>> On 18 Mar 2020, at 11:38, Philip Thrift > wrote:
>>> 
>>> 
>>> 
>>> It is a contradiction for a physicist to say, literally,
>>> 
>>>  nothing real is infinite
>>> 
>>> http://backreaction.blogspot.com/2020/03/unpredictability-undecidability-and.html
>>>  
>>> 
>>> 
>>> yet their physics extensively uses infinitary mathematics
>>> 
>>> https://physics.stackexchange.com/questions/149786/why-do-we-need-infinite-dimensional-hilbert-spaces-in-physics
>>>  
>>> 
>>> 
>>> (To be consistent: All theoretical physics should be based on discrete, 
>>> finite mathematics. with no violations permitted. That, or the premise 
>>> itself should be voided.)
>> 
>> 
>> The problem is that any finite mathematics, rich enough to define what it is 
>> a computer, will have a extremely complex semantics, full of infinities.
>> 
>> Before Gödel, we though we could protect the use of the infinities by 
>> handling their finite descriptions only.
>> After Gödel, we know that we cannot even protect the finitely realm by 
>> itself, and that we have to use infinities to manage even very partial 
>> “protection”.
>> 
>> We can no more separate the finite from the infinite. In fact, we cannot 
>> even really get a precise (first-order) analysis of what finite means, even 
>> by using strong powerful theory like ZFC. Some same object can be finite in 
>> a model, and infinite in another model.
>> 
>> What we can do, and what I have done with Mechanism, is to limite the 
>> ontology on the finite things, in their intuitive usual sense, and put all 
>> the infinities (including the physical) in the phenomenologies associated 
>> with the observers.
>> 
>> Bruno
>> 
>> 
>> 
>> From the P-L-T-O-S (program-language-translator-object-semantics) framework, 
>> the only models are only those that exist in the universe - the 
>> physical-material universe, or PMU, to use the vernacular of the science 
>> types. 
> 
> If you *assume* a primitive physical universe, then you have to abandon the 
> digital mechanist thesis. (That is the first half of my contribution, and if 
> you have not grasp this I can explain).
> No ontological commitment can select a computation, as seen from the first 
> person perspective, and make it more real than those emulated in the 
> arithmetical reality, because this would provide a non Turing emulable role 
> of that physical reality with respect to the mind/consciousness.
> Also, my goal is to explain matter, or its conscious appearrances, so I 
> prefer to be neutral on this at the start.
> 
> 
> 
>> 
>> So whatever can be mapped to some subset of the PMU are the only models 
>> there can be.
>> 
>> Now it is possible that 
>> 
>> a computer operating in a Malament–Hogarth spacetime or in orbit around a 
>> rotating black hole could theoretically perform non-Turing computations for 
>> an observer inside the black hole
> 
> In principle, but quantum mechanics makes this quite unlikely to happen.
> 
> 
> 
>> 
>> if the PMU permits it.
>> 
>> (Scientific theories are completely irrelevant to whether this phenomenon 
>> can happen. If it can't happen, it can't happen.)
> 
> ?
> 
> It can happen with GR. But it cannot happen with QM. Eventually we need a 
> theory making QM and GR consistent. We are not there yet, and with mechanism, 
> we have to extract it from the relative measure on all computations.
> 
> 
>> 
>> In any case, statements like there are an infinite number of integers may be 
>> false (which would automatically let the air out of the hypercomputation 
>> balloon).
> 
> Frankly, I don’t see how “there are an infinite number of integers” can be 
> false, no matter which metaphysics principle we accept. But this is not 
> relevant, as the ontological part of the “theory of everything” does not use 
> any infinity axiom, and Robinson arithmetic is consistent with the existence 
> of a greatest integer.
> 
> 
> 
> 
>> 
>> In any case: 
>> 
>> Mathematics (at least Applied Math, and its twin sister, Computing) have 
>> only to do with what one can do, not with what is true.
> 
> Theoretical computer science has a lot to do with the things that we, the 
> machines, cannot do, indeed, even with what we cannot do despite the use of 
> powerful oracle. Recursion theory is the study of the degree of 
> unsolvability, and the while truth has something to say for theology and the 
> origin of the physical laws.
> 
> Bruno
> 
> 
> 
> What a theory (a linguistic expression we make up and hope turns out to me 
> useful) permits or 

Re: A Church-Turing-Thesis for Infinitary Computations

[Lawrence Crowell]

Todd Brun found [ https://arxiv.org/pdf/gr-qc/0209061v1.pdf ] that P = NP 
is true for closed timelike curves. This is a short, readable and decent 
paper. The extension to all PSPACE and undecidable propositions is of 
course difficult to prove explicitly. However, a spacetime that permits 
CTCs will present Cauchy horizons, and in principle an observer can in a 
finite time verify whether a Turing machine halts or does not halt, even if 
the proper time of that TM is infinite. This is of course an in principle 
argument. 

It is potentially interesting in the context of P = NP vs P ≠ NP whether 
this result really does mean this is undecidable proposition. P = NP 
appears true in a spacetime with CTCs, such as AdS or wormholes and so 
forth. We have no knowledge whether P = NP can hold in our more normal 
dS-like spacetime with positive vacuum energy.

Aaronson and Watrous found [ https://arxiv.org/pdf/0808.2669.pdf ] that 
classical systems on closed timelike curves can perform some BQP algorithms 
quantum computers execute. This emboldens my hypothesis that quantum 
physics and spacetime physics are categorically equivalent, or that 
spacetime is an epiphenomenon of large N-entanglements. On the top of page 
5 of this paper is an interesting diagram. This illustrates a register or 
memory system with two parts, one part for a spacetime such as what we 
observe with open timelike curves and another with part with closed 
timelike curves. Aaronson and Watrous argue the Deutsche self-consistency 
condition on CTCs should hold and that a quantum wave corresponding to the 
causality respecting must also constructively interfere with the CTC wave 
function. The argument then is it is possible to emulate all PSPACE this 
way.

Spacetimes such as Gödel’s universe, the global metric on AdS or the 
timelike interior of a Kerr black hole have CTCs. BTW, it appears that 
Gödel had some mental obsession with closed loopy systems! The question 
might be raised, what is the separation or distinction between causal 
respecting CR and closed timelike curve CTC spaces? The diagram on the AW 
paper suggests there is some quantum wave interference between a wave 
function associated with the CR and CTC spacetimes. The de Sitter and 
anti-de Sitter spaces respectively fit as a single sheet hyperboloid 
surrounding a light cone and two hyperboloids bounded within the conical 
openings. These meet at I^{±∞}, which means they share the same quantum 
information as defined by the AdS/CFT correspondence of Maldacena et al. . 
In the setting of holography we have something similar, and there are 
arguments of AdS black hole correspondence as well. 

This according to A. Almheiri1, R. Mahajan, J. Maldacena, and Y. Zhao 
(AMMZ) [ arXiv:1908.10996v1  [hep-th] ] also has some correspondence with 
the interior state of a black hole. This paper is rather qualitative and 
speculative. The idea is the interior of a black hole has “islands” of 
states defined by a dimension difference of one. We might compare this to 
how the Reisner-Nordstrom metric, and by extension the Kerr metric, has a 
near horizon condition for an accelerated observer equivalent to AdS_2×*S*^2. 
The AdS globally has CTCs, and locally we consider conformal patches that 
restrict away from CTCs and respects CR. What I am working on now is to 
illustrate how the AMMZ islands correspond to local AdS regions or 
conformal patches. This would imply event horizons or boundaries imposes 
restrictions away from a complete correspondence. This is in line with my 
FQXi paper on topological restrictions between entanglement types and their 
correspondence with Szangolies’ concept of the epistemic horizon. 

The issue with P = NP vs P ≠ NP is then still open. As I approach this with 
p-adic numbers and the Gödel undecidability of these sets, a complex number 
version corresponds to problems in algebraic geometry. Mulmuley has devoted 
much work on the algebraic geometry of computation. This leads to 
interesting issues with the Riemann ζ-function.

LC


On Saturday, March 21, 2020 at 4:35:51 AM UTC-5, Philip Thrift wrote:
>
>
>
> Gregory Chaitin's *The Limits of Reason*
>
>
> http://www.cs.virginia.edu/~robins/The_Limits_of_Reason_Chaitin_2006.pdf
>
> shows math as a jungle only small, isolated pockets of which are ever 
> explored.
>
> That humans may feel that they need :proofs" maybe on a few pages long  is 
> merely an unfounded bias. Maybe the "interesting" and "important" things to 
> be proved require 100,000 pages or 1,000,000 pages to print out.
>
> Or maybe the desire for proofs themselves is just are a human failing.
>
> @philipthrift
>
>
> @philipthrift
> On Friday, March 20, 2020 at 2:10:45 PM UTC-5, Lawrence Crowell wrote:
>>
>> On Thursday, March 19, 2020 at 11:48:00 PM UTC-5, Philip Thrift wrote:
>>>
>>>
>>>
>> I guess I am not sure why you say there is actual damage done. It see the 
>> two approaches as worthy in their own right. What might be called 

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

Gregory Chaitin's *The Limits of Reason*

   http://www.cs.virginia.edu/~robins/The_Limits_of_Reason_Chaitin_2006.pdf

shows math as a jungle only small, isolated pockets of which are ever 
explored.

That humans may feel that they need :proofs" maybe on a few pages long  is 
merely an unfounded bias. Maybe the "interesting" and "important" things to 
be proved require 100,000 pages or 1,000,000 pages to print out.

Or maybe the desire for proofs themselves is just are a human failing.

@philipthrift


@philipthrift
On Friday, March 20, 2020 at 2:10:45 PM UTC-5, Lawrence Crowell wrote:
>
> On Thursday, March 19, 2020 at 11:48:00 PM UTC-5, Philip Thrift wrote:
>>
>>
>>
> I guess I am not sure why you say there is actual damage done. It see the 
> two approaches as worthy in their own right. What might be called Greek 
> mathematics has lead us into a field where proofs of the great unknown 
> problems are huge affairs with hundreds of pages. Wiles' result with the 
> Fermat Theorem is 200 some pages of detailed work with algebraic varieties. 
> Perelman's result on the Poincare conjecture for homotopy of the 3-sphere 
> relies on the Hamilton equation of Ricci evolution. In both of these cases 
> I read these and followed the key results and ideas, though there were a 
> lot of details I tended to run over. Proofs seem likely to press into ever 
> more complex and lengthy things. A more empirical stance on mathematics has 
> taken off, where many people just do not have the patience for working out 
> massive proofs. 
>
> I can imagine GH Hardy, *A Mathematician's Apology*, is rolling in his 
> grave.
>
> LC
>  
>
>>
>> *Opinion 174: The "Greek" (Euclidean, Axiomatic, Deductive. ...) approach 
>> to mathematics did much more damage than just ruin mathematics, as is clear 
>> from Amir Alexander's fascinating new Book "Proof!". It is high time that 
>> we move over to the much more democratic and egalitarian (and far less 
>> boring!) "Babylonian" (Algorithmic, Inductive, Experimental,...) approach 
>> to mathematics*
>>
>> By Doron Zeilberger
>> Written: Oct. 20, 2019
>>
>> Way back in the mid 1960s, when I was in ninth grade, we still learned 
>> Plane Geometry the traditional way, essentially following (a watered-down, 
>> but methodologically isomorphic) version of Euclid's 2300-year-old 
>> Elements. This awful text, with its false claims to absolute truth, was 
>> almost as influential as the bible, and many generations of students shed 
>> tears trying to "prove" (often intuitively obvious) propositions, by a 
>> step-by-step "deductive" process. On the other hand, quite a few otherwise 
>> very smart people (Spinoza, Hobbes, ... ) loved it, and used its 
>> (apparent!) air of absolute certainty, adapting Euclid's style, to claim 
>> that their philosophical theses are just as absolutely certain.
>>
>> But (most) philosophers are basically good guys, and I forgive them. On 
>> the other hand, absolute monarchs, and other tyrants, are not! What I found 
>> out from Amir Alexander's fascinating new book Proof! (How the World Became 
>> Geometrical) was how Euclidean Geometry was abused by them to "prove" their 
>> inherent superiority. The `canonical example', narrated at length in the 
>> book, was Louis XIV, who commissioned a very elaborate geometrical garden, 
>> the famous Jardins du Château de Versailles, to prove his point. It was a 
>> proof by analogy. Just as the theorems of Euclidean Geometry are absolutely 
>> certain, it is absolutely certain that someone who can build such an 
>> elaborate and spectacular garden has a divine right to his position.
>>
>> As Alexander describes in his gripping style, the Sun King's "proof" was 
>> borrowed by quite a few other absolute monarchs, and colonial invaders (for 
>> example the British in India) to construct gardens, and later whole cities, 
>> inspired by Versailles, to "prove" that their occupation is true a priori 
>> and just as justified as the Pythagorean theorem.
>>
>> In the climax of the book, it is described that even our beloved capital 
>> city, Washington DC, was designed, by French-born-and-educated architect 
>> Pierre L'Enfant, in the style of Versailles, slightly tweaked to make it 
>> more egalitarian, but essentially to make a similar point, the superiority 
>> of the American democracy.
>>
>> Not everyone agreed with L'Enfant's design, and one strong opponent was 
>> no other than Thomas Jefferson, who much preferred the "Babylonian" (I 
>> guess it was an allusion to Hammurabi's invention of streets), or 
>> "Cartesian" Manhattan lattice grid. This plan was so abhorrent to L'Enfant 
>> that he forgot his usual smooth manners, to criticize Jefferson's plan so 
>> strongly, something that got him fired. But someone else, whose name was 
>> George Washington, did like L'Enfant's plan, and the latter's design was 
>> completed by other people.
>>
>> This got me thinking, that myself, I am siding with Jefferson, and I like 
>> a 

Re: A Church-Turing-Thesis for Infinitary Computations

[Lawrence Crowell]

On Thursday, March 19, 2020 at 11:48:00 PM UTC-5, Philip Thrift wrote:
>
>
>
> On Thursday, March 19, 2020 at 7:13:10 PM UTC-5, Lawrence Crowell wrote:
>>
>>
>>
>> On Thursday, March 19, 2020 at 9:54:58 AM UTC-5, Bruno Marchal wrote:
>>>
>>>
>>> On 18 Mar 2020, at 14:42, Lawrence Crowell  
>>> wrote:
>>>
>>> On Wednesday, March 18, 2020 at 4:13:36 AM UTC-5, Bruno Marchal wrote:


 On 17 Mar 2020, at 16:14, Lawrence Crowell  
 wrote:

 I pretty seriously doubt these things will enter into physics. 
 Computations with Cantor's aleph hierarchy of transfinite numbers seems 
 pretty far removed from anything really physical.



 OK. It is just abstract recursion theory, has been with Turing, and it 
 concerns divine creatures, and the goal is to show that even those 
 “divine” 
 (infinite being) cannot effectively recover the arithmetical 
 truth/reality. 
 I doubt too that such machine can be brought to Earth, and they do play 
 some role in the internal phenomenology of the “terrestrial machine”, a 
 bit 
 like infinite sums can play a role in physics, like the zeta 
 renormalisation in superstring theory.
 Note that most of those divine (infinite) machine are still obeying to 
 the same self-reference logics (G and G*), and would not change much in 
 the 
 mathematical derivation of physics from arithmetic. Note also that the 
 first person indeterminacy is connected to the machine + random oracle, so 
 that the “sigma_1” predicate is really sigma_1 in all oracles, and this 
 makes it possible to use some strong set axiom (like “projective 
 determinacy”) to assure the existence of the measure, and probably of the 
 needed generalisation of Feynman integral in arithmetic. (This needs 
 indeed 
 a generalisation of the Church’s thesis, called the hyperarihmetical 
 church’s thesis in the classical  textbook by Rogers).

 Bruno



>>> When we get into subtleties of ZF set theory we get into the application 
>>> of axioms, eg the axiom of replacement, axiom of infinity, axiom of choice 
>>> etc, that have a limited bearing on most standard mathematics. 
>>>
>>>
>>>
>>> I am not sure why you say this. Most mathematician would say that ZF is 
>>> just the usual intuition of sets made precise. Most people understand the 
>>> need (and the power) of the infinity axiom, so that we can talk about 
>>> infinite set like N, Q, R, C etc., and the functions in between those sets 
>>> of numbers, matrices, etc. The axiom of choice is just obvious, and the 
>>> fact that it cannot be proved is no more astonishing than the fact that we 
>>> cannot prove any axiom of Robinson Arithmetic from any of its other axioms.
>>>
>>>
>>>
>> In the field of physics mathematics is regarded as a tool or language. I 
>> think that Feynman put it best with his talk about Greek mathematics vs 
>> Babylonian mathematics. Greek mathematics with its precise ε - δ 
>> theorem-proof system is "hard" in that you know within any system its 
>> results are absolute. However, the Babylonians tended to do practical math, 
>> what sometimes is called "maths," which has a certain quick utility to it. 
>> I tend to have a foot in both camps, though I have to admit more weight is 
>> placed on the Babylonian side. For this reason few physicists give much 
>> consideration of ZF axiomatic models. I have to admit I generally give 
>> these things much consideration.
>>
>> LC
>>  
>>
>
>
I guess I am not sure why you say there is actual damage done. It see the 
two approaches as worthy in their own right. What might be called Greek 
mathematics has lead us into a field where proofs of the great unknown 
problems are huge affairs with hundreds of pages. Wiles' result with the 
Fermat Theorem is 200 some pages of detailed work with algebraic varieties. 
Perelman's result on the Poincare conjecture for homotopy of the 3-sphere 
relies on the Hamilton equation of Ricci evolution. In both of these cases 
I read these and followed the key results and ideas, though there were a 
lot of details I tended to run over. Proofs seem likely to press into ever 
more complex and lengthy things. A more empirical stance on mathematics has 
taken off, where many people just do not have the patience for working out 
massive proofs. 

I can imagine GH Hardy, *A Mathematician's Apology*, is rolling in his 
grave.

LC
 

>
> *Opinion 174: The "Greek" (Euclidean, Axiomatic, Deductive. ...) approach 
> to mathematics did much more damage than just ruin mathematics, as is clear 
> from Amir Alexander's fascinating new Book "Proof!". It is high time that 
> we move over to the much more democratic and egalitarian (and far less 
> boring!) "Babylonian" (Algorithmic, Inductive, Experimental,...) approach 
> to mathematics*
>
> By Doron Zeilberger
> Written: Oct. 20, 2019
>
> Way back in the mid 1960s, when I was in ninth grade, we 

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

On Friday, March 20, 2020 at 4:03:36 AM UTC-5, Bruno Marchal wrote:
>
>
> On 19 Mar 2020, at 20:05, Philip Thrift > 
> wrote:
>
>
>
> On Thursday, March 19, 2020 at 9:34:36 AM UTC-5, Bruno Marchal wrote:
>>
>>
>> On 18 Mar 2020, at 11:38, Philip Thrift  wrote:
>>
>>
>>
>> It is a contradiction for a physicist to say, literally,
>>
>>  *nothing real is infinite*
>>
>>
>> http://backreaction.blogspot.com/2020/03/unpredictability-undecidability-and.html
>>
>> yet their physics extensively uses infinitary mathematics
>>
>>
>> https://physics.stackexchange.com/questions/149786/why-do-we-need-infinite-dimensional-hilbert-spaces-in-physics
>>
>> (To be consistent: All theoretical physics should be based on *discrete, 
>> finite mathematics*. with *no violations permitted*. That, or the 
>> premise itself should be voided.)
>>
>>
>>
>> The problem is that any finite mathematics, rich enough to define what it 
>> is a computer, will have a extremely complex semantics, full of infinities.
>>
>> Before Gödel, we though we could protect the use of the infinities by 
>> handling their finite descriptions only.
>> After Gödel, we know that we cannot even protect the finitely realm by 
>> itself, and that we have to use infinities to manage even very partial 
>> “protection”.
>>
>> We can no more separate the finite from the infinite. In fact, we cannot 
>> even really get a precise (first-order) analysis of what finite means, even 
>> by using strong powerful theory like ZFC. Some same object can be finite in 
>> a model, and infinite in another model.
>>
>> What we can do, and what I have done with Mechanism, is to limite the 
>> ontology on the finite things, in their intuitive usual sense, and put all 
>> the infinities (including the physical) in the phenomenologies associated 
>> with the observers.
>>
>> Bruno
>>
>>
>>
> From the *P-L-T-O-S (program-language-translator-object-semantics) 
> *framework, 
> the only models are only those that exist in the universe - the 
> physical-material universe, or PMU, to use the vernacular of the science 
> types. 
>
>
> If you *assume* a primitive physical universe, then you have to abandon 
> the digital mechanist thesis. (That is the first half of my contribution, 
> and if you have not grasp this I can explain).
> No ontological commitment can select a computation, as seen from the first 
> person perspective, and make it more real than those emulated in the 
> arithmetical reality, because this would provide a non Turing emulable role 
> of that physical reality with respect to the mind/consciousness.
> Also, my goal is to explain matter, or its conscious appearrances, so I 
> prefer to be neutral on this at the start.
>
>
>
>
> So whatever can be mapped to some subset of the PMU are the only models 
> there can be.
>
> Now it is possible that 
>
> *a computer operating in a Malament–Hogarth spacetime or in orbit around a 
> rotating black hole could theoretically perform non-Turing computations for 
> an observer inside the black hole*
>
>
> In principle, but quantum mechanics makes this quite unlikely to happen.
>
>
>
>
> if the PMU permits it.
>
> (Scientific theories are completely irrelevant to whether this phenomenon 
> can happen. If it can't happen, it can't happen.)
>
>
> ?
>
> It can happen with GR. But it cannot happen with QM. Eventually we need a 
> theory making QM and GR consistent. We are not there yet, and with 
> mechanism, we have to extract it from the relative measure on all 
> computations.
>
>
>
> In any case, statements like* there are an infinite number of integers* 
> may be false (which would automatically let the air out of the 
> hypercomputation balloon).
>
>
> Frankly, I don’t see how “there are an infinite number of integers” can be 
> false, no matter which metaphysics principle we accept. But this is not 
> relevant, as the ontological part of the “theory of everything” does not 
> use any infinity axiom, and Robinson arithmetic is consistent with the 
> existence of a greatest integer.
>
>
>
>
>
> In any case: 
>
> *Mathematics (at least Applied Math, and its twin sister, Computing) have 
> only to do with what one can do, not with what is true.*
>
>
> Theoretical computer science has a lot to do with the things that we, the 
> machines, cannot do, indeed, even with what we cannot do despite the use of 
> powerful oracle. Recursion theory is the study of the degree of 
> unsolvability, and the while truth has something to say for theology and 
> the origin of the physical laws.
>
> Bruno
>
>
>
What a theory (a linguistic expression we make up and hope turns out to me 
useful) permits or does not permit is irrelevant to whether nature permits 
it or not.


Max Tegmark's dictum:

"Not only do we lack evidence for the infinite but *we don’t need the 
infinite to do physics*. Our best computer simulations, accurately 
describing everything from the formation of galaxies to tomorrow’s weather 
to the masses of elementary 

Re: A Church-Turing-Thesis for Infinitary Computations

[Bruno Marchal]

making mathematics much easier. 
> 
> 
> 
> 
>> Transfinite numbers and the question of א_0 ≤ c ≤ 2^א_0 or the continuum 
>> hypothesis has a role with Robinson’s numbers.
> 
> 
> You mean Robinson non standard analysis. This shows something 
> “sociologically” interesting, as it refutes many old authors, like Carnot for 
> example, or Berkeley, who were convinced that Lebiniz and Newton’s notion of 
> infinitesimal were incoherent. The use of non standard model of arithmetic 
> shows that those infinitesimal can be consistently add to the classical 
> theory, and so we get relative consistency result.
> 
> Now, some advocates that we use them in the teaching of analysis, but here I 
> am with the majority who think that the Cauchy epsilon-eta definition of 
> continuity and differentiability is much simpler, and avoid the appendices on 
> Mathematical Logic. 
> 
> 
> 
>> These are in a sense the reciprocals of transfinite numbers or the 
>> continuum. This has some bearing in the foundations of calculus, though I am 
>> far from familiar with this. I am not sure what possible role this could 
>> have for physics.
> 
> Neither am I. But we never known. Note that category theory has also provided 
> “synthetic differential calculus”, which are non standard, but have some 
> appeal in algebraic geometry. 
> 
> 
> 
>> 
>> Infinite mathematical quantities are common in physics. The 2-dim CFT is 
>> Virasoro which is a Witt algebra extended to infinite dimensions with a 
>> kernel. This does not though mean physics predicts the measurement of 
>> infinite quantities 
> 
> Indeed. In physics, the mathematics is neutral, and its infinities can be put 
> on the phenomenological side. But with mechanism, there remain some realism 
> about the phenomenology, and choice have to been made. Arithmetic, seen from 
> inside has an unbounded difficulty: it is beyond the whole of mathematics, 
> somehow.
> 
> 
> 
>> A Hilbert space may have an infinite number of states, but that does not 
>> mean we expect to measure a quantum state with N → ∞.
> 
> I agree. Yet, with mechanism, somehow we must do “infinite calculation” to 
> get the measure right “here and now”, and in sting theory, we might need 
> infinite sum being regulated by analytical complex object (like Ramanujan’s 
> sum of all integers), but that does not go beyond arithmetic, when we look at 
> this more closely.
> Now, I am studying and teaching the table of Laver, born in ZF + high 
> cardinal assumption, and amazingly, there are still purely finite 
> combinatorial problems which we are unable to solve without using some high 
> cardinal, and nothing prevented this to be necessary. For some such problem, 
> some case of need of high infinities can be shown, like with the Goodstein 
> sequences, or with some principle in descriptive set theory.
> 
> Now, in (serious) theology, we can expect more easily those higher infinities 
> to p^lay a role, even in machine theology. If a machine can think, a machine 
> can think about Laver Cardinals!
> 
> Bruno
> 
> 
> 
>> 
>> LC
>> 
>>  
>> 
>>> 
>>> LC
>>> 
>>> On Tuesday, March 17, 2020 at 4:41:09 AM UTC-5, Philip Thrift wrote:
>>> 
>>> Towards a Church-Turing-Thesis for Infinitary Computations
>>> https://arxiv.org/abs/1307.6599 <https://arxiv.org/abs/1307.6599>
>>> Merlin Carl
>>> 
>>> We consider the question whether there is an infinitary analogue of the 
>>> Church-Turing-thesis. To this end, we argue that there is an intuitive 
>>> notion of transfinite computability and build a canonical model, called 
>>> Idealized Agent Machines (IAMs) of this which will turn out to be 
>>> equivalent in strength to the Ordinal Turing Machines defined by P. Koepke.
>>> 
>>> Infinite computations with random oracles
>>> https://arxiv.org/abs/1307.0160 <https://arxiv.org/abs/1307.0160>
>>> 
>>> Effectivity and Reducibility with Ordinal Turing Machines
>>> https://arxiv.org/abs/1811.11630 <https://arxiv.org/abs/1811.11630>
>>> 
>>> Ordinal Computability: An Introduction to Infinitary Machines
>>> https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ
>>>  
>>> <https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ>
>>> 
>>> @philipthrift
>>> 
>>> -- 
>>> You received this message because you are subscribed to the Google Groups 
>>> "Everything List" group.
>>> To unsubscribe from this gr

Re: A Church-Turing-Thesis for Infinitary Computations

[Bruno Marchal]

> On 19 Mar 2020, at 20:05, Philip Thrift  wrote:
> 
> 
> 
> On Thursday, March 19, 2020 at 9:34:36 AM UTC-5, Bruno Marchal wrote:
> 
>> On 18 Mar 2020, at 11:38, Philip Thrift > 
>> wrote:
>> 
>> 
>> 
>> It is a contradiction for a physicist to say, literally,
>> 
>>  nothing real is infinite
>> 
>> http://backreaction.blogspot.com/2020/03/unpredictability-undecidability-and.html
>>  
>> 
>> 
>> yet their physics extensively uses infinitary mathematics
>> 
>> https://physics.stackexchange.com/questions/149786/why-do-we-need-infinite-dimensional-hilbert-spaces-in-physics
>>  
>> 
>> 
>> (To be consistent: All theoretical physics should be based on discrete, 
>> finite mathematics. with no violations permitted. That, or the premise 
>> itself should be voided.)
> 
> 
> The problem is that any finite mathematics, rich enough to define what it is 
> a computer, will have a extremely complex semantics, full of infinities.
> 
> Before Gödel, we though we could protect the use of the infinities by 
> handling their finite descriptions only.
> After Gödel, we know that we cannot even protect the finitely realm by 
> itself, and that we have to use infinities to manage even very partial 
> “protection”.
> 
> We can no more separate the finite from the infinite. In fact, we cannot even 
> really get a precise (first-order) analysis of what finite means, even by 
> using strong powerful theory like ZFC. Some same object can be finite in a 
> model, and infinite in another model.
> 
> What we can do, and what I have done with Mechanism, is to limite the 
> ontology on the finite things, in their intuitive usual sense, and put all 
> the infinities (including the physical) in the phenomenologies associated 
> with the observers.
> 
> Bruno
> 
> 
> 
> From the P-L-T-O-S (program-language-translator-object-semantics) framework, 
> the only models are only those that exist in the universe - the 
> physical-material universe, or PMU, to use the vernacular of the science 
> types. 

If you *assume* a primitive physical universe, then you have to abandon the 
digital mechanist thesis. (That is the first half of my contribution, and if 
you have not grasp this I can explain).
No ontological commitment can select a computation, as seen from the first 
person perspective, and make it more real than those emulated in the 
arithmetical reality, because this would provide a non Turing emulable role of 
that physical reality with respect to the mind/consciousness.
Also, my goal is to explain matter, or its conscious appearrances, so I prefer 
to be neutral on this at the start.



> 
> So whatever can be mapped to some subset of the PMU are the only models there 
> can be.
> 
> Now it is possible that 
> 
> a computer operating in a Malament–Hogarth spacetime or in orbit around a 
> rotating black hole could theoretically perform non-Turing computations for 
> an observer inside the black hole

In principle, but quantum mechanics makes this quite unlikely to happen.



> 
> if the PMU permits it.
> 
> (Scientific theories are completely irrelevant to whether this phenomenon can 
> happen. If it can't happen, it can't happen.)

?

It can happen with GR. But it cannot happen with QM. Eventually we need a 
theory making QM and GR consistent. We are not there yet, and with mechanism, 
we have to extract it from the relative measure on all computations.


> 
> In any case, statements like there are an infinite number of integers may be 
> false (which would automatically let the air out of the hypercomputation 
> balloon).

Frankly, I don’t see how “there are an infinite number of integers” can be 
false, no matter which metaphysics principle we accept. But this is not 
relevant, as the ontological part of the “theory of everything” does not use 
any infinity axiom, and Robinson arithmetic is consistent with the existence of 
a greatest integer.




> 
> In any case: 
> 
> Mathematics (at least Applied Math, and its twin sister, Computing) have only 
> to do with what one can do, not with what is true.

Theoretical computer science has a lot to do with the things that we, the 
machines, cannot do, indeed, even with what we cannot do despite the use of 
powerful oracle. Recursion theory is the study of the degree of unsolvability, 
and the while truth has something to say for theology and the origin of the 
physical laws.

Bruno




> 
> @philipthrift
> 
> 
> -- 
> 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 view this discussion on the web visit 
> 

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

On Thursday, March 19, 2020 at 7:13:10 PM UTC-5, Lawrence Crowell wrote:
>
>
>
> On Thursday, March 19, 2020 at 9:54:58 AM UTC-5, Bruno Marchal wrote:
>>
>>
>> On 18 Mar 2020, at 14:42, Lawrence Crowell  
>> wrote:
>>
>> On Wednesday, March 18, 2020 at 4:13:36 AM UTC-5, Bruno Marchal wrote:
>>>
>>>
>>> On 17 Mar 2020, at 16:14, Lawrence Crowell  
>>> wrote:
>>>
>>> I pretty seriously doubt these things will enter into physics. 
>>> Computations with Cantor's aleph hierarchy of transfinite numbers seems 
>>> pretty far removed from anything really physical.
>>>
>>>
>>>
>>> OK. It is just abstract recursion theory, has been with Turing, and it 
>>> concerns divine creatures, and the goal is to show that even those “divine” 
>>> (infinite being) cannot effectively recover the arithmetical truth/reality. 
>>> I doubt too that such machine can be brought to Earth, and they do play 
>>> some role in the internal phenomenology of the “terrestrial machine”, a bit 
>>> like infinite sums can play a role in physics, like the zeta 
>>> renormalisation in superstring theory.
>>> Note that most of those divine (infinite) machine are still obeying to 
>>> the same self-reference logics (G and G*), and would not change much in the 
>>> mathematical derivation of physics from arithmetic. Note also that the 
>>> first person indeterminacy is connected to the machine + random oracle, so 
>>> that the “sigma_1” predicate is really sigma_1 in all oracles, and this 
>>> makes it possible to use some strong set axiom (like “projective 
>>> determinacy”) to assure the existence of the measure, and probably of the 
>>> needed generalisation of Feynman integral in arithmetic. (This needs indeed 
>>> a generalisation of the Church’s thesis, called the hyperarihmetical 
>>> church’s thesis in the classical  textbook by Rogers).
>>>
>>> Bruno
>>>
>>>
>>>
>> When we get into subtleties of ZF set theory we get into the application 
>> of axioms, eg the axiom of replacement, axiom of infinity, axiom of choice 
>> etc, that have a limited bearing on most standard mathematics. 
>>
>>
>>
>> I am not sure why you say this. Most mathematician would say that ZF is 
>> just the usual intuition of sets made precise. Most people understand the 
>> need (and the power) of the infinity axiom, so that we can talk about 
>> infinite set like N, Q, R, C etc., and the functions in between those sets 
>> of numbers, matrices, etc. The axiom of choice is just obvious, and the 
>> fact that it cannot be proved is no more astonishing than the fact that we 
>> cannot prove any axiom of Robinson Arithmetic from any of its other axioms.
>>
>>
>>
> In the field of physics mathematics is regarded as a tool or language. I 
> think that Feynman put it best with his talk about Greek mathematics vs 
> Babylonian mathematics. Greek mathematics with its precise ε - δ 
> theorem-proof system is "hard" in that you know within any system its 
> results are absolute. However, the Babylonians tended to do practical math, 
> what sometimes is called "maths," which has a certain quick utility to it. 
> I tend to have a foot in both camps, though I have to admit more weight is 
> placed on the Babylonian side. For this reason few physicists give much 
> consideration of ZF axiomatic models. I have to admit I generally give 
> these things much consideration.
>
> LC
>  
>


*Opinion 174: The "Greek" (Euclidean, Axiomatic, Deductive. ...) approach 
to mathematics did much more damage than just ruin mathematics, as is clear 
from Amir Alexander's fascinating new Book "Proof!". It is high time that 
we move over to the much more democratic and egalitarian (and far less 
boring!) "Babylonian" (Algorithmic, Inductive, Experimental,...) approach 
to mathematics*

By Doron Zeilberger
Written: Oct. 20, 2019

Way back in the mid 1960s, when I was in ninth grade, we still learned 
Plane Geometry the traditional way, essentially following (a watered-down, 
but methodologically isomorphic) version of Euclid's 2300-year-old 
Elements. This awful text, with its false claims to absolute truth, was 
almost as influential as the bible, and many generations of students shed 
tears trying to "prove" (often intuitively obvious) propositions, by a 
step-by-step "deductive" process. On the other hand, quite a few otherwise 
very smart people (Spinoza, Hobbes, ... ) loved it, and used its 
(apparent!) air of absolute certainty, adapting Euclid's style, to claim 
that their philosophical theses are just as absolutely certain.

But (most) philosophers are basically good guys, and I forgive them. On the 
other hand, absolute monarchs, and other tyrants, are not! What I found out 
from Amir Alexander's fascinating new book Proof! (How the World Became 
Geometrical) was how Euclidean Geometry was abused by them to "prove" their 
inherent superiority. The `canonical example', narrated at length in the 
book, was Louis XIV, who commissioned a very elaborate geometrical garden, 
the famous Jardins du 

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

On Thursday, March 19, 2020 at 6:57:19 PM UTC-5, Lawrence Crowell wrote:
>
> On Thursday, March 19, 2020 at 8:52:30 AM UTC-5, Philip Thrift wrote:
>>
>>
>>
>> On Thursday, March 19, 2020 at 7:46:10 AM UTC-5, Lawrence Crowell wrote:
>>>
>>> On Wednesday, March 18, 2020 at 12:47:56 PM UTC-5, Philip Thrift wrote:



 On Wednesday, March 18, 2020 at 8:42:19 AM UTC-5, Lawrence Crowell 
 wrote:
>
> On Wednesday, March 18, 2020 at 4:13:36 AM UTC-5, Bruno Marchal wrote:
>>
>>
>> On 17 Mar 2020, at 16:14, Lawrence Crowell  
>> wrote:
>>
>> I pretty seriously doubt these things will enter into physics. 
>> Computations with Cantor's aleph hierarchy of transfinite numbers seems 
>> pretty far removed from anything really physical.
>>
>>
>>
>> OK. It is just abstract recursion theory, has been with Turing, and 
>> it concerns divine creatures, and the goal is to show that even those 
>> “divine” (infinite being) cannot effectively recover the arithmetical 
>> truth/reality. I doubt too that such machine can be brought to Earth, 
>> and 
>> they do play some role in the internal phenomenology of the “terrestrial 
>> machine”, a bit like infinite sums can play a role in physics, like the 
>> zeta renormalisation in superstring theory.
>> Note that most of those divine (infinite) machine are still obeying 
>> to the same self-reference logics (G and G*), and would not change much 
>> in 
>> the mathematical derivation of physics from arithmetic. Note also that 
>> the 
>> first person indeterminacy is connected to the machine + random oracle, 
>> so 
>> that the “sigma_1” predicate is really sigma_1 in all oracles, and this 
>> makes it possible to use some strong set axiom (like “projective 
>> determinacy”) to assure the existence of the measure, and probably of 
>> the 
>> needed generalisation of Feynman integral in arithmetic. (This needs 
>> indeed 
>> a generalisation of the Church’s thesis, called the hyperarihmetical 
>> church’s thesis in the classical  textbook by Rogers).
>>
>> Bruno
>>
>>
>>
> When we get into subtleties of ZF set theory we get into the 
> application of axioms, eg the axiom of replacement, axiom of infinity, 
> axiom of choice etc, that have a limited bearing on most standard 
> mathematics. This means physics is even further removed. Transfinite 
> numbers and the question of א_0 ≤ c ≤ 2^א_0 or the continuum hypothesis 
> has 
> a role with Robinson’s numbers. These are in a sense the reciprocals of 
> transfinite numbers or the continuum. This has some bearing in the 
> foundations of calculus, though I am far from familiar with this. I am 
> not 
> sure what possible role this could have for physics.
>
> Infinite mathematical quantities are common in physics. The 2-dim CFT 
> is Virasoro which is a Witt algebra extended to infinite dimensions with 
> a 
> kernel. This does not though mean physics predicts the measurement of 
> infinite quantities  A Hilbert space may have an infinite number of 
> states, 
> but that does not mean we expect to measure a quantum state with N → ∞.
>
> LC
>
>
>

 Permitting entities in its language is a )perhaps the major) problem 
 with the current approach to theoretical physics and which most physicists 
 seem oblivious to. It is a form of double-speak to say there are no 
 infinities but then make theories based on them ... unless they are 
 introduced in a theoretically appropriate manner, which has yet been done. 

 The continuum threatens us with infinities:

 But even if we take a hard-headed practical attitude and leave logic to 
 the
 logicians, our struggles with the continuum are not over. In fact, the 
 infinitely
 divisible nature of the real line—the existence of arbitrarily small 
 real numbers—is a serious challenge to physics.

 We have seen that in every major theory of physics, challenging 
 mathematical
 questions arise from the assumption that spacetime is a continuum. The 
 continuum threatens us with infinities. Do these infinities threaten our 
 ability to
 extract predictions from these theories—or even our ability to 
 formulate these
 theories in a precise way? We can answer these questions, but only with 
 hard
 work. Is this a sign that we are somehow on the wrong track? Is the 
 continuum as we understand it only an approximation to some deeper model 
 of 
 spacetime?

 Only time will tell. Nature is providing us with plenty of clues, but 
 it will take
 patience to read them correctly.

 *Struggles with the Continuum*
 John C. Baez
 https://arxiv.org/abs/1609.01421v4
 

Re: A Church-Turing-Thesis for Infinitary Computations

[Lawrence Crowell]

own. Note that category theory has also 
> provided “synthetic differential calculus”, which are non standard, but 
> have some appeal in algebraic geometry. 
>
>
>
>
> Infinite mathematical quantities are common in physics. The 2-dim CFT is 
> Virasoro which is a Witt algebra extended to infinite dimensions with a 
> kernel. This does not though mean physics predicts the measurement of 
> infinite quantities 
>
>
> Indeed. In physics, the mathematics is neutral, and its infinities can be 
> put on the phenomenological side. But with mechanism, there remain some 
> realism about the phenomenology, and choice have to been made. Arithmetic, 
> seen from inside has an unbounded difficulty: it is beyond the whole of 
> mathematics, somehow.
>
>
>
> A Hilbert space may have an infinite number of states, but that does not 
> mean we expect to measure a quantum state with N → ∞.
>
>
> I agree. Yet, with mechanism, somehow we must do “infinite calculation” to 
> get the measure right “here and now”, and in sting theory, we might need 
> infinite sum being regulated by analytical complex object (like Ramanujan’s 
> sum of all integers), but that does not go beyond arithmetic, when we look 
> at this more closely.
> Now, I am studying and teaching the table of Laver, born in ZF + high 
> cardinal assumption, and amazingly, there are still purely finite 
> combinatorial problems which we are unable to solve without using some high 
> cardinal, and nothing prevented this to be necessary. For some such 
> problem, some case of need of high infinities can be shown, like with the 
> Goodstein sequences, or with some principle in descriptive set theory.
>
> Now, in (serious) theology, we can expect more easily those higher 
> infinities to p^lay a role, even in machine theology. If a machine can 
> think, a machine can think about Laver Cardinals!
>
> Bruno
>
>
>
>
> LC
>
>  
>
>>
>>
>> LC
>>
>> On Tuesday, March 17, 2020 at 4:41:09 AM UTC-5, Philip Thrift wrote:
>>>
>>>
>>> *Towards a Church-Turing-Thesis for Infinitary Computations*
>>> https://arxiv.org/abs/1307.6599
>>> Merlin Carl
>>>
>>> *We consider the question whether there is an infinitary analogue of the 
>>> Church-Turing-thesis. To this end, we argue that there is an intuitive 
>>> notion of transfinite computability and build a canonical model, called 
>>> Idealized Agent Machines (IAMs) of this which will turn out to be 
>>> equivalent in strength to the Ordinal Turing Machines defined by P. Koepke.*
>>>
>>> *Infinite computations with random oracles*
>>> https://arxiv.org/abs/1307.0160
>>>
>>> *Effectivity and Reducibility with Ordinal Turing Machines*
>>> https://arxiv.org/abs/1811.11630
>>>
>>> *Ordinal Computability: An Introduction to Infinitary Machines*
>>>
>>> https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ
>>>
>>> @philipthrift
>>>
>>
>> -- 
>> 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 everyth...@googlegroups.com.
>> To view this discussion on the web visit 
>> https://groups.google.com/d/msgid/everything-list/d9532c24-0130-4733-9ffe-154b335103d9%40googlegroups.com
>>  
>> <https://groups.google.com/d/msgid/everything-list/d9532c24-0130-4733-9ffe-154b335103d9%40googlegroups.com?utm_medium=email_source=footer>
>> .
>>
>>
>>
> -- 
> 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 everyth...@googlegroups.com .
> To view this discussion on the web visit 
> https://groups.google.com/d/msgid/everything-list/9cfe048d-2088-4c55-8304-517c0fc5658f%40googlegroups.com
>  
> <https://groups.google.com/d/msgid/everything-list/9cfe048d-2088-4c55-8304-517c0fc5658f%40googlegroups.com?utm_medium=email_source=footer>
> .
>
>
>

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/f9547ebf-9dff-4e3e-b5ba-876629874330%40googlegroups.com.

Re: A Church-Turing-Thesis for Infinitary Computations

[Lawrence Crowell]

On Thursday, March 19, 2020 at 8:52:30 AM UTC-5, Philip Thrift wrote:
>
>
>
> On Thursday, March 19, 2020 at 7:46:10 AM UTC-5, Lawrence Crowell wrote:
>>
>> On Wednesday, March 18, 2020 at 12:47:56 PM UTC-5, Philip Thrift wrote:
>>>
>>>
>>>
>>> On Wednesday, March 18, 2020 at 8:42:19 AM UTC-5, Lawrence Crowell wrote:

 On Wednesday, March 18, 2020 at 4:13:36 AM UTC-5, Bruno Marchal wrote:
>
>
> On 17 Mar 2020, at 16:14, Lawrence Crowell  
> wrote:
>
> I pretty seriously doubt these things will enter into physics. 
> Computations with Cantor's aleph hierarchy of transfinite numbers seems 
> pretty far removed from anything really physical.
>
>
>
> OK. It is just abstract recursion theory, has been with Turing, and it 
> concerns divine creatures, and the goal is to show that even those 
> “divine” 
> (infinite being) cannot effectively recover the arithmetical 
> truth/reality. 
> I doubt too that such machine can be brought to Earth, and they do play 
> some role in the internal phenomenology of the “terrestrial machine”, a 
> bit 
> like infinite sums can play a role in physics, like the zeta 
> renormalisation in superstring theory.
> Note that most of those divine (infinite) machine are still obeying to 
> the same self-reference logics (G and G*), and would not change much in 
> the 
> mathematical derivation of physics from arithmetic. Note also that the 
> first person indeterminacy is connected to the machine + random oracle, 
> so 
> that the “sigma_1” predicate is really sigma_1 in all oracles, and this 
> makes it possible to use some strong set axiom (like “projective 
> determinacy”) to assure the existence of the measure, and probably of the 
> needed generalisation of Feynman integral in arithmetic. (This needs 
> indeed 
> a generalisation of the Church’s thesis, called the hyperarihmetical 
> church’s thesis in the classical  textbook by Rogers).
>
> Bruno
>
>
>
 When we get into subtleties of ZF set theory we get into the 
 application of axioms, eg the axiom of replacement, axiom of infinity, 
 axiom of choice etc, that have a limited bearing on most standard 
 mathematics. This means physics is even further removed. Transfinite 
 numbers and the question of א_0 ≤ c ≤ 2^א_0 or the continuum hypothesis 
 has 
 a role with Robinson’s numbers. These are in a sense the reciprocals of 
 transfinite numbers or the continuum. This has some bearing in the 
 foundations of calculus, though I am far from familiar with this. I am not 
 sure what possible role this could have for physics.

 Infinite mathematical quantities are common in physics. The 2-dim CFT 
 is Virasoro which is a Witt algebra extended to infinite dimensions with a 
 kernel. This does not though mean physics predicts the measurement of 
 infinite quantities  A Hilbert space may have an infinite number of 
 states, 
 but that does not mean we expect to measure a quantum state with N → ∞.

 LC



>>>
>>> Permitting entities in its language is a )perhaps the major) problem 
>>> with the current approach to theoretical physics and which most physicists 
>>> seem oblivious to. It is a form of double-speak to say there are no 
>>> infinities but then make theories based on them ... unless they are 
>>> introduced in a theoretically appropriate manner, which has yet been done. 
>>>
>>> The continuum threatens us with infinities:
>>>
>>> But even if we take a hard-headed practical attitude and leave logic to 
>>> the
>>> logicians, our struggles with the continuum are not over. In fact, the 
>>> infinitely
>>> divisible nature of the real line—the existence of arbitrarily small 
>>> real numbers—is a serious challenge to physics.
>>>
>>> We have seen that in every major theory of physics, challenging 
>>> mathematical
>>> questions arise from the assumption that spacetime is a continuum. The 
>>> continuum threatens us with infinities. Do these infinities threaten our 
>>> ability to
>>> extract predictions from these theories—or even our ability to formulate 
>>> these
>>> theories in a precise way? We can answer these questions, but only with 
>>> hard
>>> work. Is this a sign that we are somehow on the wrong track? Is the 
>>> continuum as we understand it only an approximation to some deeper model of 
>>> spacetime?
>>>
>>> Only time will tell. Nature is providing us with plenty of clues, but it 
>>> will take
>>> patience to read them correctly.
>>>
>>> *Struggles with the Continuum*
>>> John C. Baez
>>> https://arxiv.org/abs/1609.01421v4
>>> https://arxiv.org/pdf/1609.01421v4.pdf
>>>
>>>
>>> @philipthrift
>>>
>>
>> In a funny way quantum mechanics may rescue this situation. The Fermi and 
>> Integral spacecraft measurements of EM radiation from distant burstars 
>> indicates spacetime 

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

On Thursday, March 19, 2020 at 9:34:36 AM UTC-5, Bruno Marchal wrote:
>
>
> On 18 Mar 2020, at 11:38, Philip Thrift > 
> wrote:
>
>
>
> It is a contradiction for a physicist to say, literally,
>
>  *nothing real is infinite*
>
>
> http://backreaction.blogspot.com/2020/03/unpredictability-undecidability-and.html
>
> yet their physics extensively uses infinitary mathematics
>
>
> https://physics.stackexchange.com/questions/149786/why-do-we-need-infinite-dimensional-hilbert-spaces-in-physics
>
> (To be consistent: All theoretical physics should be based on *discrete, 
> finite mathematics*. with *no violations permitted*. That, or the premise 
> itself should be voided.)
>
>
>
> The problem is that any finite mathematics, rich enough to define what it 
> is a computer, will have a extremely complex semantics, full of infinities.
>
> Before Gödel, we though we could protect the use of the infinities by 
> handling their finite descriptions only.
> After Gödel, we know that we cannot even protect the finitely realm by 
> itself, and that we have to use infinities to manage even very partial 
> “protection”.
>
> We can no more separate the finite from the infinite. In fact, we cannot 
> even really get a precise (first-order) analysis of what finite means, even 
> by using strong powerful theory like ZFC. Some same object can be finite in 
> a model, and infinite in another model.
>
> What we can do, and what I have done with Mechanism, is to limite the 
> ontology on the finite things, in their intuitive usual sense, and put all 
> the infinities (including the physical) in the phenomenologies associated 
> with the observers.
>
> Bruno
>
>
>
>From the *P-L-T-O-S (program-language-translator-object-semantics) *framework, 
the only models are only those that exist in the universe - the 
physical-material universe, or PMU, to use the vernacular of the science 
types. 

So whatever can be mapped to some subset of the PMU are the only models 
there can be.

Now it is possible that 

*a computer operating in a Malament–Hogarth spacetime or in orbit around a 
rotating black hole could theoretically perform non-Turing computations for 
an observer inside the black hole*

if the PMU permits it.

(Scientific theories are completely irrelevant to whether this phenomenon 
can happen. If it can't happen, it can't happen.)

In any case, statements like* there are an infinite number of integers* may 
be false (which would automatically let the air out of the hypercomputation 
balloon).

In any case: 

*Mathematics (at least Applied Math, and its twin sister, Computing) have 
only to do with what one can do, not with what is true.*

@philipthrift

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/731b79fa-2709-4180-96d4-ea9156e9976f%40googlegroups.com.

Re: A Church-Turing-Thesis for Infinitary Computations

[Bruno Marchal]

 of all 
integers), but that does not go beyond arithmetic, when we look at this more 
closely.
Now, I am studying and teaching the table of Laver, born in ZF + high cardinal 
assumption, and amazingly, there are still purely finite combinatorial problems 
which we are unable to solve without using some high cardinal, and nothing 
prevented this to be necessary. For some such problem, some case of need of 
high infinities can be shown, like with the Goodstein sequences, or with some 
principle in descriptive set theory.

Now, in (serious) theology, we can expect more easily those higher infinities 
to p^lay a role, even in machine theology. If a machine can think, a machine 
can think about Laver Cardinals!

Bruno



> 
> LC
> 
>  
> 
>> 
>> LC
>> 
>> On Tuesday, March 17, 2020 at 4:41:09 AM UTC-5, Philip Thrift wrote:
>> 
>> Towards a Church-Turing-Thesis for Infinitary Computations
>> https://arxiv.org/abs/1307.6599 <https://arxiv.org/abs/1307.6599>
>> Merlin Carl
>> 
>> We consider the question whether there is an infinitary analogue of the 
>> Church-Turing-thesis. To this end, we argue that there is an intuitive 
>> notion of transfinite computability and build a canonical model, called 
>> Idealized Agent Machines (IAMs) of this which will turn out to be equivalent 
>> in strength to the Ordinal Turing Machines defined by P. Koepke.
>> 
>> Infinite computations with random oracles
>> https://arxiv.org/abs/1307.0160 <https://arxiv.org/abs/1307.0160>
>> 
>> Effectivity and Reducibility with Ordinal Turing Machines
>> https://arxiv.org/abs/1811.11630 <https://arxiv.org/abs/1811.11630>
>> 
>> Ordinal Computability: An Introduction to Infinitary Machines
>> https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ
>>  
>> <https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ>
>> 
>> @philipthrift
>> 
>> -- 
>> 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 everyth...@googlegroups.com .
>> To view this discussion on the web visit 
>> https://groups.google.com/d/msgid/everything-list/d9532c24-0130-4733-9ffe-154b335103d9%40googlegroups.com
>>  
>> <https://groups.google.com/d/msgid/everything-list/d9532c24-0130-4733-9ffe-154b335103d9%40googlegroups.com?utm_medium=email_source=footer>.
> 
> 
> -- 
> 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 view this discussion on the web visit 
> https://groups.google.com/d/msgid/everything-list/9cfe048d-2088-4c55-8304-517c0fc5658f%40googlegroups.com
>  
> <https://groups.google.com/d/msgid/everything-list/9cfe048d-2088-4c55-8304-517c0fc5658f%40googlegroups.com?utm_medium=email_source=footer>.

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/C4EDF8D3-8F9E-4E5D-8147-89FA8C2FBF28%40ulb.ac.be.

Re: A Church-Turing-Thesis for Infinitary Computations

[Bruno Marchal]

> On 18 Mar 2020, at 11:38, Philip Thrift  wrote:
> 
> 
> 
> It is a contradiction for a physicist to say, literally,
> 
>  nothing real is infinite
> 
> http://backreaction.blogspot.com/2020/03/unpredictability-undecidability-and.html
>  
> <http://backreaction.blogspot.com/2020/03/unpredictability-undecidability-and.html>
> 
> yet their physics extensively uses infinitary mathematics
> 
> https://physics.stackexchange.com/questions/149786/why-do-we-need-infinite-dimensional-hilbert-spaces-in-physics
>  
> <https://physics.stackexchange.com/questions/149786/why-do-we-need-infinite-dimensional-hilbert-spaces-in-physics>
> 
> (To be consistent: All theoretical physics should be based on discrete, 
> finite mathematics. with no violations permitted. That, or the premise itself 
> should be voided.)


The problem is that any finite mathematics, rich enough to define what it is a 
computer, will have a extremely complex semantics, full of infinities.

Before Gödel, we though we could protect the use of the infinities by handling 
their finite descriptions only.
After Gödel, we know that we cannot even protect the finitely realm by itself, 
and that we have to use infinities to manage even very partial “protection”.

We can no more separate the finite from the infinite. In fact, we cannot even 
really get a precise (first-order) analysis of what finite means, even by using 
strong powerful theory like ZFC. Some same object can be finite in a model, and 
infinite in another model.

What we can do, and what I have done with Mechanism, is to limite the ontology 
on the finite things, in their intuitive usual sense, and put all the 
infinities (including the physical) in the phenomenologies associated with the 
observers.

Bruno






> 
> It's like one hand does not know what the other hand is doing.
> 
> @philipthrift
> 
> 
> On Tuesday, March 17, 2020 at 10:14:28 AM UTC-5, Lawrence Crowell wrote:
> I pretty seriously doubt these things will enter into physics. Computations 
> with Cantor's aleph hierarchy of transfinite numbers seems pretty far removed 
> from anything really physical.
> 
> LC
> 
> On Tuesday, March 17, 2020 at 4:41:09 AM UTC-5, Philip Thrift wrote:
> 
> Towards a Church-Turing-Thesis for Infinitary Computations
> https://arxiv.org/abs/1307.6599 <https://arxiv.org/abs/1307.6599>
> Merlin Carl
> 
> We consider the question whether there is an infinitary analogue of the 
> Church-Turing-thesis. To this end, we argue that there is an intuitive notion 
> of transfinite computability and build a canonical model, called Idealized 
> Agent Machines (IAMs) of this which will turn out to be equivalent in 
> strength to the Ordinal Turing Machines defined by P. Koepke.
> 
> Infinite computations with random oracles
> https://arxiv.org/abs/1307.0160 <https://arxiv.org/abs/1307.0160>
> 
> Effectivity and Reducibility with Ordinal Turing Machines
> https://arxiv.org/abs/1811.11630 <https://arxiv.org/abs/1811.11630>
> 
> Ordinal Computability: An Introduction to Infinitary Machines
> https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ
>  
> <https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ>
> 
> @philipthrift
> 
> -- 
> 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 view this discussion on the web visit 
> https://groups.google.com/d/msgid/everything-list/50935dcd-1921-494c-ab2a-1a151d1fb17b%40googlegroups.com
>  
> <https://groups.google.com/d/msgid/everything-list/50935dcd-1921-494c-ab2a-1a151d1fb17b%40googlegroups.com?utm_medium=email_source=footer>.

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/605C7091-A23E-4F6C-B7E7-ACF0848895B6%40ulb.ac.be.

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

On Thursday, March 19, 2020 at 8:52:30 AM UTC-5, Philip Thrift wrote:
>
>
>
> On Thursday, March 19, 2020 at 7:46:10 AM UTC-5, Lawrence Crowell wrote:
>>
>> On Wednesday, March 18, 2020 at 12:47:56 PM UTC-5, Philip Thrift wrote:
>>>
>>>
>>>
>>> On Wednesday, March 18, 2020 at 8:42:19 AM UTC-5, Lawrence Crowell wrote:

 On Wednesday, March 18, 2020 at 4:13:36 AM UTC-5, Bruno Marchal wrote:
>
>
> On 17 Mar 2020, at 16:14, Lawrence Crowell  
> wrote:
>
> I pretty seriously doubt these things will enter into physics. 
> Computations with Cantor's aleph hierarchy of transfinite numbers seems 
> pretty far removed from anything really physical.
>
>
>
> OK. It is just abstract recursion theory, has been with Turing, and it 
> concerns divine creatures, and the goal is to show that even those 
> “divine” 
> (infinite being) cannot effectively recover the arithmetical 
> truth/reality. 
> I doubt too that such machine can be brought to Earth, and they do play 
> some role in the internal phenomenology of the “terrestrial machine”, a 
> bit 
> like infinite sums can play a role in physics, like the zeta 
> renormalisation in superstring theory.
> Note that most of those divine (infinite) machine are still obeying to 
> the same self-reference logics (G and G*), and would not change much in 
> the 
> mathematical derivation of physics from arithmetic. Note also that the 
> first person indeterminacy is connected to the machine + random oracle, 
> so 
> that the “sigma_1” predicate is really sigma_1 in all oracles, and this 
> makes it possible to use some strong set axiom (like “projective 
> determinacy”) to assure the existence of the measure, and probably of the 
> needed generalisation of Feynman integral in arithmetic. (This needs 
> indeed 
> a generalisation of the Church’s thesis, called the hyperarihmetical 
> church’s thesis in the classical  textbook by Rogers).
>
> Bruno
>
>
>
 When we get into subtleties of ZF set theory we get into the 
 application of axioms, eg the axiom of replacement, axiom of infinity, 
 axiom of choice etc, that have a limited bearing on most standard 
 mathematics. This means physics is even further removed. Transfinite 
 numbers and the question of א_0 ≤ c ≤ 2^א_0 or the continuum hypothesis 
 has 
 a role with Robinson’s numbers. These are in a sense the reciprocals of 
 transfinite numbers or the continuum. This has some bearing in the 
 foundations of calculus, though I am far from familiar with this. I am not 
 sure what possible role this could have for physics.

 Infinite mathematical quantities are common in physics. The 2-dim CFT 
 is Virasoro which is a Witt algebra extended to infinite dimensions with a 
 kernel. This does not though mean physics predicts the measurement of 
 infinite quantities  A Hilbert space may have an infinite number of 
 states, 
 but that does not mean we expect to measure a quantum state with N → ∞.

 LC



>>>
>>> Permitting entities in its language is a )perhaps the major) problem 
>>> with the current approach to theoretical physics and which most physicists 
>>> seem oblivious to. It is a form of double-speak to say there are no 
>>> infinities but then make theories based on them ... unless they are 
>>> introduced in a theoretically appropriate manner, which has yet been done. 
>>>
>>> The continuum threatens us with infinities:
>>>
>>> But even if we take a hard-headed practical attitude and leave logic to 
>>> the
>>> logicians, our struggles with the continuum are not over. In fact, the 
>>> infinitely
>>> divisible nature of the real line—the existence of arbitrarily small 
>>> real numbers—is a serious challenge to physics.
>>>
>>> We have seen that in every major theory of physics, challenging 
>>> mathematical
>>> questions arise from the assumption that spacetime is a continuum. The 
>>> continuum threatens us with infinities. Do these infinities threaten our 
>>> ability to
>>> extract predictions from these theories—or even our ability to formulate 
>>> these
>>> theories in a precise way? We can answer these questions, but only with 
>>> hard
>>> work. Is this a sign that we are somehow on the wrong track? Is the 
>>> continuum as we understand it only an approximation to some deeper model of 
>>> spacetime?
>>>
>>> Only time will tell. Nature is providing us with plenty of clues, but it 
>>> will take
>>> patience to read them correctly.
>>>
>>> *Struggles with the Continuum*
>>> John C. Baez
>>> https://arxiv.org/abs/1609.01421v4
>>> https://arxiv.org/pdf/1609.01421v4.pdf
>>>
>>>
>>> @philipthrift
>>>
>>
>> In a funny way quantum mechanics may rescue this situation. The Fermi and 
>> Integral spacecraft measurements of EM radiation from distant burstars 
>> indicates 

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

On Thursday, March 19, 2020 at 7:46:10 AM UTC-5, Lawrence Crowell wrote:
>
> On Wednesday, March 18, 2020 at 12:47:56 PM UTC-5, Philip Thrift wrote:
>>
>>
>>
>> On Wednesday, March 18, 2020 at 8:42:19 AM UTC-5, Lawrence Crowell wrote:
>>>
>>> On Wednesday, March 18, 2020 at 4:13:36 AM UTC-5, Bruno Marchal wrote:


 On 17 Mar 2020, at 16:14, Lawrence Crowell  
 wrote:

 I pretty seriously doubt these things will enter into physics. 
 Computations with Cantor's aleph hierarchy of transfinite numbers seems 
 pretty far removed from anything really physical.



 OK. It is just abstract recursion theory, has been with Turing, and it 
 concerns divine creatures, and the goal is to show that even those 
 “divine” 
 (infinite being) cannot effectively recover the arithmetical 
 truth/reality. 
 I doubt too that such machine can be brought to Earth, and they do play 
 some role in the internal phenomenology of the “terrestrial machine”, a 
 bit 
 like infinite sums can play a role in physics, like the zeta 
 renormalisation in superstring theory.
 Note that most of those divine (infinite) machine are still obeying to 
 the same self-reference logics (G and G*), and would not change much in 
 the 
 mathematical derivation of physics from arithmetic. Note also that the 
 first person indeterminacy is connected to the machine + random oracle, so 
 that the “sigma_1” predicate is really sigma_1 in all oracles, and this 
 makes it possible to use some strong set axiom (like “projective 
 determinacy”) to assure the existence of the measure, and probably of the 
 needed generalisation of Feynman integral in arithmetic. (This needs 
 indeed 
 a generalisation of the Church’s thesis, called the hyperarihmetical 
 church’s thesis in the classical  textbook by Rogers).

 Bruno



>>> When we get into subtleties of ZF set theory we get into the application 
>>> of axioms, eg the axiom of replacement, axiom of infinity, axiom of choice 
>>> etc, that have a limited bearing on most standard mathematics. This means 
>>> physics is even further removed. Transfinite numbers and the question of 
>>> א_0 ≤ c ≤ 2^א_0 or the continuum hypothesis has a role with Robinson’s 
>>> numbers. These are in a sense the reciprocals of transfinite numbers or the 
>>> continuum. This has some bearing in the foundations of calculus, though I 
>>> am far from familiar with this. I am not sure what possible role this could 
>>> have for physics.
>>>
>>> Infinite mathematical quantities are common in physics. The 2-dim CFT is 
>>> Virasoro which is a Witt algebra extended to infinite dimensions with a 
>>> kernel. This does not though mean physics predicts the measurement of 
>>> infinite quantities  A Hilbert space may have an infinite number of states, 
>>> but that does not mean we expect to measure a quantum state with N → ∞.
>>>
>>> LC
>>>
>>>
>>>
>>
>> Permitting entities in its language is a )perhaps the major) problem with 
>> the current approach to theoretical physics and which most physicists seem 
>> oblivious to. It is a form of double-speak to say there are no infinities 
>> but then make theories based on them ... unless they are introduced in a 
>> theoretically appropriate manner, which has yet been done. 
>>
>> The continuum threatens us with infinities:
>>
>> But even if we take a hard-headed practical attitude and leave logic to 
>> the
>> logicians, our struggles with the continuum are not over. In fact, the 
>> infinitely
>> divisible nature of the real line—the existence of arbitrarily small real 
>> numbers—is a serious challenge to physics.
>>
>> We have seen that in every major theory of physics, challenging 
>> mathematical
>> questions arise from the assumption that spacetime is a continuum. The 
>> continuum threatens us with infinities. Do these infinities threaten our 
>> ability to
>> extract predictions from these theories—or even our ability to formulate 
>> these
>> theories in a precise way? We can answer these questions, but only with 
>> hard
>> work. Is this a sign that we are somehow on the wrong track? Is the 
>> continuum as we understand it only an approximation to some deeper model of 
>> spacetime?
>>
>> Only time will tell. Nature is providing us with plenty of clues, but it 
>> will take
>> patience to read them correctly.
>>
>> *Struggles with the Continuum*
>> John C. Baez
>> https://arxiv.org/abs/1609.01421v4
>> https://arxiv.org/pdf/1609.01421v4.pdf
>>
>>
>> @philipthrift
>>
>
> In a funny way quantum mechanics may rescue this situation. The Fermi and 
> Integral spacecraft measurements of EM radiation from distant burstars 
> indicates spacetime is smooth down to 50 times smaller than the Planck 
> length.  This suggests space or spacetime is smooth "all the way down" in a 
> calculus ε - δ sense. This would appear to lead directly into questions 

Re: A Church-Turing-Thesis for Infinitary Computations

[Lawrence Crowell]

On Wednesday, March 18, 2020 at 12:47:56 PM UTC-5, Philip Thrift wrote:
>
>
>
> On Wednesday, March 18, 2020 at 8:42:19 AM UTC-5, Lawrence Crowell wrote:
>>
>> On Wednesday, March 18, 2020 at 4:13:36 AM UTC-5, Bruno Marchal wrote:
>>>
>>>
>>> On 17 Mar 2020, at 16:14, Lawrence Crowell  
>>> wrote:
>>>
>>> I pretty seriously doubt these things will enter into physics. 
>>> Computations with Cantor's aleph hierarchy of transfinite numbers seems 
>>> pretty far removed from anything really physical.
>>>
>>>
>>>
>>> OK. It is just abstract recursion theory, has been with Turing, and it 
>>> concerns divine creatures, and the goal is to show that even those “divine” 
>>> (infinite being) cannot effectively recover the arithmetical truth/reality. 
>>> I doubt too that such machine can be brought to Earth, and they do play 
>>> some role in the internal phenomenology of the “terrestrial machine”, a bit 
>>> like infinite sums can play a role in physics, like the zeta 
>>> renormalisation in superstring theory.
>>> Note that most of those divine (infinite) machine are still obeying to 
>>> the same self-reference logics (G and G*), and would not change much in the 
>>> mathematical derivation of physics from arithmetic. Note also that the 
>>> first person indeterminacy is connected to the machine + random oracle, so 
>>> that the “sigma_1” predicate is really sigma_1 in all oracles, and this 
>>> makes it possible to use some strong set axiom (like “projective 
>>> determinacy”) to assure the existence of the measure, and probably of the 
>>> needed generalisation of Feynman integral in arithmetic. (This needs indeed 
>>> a generalisation of the Church’s thesis, called the hyperarihmetical 
>>> church’s thesis in the classical  textbook by Rogers).
>>>
>>> Bruno
>>>
>>>
>>>
>> When we get into subtleties of ZF set theory we get into the application 
>> of axioms, eg the axiom of replacement, axiom of infinity, axiom of choice 
>> etc, that have a limited bearing on most standard mathematics. This means 
>> physics is even further removed. Transfinite numbers and the question of 
>> א_0 ≤ c ≤ 2^א_0 or the continuum hypothesis has a role with Robinson’s 
>> numbers. These are in a sense the reciprocals of transfinite numbers or the 
>> continuum. This has some bearing in the foundations of calculus, though I 
>> am far from familiar with this. I am not sure what possible role this could 
>> have for physics.
>>
>> Infinite mathematical quantities are common in physics. The 2-dim CFT is 
>> Virasoro which is a Witt algebra extended to infinite dimensions with a 
>> kernel. This does not though mean physics predicts the measurement of 
>> infinite quantities  A Hilbert space may have an infinite number of states, 
>> but that does not mean we expect to measure a quantum state with N → ∞.
>>
>> LC
>>
>>
>>
>
> Permitting entities in its language is a )perhaps the major) problem with 
> the current approach to theoretical physics and which most physicists seem 
> oblivious to. It is a form of double-speak to say there are no infinities 
> but then make theories based on them ... unless they are introduced in a 
> theoretically appropriate manner, which has yet been done. 
>
> The continuum threatens us with infinities:
>
> But even if we take a hard-headed practical attitude and leave logic to the
> logicians, our struggles with the continuum are not over. In fact, the 
> infinitely
> divisible nature of the real line—the existence of arbitrarily small real 
> numbers—is a serious challenge to physics.
>
> We have seen that in every major theory of physics, challenging 
> mathematical
> questions arise from the assumption that spacetime is a continuum. The 
> continuum threatens us with infinities. Do these infinities threaten our 
> ability to
> extract predictions from these theories—or even our ability to formulate 
> these
> theories in a precise way? We can answer these questions, but only with 
> hard
> work. Is this a sign that we are somehow on the wrong track? Is the 
> continuum as we understand it only an approximation to some deeper model of 
> spacetime?
>
> Only time will tell. Nature is providing us with plenty of clues, but it 
> will take
> patience to read them correctly.
>
> *Struggles with the Continuum*
> John C. Baez
> https://arxiv.org/abs/1609.01421v4
> https://arxiv.org/pdf/1609.01421v4.pdf
>
>
> @philipthrift
>

In a funny way quantum mechanics may rescue this situation. The Fermi and 
Integral spacecraft measurements of EM radiation from distant burstars 
indicates spacetime is smooth down to 50 times smaller than the Planck 
length.  This suggests space or spacetime is smooth "all the way down" in a 
calculus ε - δ sense. This would appear to lead directly into questions on 
how it is that an uncountable infinite number of entities might enter into 
physics. Of course in these measurements there was no Heisenberg microscope 
looking in on space. Further, space and spacetime are likely an 

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

On Wednesday, March 18, 2020 at 8:42:19 AM UTC-5, Lawrence Crowell wrote:
>
> On Wednesday, March 18, 2020 at 4:13:36 AM UTC-5, Bruno Marchal wrote:
>>
>>
>> On 17 Mar 2020, at 16:14, Lawrence Crowell  
>> wrote:
>>
>> I pretty seriously doubt these things will enter into physics. 
>> Computations with Cantor's aleph hierarchy of transfinite numbers seems 
>> pretty far removed from anything really physical.
>>
>>
>>
>> OK. It is just abstract recursion theory, has been with Turing, and it 
>> concerns divine creatures, and the goal is to show that even those “divine” 
>> (infinite being) cannot effectively recover the arithmetical truth/reality. 
>> I doubt too that such machine can be brought to Earth, and they do play 
>> some role in the internal phenomenology of the “terrestrial machine”, a bit 
>> like infinite sums can play a role in physics, like the zeta 
>> renormalisation in superstring theory.
>> Note that most of those divine (infinite) machine are still obeying to 
>> the same self-reference logics (G and G*), and would not change much in the 
>> mathematical derivation of physics from arithmetic. Note also that the 
>> first person indeterminacy is connected to the machine + random oracle, so 
>> that the “sigma_1” predicate is really sigma_1 in all oracles, and this 
>> makes it possible to use some strong set axiom (like “projective 
>> determinacy”) to assure the existence of the measure, and probably of the 
>> needed generalisation of Feynman integral in arithmetic. (This needs indeed 
>> a generalisation of the Church’s thesis, called the hyperarihmetical 
>> church’s thesis in the classical  textbook by Rogers).
>>
>> Bruno
>>
>>
>>
> When we get into subtleties of ZF set theory we get into the application 
> of axioms, eg the axiom of replacement, axiom of infinity, axiom of choice 
> etc, that have a limited bearing on most standard mathematics. This means 
> physics is even further removed. Transfinite numbers and the question of 
> א_0 ≤ c ≤ 2^א_0 or the continuum hypothesis has a role with Robinson’s 
> numbers. These are in a sense the reciprocals of transfinite numbers or the 
> continuum. This has some bearing in the foundations of calculus, though I 
> am far from familiar with this. I am not sure what possible role this could 
> have for physics.
>
> Infinite mathematical quantities are common in physics. The 2-dim CFT is 
> Virasoro which is a Witt algebra extended to infinite dimensions with a 
> kernel. This does not though mean physics predicts the measurement of 
> infinite quantities  A Hilbert space may have an infinite number of states, 
> but that does not mean we expect to measure a quantum state with N → ∞.
>
> LC
>
>
>

Permitting entities in its language is a )perhaps the major) problem with 
the current approach to theoretical physics and which most physicists seem 
oblivious to. It is a form of double-speak to say there are no infinities 
but then make theories based on them ... unless they are introduced in a 
theoretically appropriate manner, which has yet been done. 

The continuum threatens us with infinities:

But even if we take a hard-headed practical attitude and leave logic to the
logicians, our struggles with the continuum are not over. In fact, the 
infinitely
divisible nature of the real line—the existence of arbitrarily small real 
numbers—is a serious challenge to physics.

We have seen that in every major theory of physics, challenging mathematical
questions arise from the assumption that spacetime is a continuum. The 
continuum threatens us with infinities. Do these infinities threaten our 
ability to
extract predictions from these theories—or even our ability to formulate 
these
theories in a precise way? We can answer these questions, but only with hard
work. Is this a sign that we are somehow on the wrong track? Is the 
continuum as we understand it only an approximation to some deeper model of 
spacetime?

Only time will tell. Nature is providing us with plenty of clues, but it 
will take
patience to read them correctly.

*Struggles with the Continuum*
John C. Baez
https://arxiv.org/abs/1609.01421v4
https://arxiv.org/pdf/1609.01421v4.pdf


@philipthrift

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/ac138fac-df6e-4e4f-b467-5be38b70e30e%40googlegroups.com.

Re: A Church-Turing-Thesis for Infinitary Computations

[Lawrence Crowell]

On Wednesday, March 18, 2020 at 4:13:36 AM UTC-5, Bruno Marchal wrote:
>
>
> On 17 Mar 2020, at 16:14, Lawrence Crowell  > wrote:
>
> I pretty seriously doubt these things will enter into physics. 
> Computations with Cantor's aleph hierarchy of transfinite numbers seems 
> pretty far removed from anything really physical.
>
>
>
> OK. It is just abstract recursion theory, has been with Turing, and it 
> concerns divine creatures, and the goal is to show that even those “divine” 
> (infinite being) cannot effectively recover the arithmetical truth/reality. 
> I doubt too that such machine can be brought to Earth, and they do play 
> some role in the internal phenomenology of the “terrestrial machine”, a bit 
> like infinite sums can play a role in physics, like the zeta 
> renormalisation in superstring theory.
> Note that most of those divine (infinite) machine are still obeying to the 
> same self-reference logics (G and G*), and would not change much in the 
> mathematical derivation of physics from arithmetic. Note also that the 
> first person indeterminacy is connected to the machine + random oracle, so 
> that the “sigma_1” predicate is really sigma_1 in all oracles, and this 
> makes it possible to use some strong set axiom (like “projective 
> determinacy”) to assure the existence of the measure, and probably of the 
> needed generalisation of Feynman integral in arithmetic. (This needs indeed 
> a generalisation of the Church’s thesis, called the hyperarihmetical 
> church’s thesis in the classical  textbook by Rogers).
>
> Bruno
>
>
>
When we get into subtleties of ZF set theory we get into the application of 
axioms, eg the axiom of replacement, axiom of infinity, axiom of choice 
etc, that have a limited bearing on most standard mathematics. This means 
physics is even further removed. Transfinite numbers and the question of 
א_0 ≤ c ≤ 2^א_0 or the continuum hypothesis has a role with Robinson’s 
numbers. These are in a sense the reciprocals of transfinite numbers or the 
continuum. This has some bearing in the foundations of calculus, though I 
am far from familiar with this. I am not sure what possible role this could 
have for physics.

Infinite mathematical quantities are common in physics. The 2-dim CFT is 
Virasoro which is a Witt algebra extended to infinite dimensions with a 
kernel. This does not though mean physics predicts the measurement of 
infinite quantities  A Hilbert space may have an infinite number of states, 
but that does not mean we expect to measure a quantum state with N → ∞.

LC

 

>
>
> LC
>
> On Tuesday, March 17, 2020 at 4:41:09 AM UTC-5, Philip Thrift wrote:
>>
>>
>> *Towards a Church-Turing-Thesis for Infinitary Computations*
>> https://arxiv.org/abs/1307.6599
>> Merlin Carl
>>
>> *We consider the question whether there is an infinitary analogue of the 
>> Church-Turing-thesis. To this end, we argue that there is an intuitive 
>> notion of transfinite computability and build a canonical model, called 
>> Idealized Agent Machines (IAMs) of this which will turn out to be 
>> equivalent in strength to the Ordinal Turing Machines defined by P. Koepke.*
>>
>> *Infinite computations with random oracles*
>> https://arxiv.org/abs/1307.0160
>>
>> *Effectivity and Reducibility with Ordinal Turing Machines*
>> https://arxiv.org/abs/1811.11630
>>
>> *Ordinal Computability: An Introduction to Infinitary Machines*
>>
>> https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ
>>
>> @philipthrift
>>
>
> -- 
> 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 everyth...@googlegroups.com .
> To view this discussion on the web visit 
> https://groups.google.com/d/msgid/everything-list/d9532c24-0130-4733-9ffe-154b335103d9%40googlegroups.com
>  
> <https://groups.google.com/d/msgid/everything-list/d9532c24-0130-4733-9ffe-154b335103d9%40googlegroups.com?utm_medium=email_source=footer>
> .
>
>
>

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/9cfe048d-2088-4c55-8304-517c0fc5658f%40googlegroups.com.

Re: A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

It is a contradiction for a physicist to say, literally,

 *nothing real is infinite*

http://backreaction.blogspot.com/2020/03/unpredictability-undecidability-and.html

yet their physics extensively uses infinitary mathematics

https://physics.stackexchange.com/questions/149786/why-do-we-need-infinite-dimensional-hilbert-spaces-in-physics

(To be consistent: All theoretical physics should be based on *discrete, 
finite mathematics*. with *no violations permitted*. That, or the premise 
itself should be voided.)

It's like one hand does not know what the other hand is doing.

@philipthrift


On Tuesday, March 17, 2020 at 10:14:28 AM UTC-5, Lawrence Crowell wrote:
>
> I pretty seriously doubt these things will enter into physics. 
> Computations with Cantor's aleph hierarchy of transfinite numbers seems 
> pretty far removed from anything really physical.
>
> LC
>
> On Tuesday, March 17, 2020 at 4:41:09 AM UTC-5, Philip Thrift wrote:
>>
>>
>> *Towards a Church-Turing-Thesis for Infinitary Computations*
>> https://arxiv.org/abs/1307.6599
>> Merlin Carl
>>
>> *We consider the question whether there is an infinitary analogue of the 
>> Church-Turing-thesis. To this end, we argue that there is an intuitive 
>> notion of transfinite computability and build a canonical model, called 
>> Idealized Agent Machines (IAMs) of this which will turn out to be 
>> equivalent in strength to the Ordinal Turing Machines defined by P. Koepke.*
>>
>> *Infinite computations with random oracles*
>> https://arxiv.org/abs/1307.0160
>>
>> *Effectivity and Reducibility with Ordinal Turing Machines*
>> https://arxiv.org/abs/1811.11630
>>
>> *Ordinal Computability: An Introduction to Infinitary Machines*
>>
>> https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ
>>
>> @philipthrift
>>
>

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/50935dcd-1921-494c-ab2a-1a151d1fb17b%40googlegroups.com.

Re: A Church-Turing-Thesis for Infinitary Computations

[Bruno Marchal]

> On 17 Mar 2020, at 16:14, Lawrence Crowell  
> wrote:
> 
> I pretty seriously doubt these things will enter into physics. Computations 
> with Cantor's aleph hierarchy of transfinite numbers seems pretty far removed 
> from anything really physical.


OK. It is just abstract recursion theory, has been with Turing, and it concerns 
divine creatures, and the goal is to show that even those “divine” (infinite 
being) cannot effectively recover the arithmetical truth/reality. I doubt too 
that such machine can be brought to Earth, and they do play some role in the 
internal phenomenology of the “terrestrial machine”, a bit like infinite sums 
can play a role in physics, like the zeta renormalisation in superstring theory.
Note that most of those divine (infinite) machine are still obeying to the same 
self-reference logics (G and G*), and would not change much in the mathematical 
derivation of physics from arithmetic. Note also that the first person 
indeterminacy is connected to the machine + random oracle, so that the 
“sigma_1” predicate is really sigma_1 in all oracles, and this makes it 
possible to use some strong set axiom (like “projective determinacy”) to assure 
the existence of the measure, and probably of the needed generalisation of 
Feynman integral in arithmetic. (This needs indeed a generalisation of the 
Church’s thesis, called the hyperarihmetical church’s thesis in the classical  
textbook by Rogers).

Bruno




> 
> LC
> 
> On Tuesday, March 17, 2020 at 4:41:09 AM UTC-5, Philip Thrift wrote:
> 
> Towards a Church-Turing-Thesis for Infinitary Computations
> https://arxiv.org/abs/1307.6599 <https://arxiv.org/abs/1307.6599>
> Merlin Carl
> 
> We consider the question whether there is an infinitary analogue of the 
> Church-Turing-thesis. To this end, we argue that there is an intuitive notion 
> of transfinite computability and build a canonical model, called Idealized 
> Agent Machines (IAMs) of this which will turn out to be equivalent in 
> strength to the Ordinal Turing Machines defined by P. Koepke.
> 
> Infinite computations with random oracles
> https://arxiv.org/abs/1307.0160 <https://arxiv.org/abs/1307.0160>
> 
> Effectivity and Reducibility with Ordinal Turing Machines
> https://arxiv.org/abs/1811.11630 <https://arxiv.org/abs/1811.11630>
> 
> Ordinal Computability: An Introduction to Infinitary Machines
> https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ
>  
> <https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ>
> 
> @philipthrift
> 
> -- 
> 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 view this discussion on the web visit 
> https://groups.google.com/d/msgid/everything-list/d9532c24-0130-4733-9ffe-154b335103d9%40googlegroups.com
>  
> <https://groups.google.com/d/msgid/everything-list/d9532c24-0130-4733-9ffe-154b335103d9%40googlegroups.com?utm_medium=email_source=footer>.

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/6CA3CA7A-2601-4002-912E-15E97C201F1F%40ulb.ac.be.

Re: A Church-Turing-Thesis for Infinitary Computations

[Lawrence Crowell]

I pretty seriously doubt these things will enter into physics. Computations 
with Cantor's aleph hierarchy of transfinite numbers seems pretty far 
removed from anything really physical.

LC

On Tuesday, March 17, 2020 at 4:41:09 AM UTC-5, Philip Thrift wrote:
>
>
> *Towards a Church-Turing-Thesis for Infinitary Computations*
> https://arxiv.org/abs/1307.6599
> Merlin Carl
>
> *We consider the question whether there is an infinitary analogue of the 
> Church-Turing-thesis. To this end, we argue that there is an intuitive 
> notion of transfinite computability and build a canonical model, called 
> Idealized Agent Machines (IAMs) of this which will turn out to be 
> equivalent in strength to the Ordinal Turing Machines defined by P. Koepke.*
>
> *Infinite computations with random oracles*
> https://arxiv.org/abs/1307.0160
>
> *Effectivity and Reducibility with Ordinal Turing Machines*
> https://arxiv.org/abs/1811.11630
>
> *Ordinal Computability: An Introduction to Infinitary Machines*
>
> https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ
>
> @philipthrift
>

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/d9532c24-0130-4733-9ffe-154b335103d9%40googlegroups.com.

A Church-Turing-Thesis for Infinitary Computations

[Philip Thrift]

*Towards a Church-Turing-Thesis for Infinitary Computations*
https://arxiv.org/abs/1307.6599
Merlin Carl

*We consider the question whether there is an infinitary analogue of the 
Church-Turing-thesis. To this end, we argue that there is an intuitive 
notion of transfinite computability and build a canonical model, called 
Idealized Agent Machines (IAMs) of this which will turn out to be 
equivalent in strength to the Ordinal Turing Machines defined by P. Koepke.*

*Infinite computations with random oracles*
https://arxiv.org/abs/1307.0160

*Effectivity and Reducibility with Ordinal Turing Machines*
https://arxiv.org/abs/1811.11630

*Ordinal Computability: An Introduction to Infinitary Machines*
https://books.google.com/books/about/Ordinal_Computability.html?id=UjvEDwAAQBAJ

@philipthrift

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/everything-list/fd7973e7-fba2-4f14-bf6f-dbded76e5bbf%40googlegroups.com.

Re: Church-Turing Thesis

[Bruno Marchal]

> On 29 Aug 2018, at 19:11, agrayson2...@gmail.com wrote:
> 
> 
> 
> On Wednesday, August 29, 2018 at 12:14:50 AM UTC-6, Bruno Marchal wrote:
> 
>> On 29 Aug 2018, at 02:30, agrays...@gmail.com  wrote:
>> 
>> 
>> 
>> On Tuesday, August 28, 2018 at 2:19:40 AM UTC-6, Bruno Marchal wrote:
>> 
>>> On 27 Aug 2018, at 19:54, agrays...@gmail.com <> wrote:
>>> 
>>> 
>>> 
>>> On Saturday, August 25, 2018 at 1:11:47 AM UTC-6, Bruno Marchal wrote:
>>> 
>>>> On 25 Aug 2018, at 01:15, agrays...@gmail.com <> wrote:
>>>> 
>>>> 
>>>> 
>>>> On Friday, August 24, 2018 at 12:25:03 PM UTC, telmo_menezes wrote:
>>>> On 23 August 2018 at 06:31,  > wrote: 
>>>> > 
>>>> > 
>>>> > On Thursday, August 23, 2018 at 2:01:24 AM UTC, Jason wrote: 
>>>> >> 
>>>> >> 
>>>> >> 
>>>> >> On Wed, Aug 22, 2018 at 4:43 PM > wrote: 
>>>> >>> 
>>>> >>> 
>>>> >>> 
>>>> >>> On Tuesday, August 21, 2018 at 3:22:04 PM UTC, Jason wrote: 
>>>> >>>> 
>>>> >>>> 
>>>> >>>> 
>>>> >>>> On Tue, Aug 21, 2018 at 1:16 AM > wrote: 
>>>> >>>>> 
>>>> >>>>> I've been looking at the Wiki article on this topic. I find that I 
>>>> >>>>> really don't understand what it is, or why it's important. Maybe a 
>>>> >>>>> few 
>>>> >>>>> succinct words from the usual suspects can be of help. TIA. 
>>>> >>>>> 
>>>> >>>>> 
>>>> >>>> 
>>>> >>>> 
>>>> >>>> Bruno provided a great definition and background of the Church-Turing 
>>>> >>>> Thesis. I will try to answer why it is important and comes up often 
>>>> >>>> in our 
>>>> >>>> discussion. 
>>>> >>>> 
>>>> >>>> 
>>>> >>>> The Church-Turing thesis says that anything that is computable is 
>>>> >>>> computable by any computer.  In other words, there is nothing that 
>>>> >>>> the 
>>>> >>>> computer in your cell phone can't compute, that your laptop or that a 
>>>> >>>> super 
>>>> >>>> computer (or even a quantum computer) can.  It just comes down to 
>>>> >>>> having 
>>>> >>>> enough time and memory. 
>>>> >>>> 
>>>> >>>> This is why you don't need to buy a new phone with new hardware every 
>>>> >>>> time you want to install a new app.  Regardless of the type of CPU in 
>>>> >>>> your 
>>>> >>>> phone, it can be extended in its power of what it might compute only 
>>>> >>>> given 
>>>> >>>> some new software.  It is in this sense that computers are 
>>>> >>>> "Universal", they 
>>>> >>>> are universal in the same sense that of a universal remote, or in the 
>>>> >>>> sense 
>>>> >>>> that a record player is a universal sound imitating device.  A record 
>>>> >>>> player 
>>>> >>>> might emulate the sounds of an orchestra, Britney Spears, whale 
>>>> >>>> songs, etc., 
>>>> >>>> all it needs is the appropriate record and it can produce the sound. 
>>>> >>>> 
>>>> >>>> In the same sense, all a Turing Machine (computer) needs to imitate 
>>>> >>>> (or 
>>>> >>>> emulate) the right program or function is the right software.  
>>>> >>>> Because of 
>>>> >>>> this, anything that can be described in software, be it a brain 
>>>> >>>> emulation, 
>>>> >>>> an AI, a virtual environment, a virtual machine or operating system, 
>>>> >>>> can 
>>>> >>>> never know what hardware is running it, because the Church-Turing 
>>>> >>>> thesis 
>>>> >>>> says that any computer is capable of running it. 
>>>> >>>> 
>>

Re: Church-Turing Thesis

[agrayson2000]

On Wednesday, August 29, 2018 at 12:14:50 AM UTC-6, Bruno Marchal wrote:
>
>
> On 29 Aug 2018, at 02:30, agrays...@gmail.com  wrote:
>
>
>
> On Tuesday, August 28, 2018 at 2:19:40 AM UTC-6, Bruno Marchal wrote:
>>
>>
>> On 27 Aug 2018, at 19:54, agrays...@gmail.com wrote:
>>
>>
>>
>> On Saturday, August 25, 2018 at 1:11:47 AM UTC-6, Bruno Marchal wrote:
>>>
>>>
>>> On 25 Aug 2018, at 01:15, agrays...@gmail.com wrote:
>>>
>>>
>>>
>>> On Friday, August 24, 2018 at 12:25:03 PM UTC, telmo_menezes wrote:
>>>>
>>>> On 23 August 2018 at 06:31,   wrote: 
>>>> > 
>>>> > 
>>>> > On Thursday, August 23, 2018 at 2:01:24 AM UTC, Jason wrote: 
>>>> >> 
>>>> >> 
>>>> >> 
>>>> >> On Wed, Aug 22, 2018 at 4:43 PM  wrote: 
>>>> >>> 
>>>> >>> 
>>>> >>> 
>>>> >>> On Tuesday, August 21, 2018 at 3:22:04 PM UTC, Jason wrote: 
>>>> >>>> 
>>>> >>>> 
>>>> >>>> 
>>>> >>>> On Tue, Aug 21, 2018 at 1:16 AM  wrote: 
>>>> >>>>> 
>>>> >>>>> I've been looking at the Wiki article on this topic. I find that 
>>>> I 
>>>> >>>>> really don't understand what it is, or why it's important. Maybe 
>>>> a few 
>>>> >>>>> succinct words from the usual suspects can be of help. TIA. 
>>>> >>>>> 
>>>> >>>>> 
>>>> >>>> 
>>>> >>>> 
>>>> >>>> Bruno provided a great definition and background of the 
>>>> Church-Turing 
>>>> >>>> Thesis. I will try to answer why it is important and comes up 
>>>> often in our 
>>>> >>>> discussion. 
>>>> >>>> 
>>>> >>>> 
>>>> >>>> The Church-Turing thesis says that anything that is computable is 
>>>> >>>> computable by any computer.  In other words, there is nothing that 
>>>> the 
>>>> >>>> computer in your cell phone can't compute, that your laptop or 
>>>> that a super 
>>>> >>>> computer (or even a quantum computer) can.  It just comes down to 
>>>> having 
>>>> >>>> enough time and memory. 
>>>> >>>> 
>>>> >>>> This is why you don't need to buy a new phone with new hardware 
>>>> every 
>>>> >>>> time you want to install a new app.  Regardless of the type of CPU 
>>>> in your 
>>>> >>>> phone, it can be extended in its power of what it might compute 
>>>> only given 
>>>> >>>> some new software.  It is in this sense that computers are 
>>>> "Universal", they 
>>>> >>>> are universal in the same sense that of a universal remote, or in 
>>>> the sense 
>>>> >>>> that a record player is a universal sound imitating device.  A 
>>>> record player 
>>>> >>>> might emulate the sounds of an orchestra, Britney Spears, whale 
>>>> songs, etc., 
>>>> >>>> all it needs is the appropriate record and it can produce the 
>>>> sound. 
>>>> >>>> 
>>>> >>>> In the same sense, all a Turing Machine (computer) needs to 
>>>> imitate (or 
>>>> >>>> emulate) the right program or function is the right software. 
>>>>  Because of 
>>>> >>>> this, anything that can be described in software, be it a brain 
>>>> emulation, 
>>>> >>>> an AI, a virtual environment, a virtual machine or operating 
>>>> system, can 
>>>> >>>> never know what hardware is running it, because the Church-Turing 
>>>> thesis 
>>>> >>>> says that any computer is capable of running it. 
>>>> >>>> 
>>>> >>>> This is why if consciousness is computable (the computational 
>>>> theory of 
>>>> >>>> mind) we cannot know what is computing us (e.g. we could be in a 
>>>> matrix type 
>>>> >>>> simulation for all we know).  The other implication is that if

Re: Church-Turing Thesis

[Bruno Marchal]

> On 29 Aug 2018, at 02:30, agrayson2...@gmail.com wrote:
> 
> 
> 
> On Tuesday, August 28, 2018 at 2:19:40 AM UTC-6, Bruno Marchal wrote:
> 
>> On 27 Aug 2018, at 19:54, agrays...@gmail.com  wrote:
>> 
>> 
>> 
>> On Saturday, August 25, 2018 at 1:11:47 AM UTC-6, Bruno Marchal wrote:
>> 
>>> On 25 Aug 2018, at 01:15, agrays...@gmail.com <> wrote:
>>> 
>>> 
>>> 
>>> On Friday, August 24, 2018 at 12:25:03 PM UTC, telmo_menezes wrote:
>>> On 23 August 2018 at 06:31,  > wrote: 
>>> > 
>>> > 
>>> > On Thursday, August 23, 2018 at 2:01:24 AM UTC, Jason wrote: 
>>> >> 
>>> >> 
>>> >> 
>>> >> On Wed, Aug 22, 2018 at 4:43 PM > wrote: 
>>> >>> 
>>> >>> 
>>> >>> 
>>> >>> On Tuesday, August 21, 2018 at 3:22:04 PM UTC, Jason wrote: 
>>> >>>> 
>>> >>>> 
>>> >>>> 
>>> >>>> On Tue, Aug 21, 2018 at 1:16 AM > wrote: 
>>> >>>>> 
>>> >>>>> I've been looking at the Wiki article on this topic. I find that I 
>>> >>>>> really don't understand what it is, or why it's important. Maybe a 
>>> >>>>> few 
>>> >>>>> succinct words from the usual suspects can be of help. TIA. 
>>> >>>>> 
>>> >>>>> 
>>> >>>> 
>>> >>>> 
>>> >>>> Bruno provided a great definition and background of the Church-Turing 
>>> >>>> Thesis. I will try to answer why it is important and comes up often in 
>>> >>>> our 
>>> >>>> discussion. 
>>> >>>> 
>>> >>>> 
>>> >>>> The Church-Turing thesis says that anything that is computable is 
>>> >>>> computable by any computer.  In other words, there is nothing that the 
>>> >>>> computer in your cell phone can't compute, that your laptop or that a 
>>> >>>> super 
>>> >>>> computer (or even a quantum computer) can.  It just comes down to 
>>> >>>> having 
>>> >>>> enough time and memory. 
>>> >>>> 
>>> >>>> This is why you don't need to buy a new phone with new hardware every 
>>> >>>> time you want to install a new app.  Regardless of the type of CPU in 
>>> >>>> your 
>>> >>>> phone, it can be extended in its power of what it might compute only 
>>> >>>> given 
>>> >>>> some new software.  It is in this sense that computers are 
>>> >>>> "Universal", they 
>>> >>>> are universal in the same sense that of a universal remote, or in the 
>>> >>>> sense 
>>> >>>> that a record player is a universal sound imitating device.  A record 
>>> >>>> player 
>>> >>>> might emulate the sounds of an orchestra, Britney Spears, whale songs, 
>>> >>>> etc., 
>>> >>>> all it needs is the appropriate record and it can produce the sound. 
>>> >>>> 
>>> >>>> In the same sense, all a Turing Machine (computer) needs to imitate 
>>> >>>> (or 
>>> >>>> emulate) the right program or function is the right software.  Because 
>>> >>>> of 
>>> >>>> this, anything that can be described in software, be it a brain 
>>> >>>> emulation, 
>>> >>>> an AI, a virtual environment, a virtual machine or operating system, 
>>> >>>> can 
>>> >>>> never know what hardware is running it, because the Church-Turing 
>>> >>>> thesis 
>>> >>>> says that any computer is capable of running it. 
>>> >>>> 
>>> >>>> This is why if consciousness is computable (the computational theory 
>>> >>>> of 
>>> >>>> mind) we cannot know what is computing us (e.g. we could be in a 
>>> >>>> matrix type 
>>> >>>> simulation for all we know).  The other implication is that if 
>>> >>>> computations 
>>> >>>> exist in mathematics (and they do), then we exist within mathematics. 
>>> >>>>

Re: Church-Turing Thesis

[agrayson2000]

On Tuesday, August 28, 2018 at 2:19:40 AM UTC-6, Bruno Marchal wrote:
>
>
> On 27 Aug 2018, at 19:54, agrays...@gmail.com  wrote:
>
>
>
> On Saturday, August 25, 2018 at 1:11:47 AM UTC-6, Bruno Marchal wrote:
>>
>>
>> On 25 Aug 2018, at 01:15, agrays...@gmail.com wrote:
>>
>>
>>
>> On Friday, August 24, 2018 at 12:25:03 PM UTC, telmo_menezes wrote:
>>>
>>> On 23 August 2018 at 06:31,   wrote: 
>>> > 
>>> > 
>>> > On Thursday, August 23, 2018 at 2:01:24 AM UTC, Jason wrote: 
>>> >> 
>>> >> 
>>> >> 
>>> >> On Wed, Aug 22, 2018 at 4:43 PM  wrote: 
>>> >>> 
>>> >>> 
>>> >>> 
>>> >>> On Tuesday, August 21, 2018 at 3:22:04 PM UTC, Jason wrote: 
>>> >>>> 
>>> >>>> 
>>> >>>> 
>>> >>>> On Tue, Aug 21, 2018 at 1:16 AM  wrote: 
>>> >>>>> 
>>> >>>>> I've been looking at the Wiki article on this topic. I find that I 
>>> >>>>> really don't understand what it is, or why it's important. Maybe a 
>>> few 
>>> >>>>> succinct words from the usual suspects can be of help. TIA. 
>>> >>>>> 
>>> >>>>> 
>>> >>>> 
>>> >>>> 
>>> >>>> Bruno provided a great definition and background of the 
>>> Church-Turing 
>>> >>>> Thesis. I will try to answer why it is important and comes up often 
>>> in our 
>>> >>>> discussion. 
>>> >>>> 
>>> >>>> 
>>> >>>> The Church-Turing thesis says that anything that is computable is 
>>> >>>> computable by any computer.  In other words, there is nothing that 
>>> the 
>>> >>>> computer in your cell phone can't compute, that your laptop or that 
>>> a super 
>>> >>>> computer (or even a quantum computer) can.  It just comes down to 
>>> having 
>>> >>>> enough time and memory. 
>>> >>>> 
>>> >>>> This is why you don't need to buy a new phone with new hardware 
>>> every 
>>> >>>> time you want to install a new app.  Regardless of the type of CPU 
>>> in your 
>>> >>>> phone, it can be extended in its power of what it might compute 
>>> only given 
>>> >>>> some new software.  It is in this sense that computers are 
>>> "Universal", they 
>>> >>>> are universal in the same sense that of a universal remote, or in 
>>> the sense 
>>> >>>> that a record player is a universal sound imitating device.  A 
>>> record player 
>>> >>>> might emulate the sounds of an orchestra, Britney Spears, whale 
>>> songs, etc., 
>>> >>>> all it needs is the appropriate record and it can produce the 
>>> sound. 
>>> >>>> 
>>> >>>> In the same sense, all a Turing Machine (computer) needs to imitate 
>>> (or 
>>> >>>> emulate) the right program or function is the right software. 
>>>  Because of 
>>> >>>> this, anything that can be described in software, be it a brain 
>>> emulation, 
>>> >>>> an AI, a virtual environment, a virtual machine or operating 
>>> system, can 
>>> >>>> never know what hardware is running it, because the Church-Turing 
>>> thesis 
>>> >>>> says that any computer is capable of running it. 
>>> >>>> 
>>> >>>> This is why if consciousness is computable (the computational 
>>> theory of 
>>> >>>> mind) we cannot know what is computing us (e.g. we could be in a 
>>> matrix type 
>>> >>>> simulation for all we know).  The other implication is that if 
>>> computations 
>>> >>>> exist in mathematics (and they do), then we exist within 
>>> mathematics. 
>>> >>>> Mathematics (or at least the part necessary to describe 
>>> computations) 
>>> >>>> becomes the fundamental science of what we experience and what is 
>>> possible 
>>> >>>> to experience or what we may predict about our future experiences 
>>> (physics). 
>>> >>>&g

Re: Church-Turing Thesis

[Bruno Marchal]

> On 27 Aug 2018, at 20:18, agrayson2...@gmail.com wrote:
> 
> 
> 
> On Friday, August 24, 2018 at 3:22:39 AM UTC-6, Bruno Marchal wrote:
> 
>> On 24 Aug 2018, at 00:53, agrays...@gmail.com  wrote:
>> 
>> 
>> 
>> On Thursday, August 23, 2018 at 5:55:33 PM UTC, agrays...@gmail.com 
>>  wrote:
>> 
>> 
>> On Thursday, August 23, 2018 at 3:28:13 PM UTC, Brent wrote:
>> Why don't we all chip in an buy Alan a computer so he can look stuff up on 
>> Wikipedia.
>> 
>> Brent
>> 
>> I will when you have the courtesy to explain your contradictory statements 
>> about the instantaneous, infinite extent of the wf. Oh BTW, with your big 
>> brain, I suppose it never occurred to you that I wanted to hear Bruno's 
>> definition, which if experience is worth anything, could be wildly DIFFERENT 
>> from Wiki. While you assess all that, why don't you go fuck yourself, and 
>> then tell us how it felt. OK? AG
>> 
>> FWIW, comparing Bruno's description with Wiki, which was my intent, 
>> confirms, at least for me, that the postulates of QM are easier to 
>> understand, even though many of the defining functions of a Turing Machine 
>> are known to those who have programmed modern computers, notwithstanding 
>> that the latter use random access memory. I don't see why the use of RAM is 
>> decisively important in distinguishing a Turing Machine from how modern 
>> computers are designed. AG  
> 
> 
> You are right. You can see a von Neumann computer as a Turing machine. As the 
> set of symbols, and state are arbitrary, you can even see a brain as a Turing 
> machine.
> 
> From my naive pov, I initially think a Turing machine can manipulate 
> arbitrary symbols and logical commands, and is limited to computable 
> functions, whatever they are. If so, and you consider a brain a Turing 
> machine, what does it do with non-computable functions? AG

I will show that universality (the ability to compute *all* computable 
function) entails the possibility of ending in a non terminating computation, 
without any ability to know that that is the case. But for this, we need first 
to get a definition of what is computable. We will come back on this. You want 
proceed to much quickly I think. It is good, but there are some subtleties and 
traps to avoid.

Bruno




>  
> That is why eventually Gödel accepted Turing’s argument for the Church’s 
> thesis.
> 
> Note that the wikipedia is often bad on logic or on computation, ...not 
> mentioning computationalism. 
> 
> Have you understood Cantor’s diagonal proof of the non enumerability of the 
> set of infinite sequence, in my yesterday post. If not I can explain again, 
> with different notation. There is a real surprise at the end of that thread, 
> you will see (I think and hope).
> 
> Bruno
> 
> 
> 
> 
>> 
>> 
>> On 8/22/2018 5:58 PM, John Clark wrote:
>>> On Wed, Aug 22, 2018 at 8:26 PM, > wrote:
>>> 
>>> >> Yes, the Busy Beaver Function is not computable. We know that:
>>> 
>>> BB(1) =1
>>> BB(2) =6
>>> BB(3) =21
>>> BB(4) =107
>>> 
>>> > You haven't *written* the function, just its alleged values for 1,2,3,4.  
>>> > What is the function? 
>>>  
>>> 
>>> Starting with a all zero tape BB(N) is the number of operations any N state 
>>> Turing Machine performs after it writes the largest number of 1's and then 
>>> halts. It is very important that it halt, some machines will go on forever 
>>> but they don't count. For example we know for sure that BB(5) is at least 
>>> 47,176,870 because one 5 state Turing Machine has been found that halts 
>>> after it goes through 47,176,870 operations (and prints 4098 1’s on the 
>>> tape), but there are 28 other 5 state machines displaying non-regular 
>>> behavior that are well past 47,176,870 operations and 4098 1's. If one of 
>>> them eventually halts then that larger number of operations will be BB(5), 
>>> if none of them ever halts then 47,176,870 really is BB(5); but the trouble 
>>> is we'll never be able to know it’s 47,176,870 because we'll never know 
>>> that none of those other 28 5 state machines will never halt because the 
>>> Halting problem is insolvable.
>>> 
>>> 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-li...@googlegroups.com <>.
>>> To post to this group, send email to everyth...@googlegroups.com <>.
>>> Visit this group at https://groups.google.com/group/everything-list 
>>> .
>>> For more options, visit 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-li...@googlegroups.com .
>> To post to this group, send 

Re: Church-Turing Thesis

[Bruno Marchal]

> On 27 Aug 2018, at 19:54, agrayson2...@gmail.com wrote:
> 
> 
> 
> On Saturday, August 25, 2018 at 1:11:47 AM UTC-6, Bruno Marchal wrote:
> 
>> On 25 Aug 2018, at 01:15, agrays...@gmail.com  wrote:
>> 
>> 
>> 
>> On Friday, August 24, 2018 at 12:25:03 PM UTC, telmo_menezes wrote:
>> On 23 August 2018 at 06:31,  > wrote: 
>> > 
>> > 
>> > On Thursday, August 23, 2018 at 2:01:24 AM UTC, Jason wrote: 
>> >> 
>> >> 
>> >> 
>> >> On Wed, Aug 22, 2018 at 4:43 PM > wrote: 
>> >>> 
>> >>> 
>> >>> 
>> >>> On Tuesday, August 21, 2018 at 3:22:04 PM UTC, Jason wrote: 
>> >>>> 
>> >>>> 
>> >>>> 
>> >>>> On Tue, Aug 21, 2018 at 1:16 AM > wrote: 
>> >>>>> 
>> >>>>> I've been looking at the Wiki article on this topic. I find that I 
>> >>>>> really don't understand what it is, or why it's important. Maybe a few 
>> >>>>> succinct words from the usual suspects can be of help. TIA. 
>> >>>>> 
>> >>>>> 
>> >>>> 
>> >>>> 
>> >>>> Bruno provided a great definition and background of the Church-Turing 
>> >>>> Thesis. I will try to answer why it is important and comes up often in 
>> >>>> our 
>> >>>> discussion. 
>> >>>> 
>> >>>> 
>> >>>> The Church-Turing thesis says that anything that is computable is 
>> >>>> computable by any computer.  In other words, there is nothing that the 
>> >>>> computer in your cell phone can't compute, that your laptop or that a 
>> >>>> super 
>> >>>> computer (or even a quantum computer) can.  It just comes down to 
>> >>>> having 
>> >>>> enough time and memory. 
>> >>>> 
>> >>>> This is why you don't need to buy a new phone with new hardware every 
>> >>>> time you want to install a new app.  Regardless of the type of CPU in 
>> >>>> your 
>> >>>> phone, it can be extended in its power of what it might compute only 
>> >>>> given 
>> >>>> some new software.  It is in this sense that computers are "Universal", 
>> >>>> they 
>> >>>> are universal in the same sense that of a universal remote, or in the 
>> >>>> sense 
>> >>>> that a record player is a universal sound imitating device.  A record 
>> >>>> player 
>> >>>> might emulate the sounds of an orchestra, Britney Spears, whale songs, 
>> >>>> etc., 
>> >>>> all it needs is the appropriate record and it can produce the sound. 
>> >>>> 
>> >>>> In the same sense, all a Turing Machine (computer) needs to imitate (or 
>> >>>> emulate) the right program or function is the right software.  Because 
>> >>>> of 
>> >>>> this, anything that can be described in software, be it a brain 
>> >>>> emulation, 
>> >>>> an AI, a virtual environment, a virtual machine or operating system, 
>> >>>> can 
>> >>>> never know what hardware is running it, because the Church-Turing 
>> >>>> thesis 
>> >>>> says that any computer is capable of running it. 
>> >>>> 
>> >>>> This is why if consciousness is computable (the computational theory of 
>> >>>> mind) we cannot know what is computing us (e.g. we could be in a matrix 
>> >>>> type 
>> >>>> simulation for all we know).  The other implication is that if 
>> >>>> computations 
>> >>>> exist in mathematics (and they do), then we exist within mathematics. 
>> >>>> Mathematics (or at least the part necessary to describe computations) 
>> >>>> becomes the fundamental science of what we experience and what is 
>> >>>> possible 
>> >>>> to experience or what we may predict about our future experiences 
>> >>>> (physics). 
>> >>>> 
>> >>>> 
>> >>>> Jason 
>> >>> 
>> >>> 
>> >>> If someone digitizes (emulates) the Mona Lisa, is this equivalent to the 
>> >>> Mona L

Re: Church-Turing Thesis

[agrayson2000]

On Friday, August 24, 2018 at 3:22:39 AM UTC-6, Bruno Marchal wrote:
>
>
> On 24 Aug 2018, at 00:53, agrays...@gmail.com  wrote:
>
>
>
> On Thursday, August 23, 2018 at 5:55:33 PM UTC, agrays...@gmail.com wrote:
>>
>>
>>
>> On Thursday, August 23, 2018 at 3:28:13 PM UTC, Brent wrote:
>>>
>>> Why don't we all chip in an buy Alan a computer so he can look stuff up 
>>> on Wikipedia.
>>>
>>> Brent
>>>
>>
>> *I will when you have the courtesy to explain your contradictory 
>> statements about the instantaneous, infinite extent of the wf. Oh BTW, with 
>> your big brain, I suppose it never occurred to you that I wanted to hear 
>> Bruno's definition, which if experience is worth anything, could be wildly 
>> DIFFERENT from Wiki. While you assess all that, why don't you go fuck 
>> yourself, and then tell us how it felt. OK? AG*
>>
>
> *FWIW, comparing Bruno's description with Wiki, which was my intent, 
> confirms, at least for me, that the postulates of QM are easier to 
> understand, even though many of the defining functions of a Turing Machine 
> are known to those who have programmed modern computers, notwithstanding 
> that the latter use random access memory. I don't see why the use of RAM is 
> decisively important in distinguishing a Turing Machine from how modern 
> computers are designed. AG*  
>
>
>
> You are right. You can see a von Neumann computer as a Turing machine. As 
> the set of symbols, and state are arbitrary, you can even see a brain as a 
> Turing machine. 
>

*From my naive pov, I initially think a Turing machine can manipulate 
arbitrary symbols and logical commands, and is limited to computable 
functions, whatever they are. If so, and you consider a brain a Turing 
machine, what does it do with non-computable functions? AG*
 

> That is why eventually Gödel accepted Turing’s argument for the Church’s 
> thesis.
>
> Note that the wikipedia is often bad on logic or on computation, ...not 
> mentioning computationalism. 
>
> Have you understood Cantor’s diagonal proof of the non enumerability of 
> the set of infinite sequence, in my yesterday post. If not I can explain 
> again, with different notation. There is a real surprise at the end of that 
> thread, you will see (I think and hope).
>
> Bruno
>
>
>
>
>
>>
>>> On 8/22/2018 5:58 PM, John Clark wrote:
>>>
>>> On Wed, Aug 22, 2018 at 8:26 PM,  wrote:
>>>
>>> >>
> Yes, the Busy Beaver Function is not computable. We know that: 
>
> BB(1) =1
> BB(2) =6
> BB(3) =21
> BB(4) =107
>

 * > You haven't *written* the function, just its alleged values for 
 1,2,3,4.  What is the function? *

>>>  
>>>
>>> Starting with a all zero tape BB(N) is the number of operations any N 
>>> state Turing Machine performs after it writes the largest number of 1's and 
>>> then halts. It is very important that it halt, some machines will go on 
>>> forever but they don't count. For example we know for sure that BB(5) is at 
>>> least 47,176,870 because one 5 state Turing Machine has been found that 
>>> halts after it goes through 47,176,870 operations (and prints 4098 1’s on 
>>> the tape), but there are 28 other 5 state machines displaying non-regular 
>>> behavior that are well past 47,176,870 operations and 4098 1's. If one of 
>>> them eventually halts then that larger number of operations will be BB(5), 
>>> if none of them ever halts then 47,176,870 really is BB(5); but the trouble 
>>> is we'll never be able to know it’s 47,176,870 because we'll never know 
>>> that none of those other 28 5 state machines will never halt because the 
>>> Halting problem is insolvable.
>>>
>>> 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-li...@googlegroups.com.
>>> To post to this group, send email to everyth...@googlegroups.com.
>>> Visit this group at https://groups.google.com/group/everything-list.
>>> For more options, visit 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-li...@googlegroups.com .
> To post to this group, send email to everyth...@googlegroups.com 
> .
> Visit this group at https://groups.google.com/group/everything-list.
> For more options, visit 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 

Re: Church-Turing Thesis

[agrayson2000]

On Saturday, August 25, 2018 at 1:11:47 AM UTC-6, Bruno Marchal wrote:
>
>
> On 25 Aug 2018, at 01:15, agrays...@gmail.com  wrote:
>
>
>
> On Friday, August 24, 2018 at 12:25:03 PM UTC, telmo_menezes wrote:
>>
>> On 23 August 2018 at 06:31,   wrote: 
>> > 
>> > 
>> > On Thursday, August 23, 2018 at 2:01:24 AM UTC, Jason wrote: 
>> >> 
>> >> 
>> >> 
>> >> On Wed, Aug 22, 2018 at 4:43 PM  wrote: 
>> >>> 
>> >>> 
>> >>> 
>> >>> On Tuesday, August 21, 2018 at 3:22:04 PM UTC, Jason wrote: 
>> >>>> 
>> >>>> 
>> >>>> 
>> >>>> On Tue, Aug 21, 2018 at 1:16 AM  wrote: 
>> >>>>> 
>> >>>>> I've been looking at the Wiki article on this topic. I find that I 
>> >>>>> really don't understand what it is, or why it's important. Maybe a 
>> few 
>> >>>>> succinct words from the usual suspects can be of help. TIA. 
>> >>>>> 
>> >>>>> 
>> >>>> 
>> >>>> 
>> >>>> Bruno provided a great definition and background of the 
>> Church-Turing 
>> >>>> Thesis. I will try to answer why it is important and comes up often 
>> in our 
>> >>>> discussion. 
>> >>>> 
>> >>>> 
>> >>>> The Church-Turing thesis says that anything that is computable is 
>> >>>> computable by any computer.  In other words, there is nothing that 
>> the 
>> >>>> computer in your cell phone can't compute, that your laptop or that 
>> a super 
>> >>>> computer (or even a quantum computer) can.  It just comes down to 
>> having 
>> >>>> enough time and memory. 
>> >>>> 
>> >>>> This is why you don't need to buy a new phone with new hardware 
>> every 
>> >>>> time you want to install a new app.  Regardless of the type of CPU 
>> in your 
>> >>>> phone, it can be extended in its power of what it might compute only 
>> given 
>> >>>> some new software.  It is in this sense that computers are 
>> "Universal", they 
>> >>>> are universal in the same sense that of a universal remote, or in 
>> the sense 
>> >>>> that a record player is a universal sound imitating device.  A 
>> record player 
>> >>>> might emulate the sounds of an orchestra, Britney Spears, whale 
>> songs, etc., 
>> >>>> all it needs is the appropriate record and it can produce the sound. 
>> >>>> 
>> >>>> In the same sense, all a Turing Machine (computer) needs to imitate 
>> (or 
>> >>>> emulate) the right program or function is the right software. 
>>  Because of 
>> >>>> this, anything that can be described in software, be it a brain 
>> emulation, 
>> >>>> an AI, a virtual environment, a virtual machine or operating system, 
>> can 
>> >>>> never know what hardware is running it, because the Church-Turing 
>> thesis 
>> >>>> says that any computer is capable of running it. 
>> >>>> 
>> >>>> This is why if consciousness is computable (the computational theory 
>> of 
>> >>>> mind) we cannot know what is computing us (e.g. we could be in a 
>> matrix type 
>> >>>> simulation for all we know).  The other implication is that if 
>> computations 
>> >>>> exist in mathematics (and they do), then we exist within 
>> mathematics. 
>> >>>> Mathematics (or at least the part necessary to describe 
>> computations) 
>> >>>> becomes the fundamental science of what we experience and what is 
>> possible 
>> >>>> to experience or what we may predict about our future experiences 
>> (physics). 
>> >>>> 
>> >>>> 
>> >>>> Jason 
>> >>> 
>> >>> 
>> >>> If someone digitizes (emulates) the Mona Lisa, is this equivalent to 
>> the 
>> >>> Mona Lisa? 
>> >> 
>> >> 
>> >> If you digitize a person and put the digitized Mona Lisa before them, 
>> it 
>> >> is equivalent to the real Mona Lisa to that person, at least as far as 
>> they 
>> >> can tell. 
>> >> 
>> &

Re: Church-Turing Thesis

[agrayson2000]

On Friday, August 24, 2018 at 12:25:03 PM UTC, telmo_menezes wrote:
>
> On 23 August 2018 at 06:31,  > wrote: 
> > 
> > 
> > On Thursday, August 23, 2018 at 2:01:24 AM UTC, Jason wrote: 
> >> 
> >> 
> >> 
> >> On Wed, Aug 22, 2018 at 4:43 PM  wrote: 
> >>> 
> >>> 
> >>> 
> >>> On Tuesday, August 21, 2018 at 3:22:04 PM UTC, Jason wrote: 
> >>>> 
> >>>> 
> >>>> 
> >>>> On Tue, Aug 21, 2018 at 1:16 AM  wrote: 
> >>>>> 
> >>>>> I've been looking at the Wiki article on this topic. I find that I 
> >>>>> really don't understand what it is, or why it's important. Maybe a 
> few 
> >>>>> succinct words from the usual suspects can be of help. TIA. 
> >>>>> 
> >>>>> 
> >>>> 
> >>>> 
> >>>> Bruno provided a great definition and background of the Church-Turing 
> >>>> Thesis. I will try to answer why it is important and comes up often 
> in our 
> >>>> discussion. 
> >>>> 
> >>>> 
> >>>> The Church-Turing thesis says that anything that is computable is 
> >>>> computable by any computer.  In other words, there is nothing that 
> the 
> >>>> computer in your cell phone can't compute, that your laptop or that a 
> super 
> >>>> computer (or even a quantum computer) can.  It just comes down to 
> having 
> >>>> enough time and memory. 
> >>>> 
> >>>> This is why you don't need to buy a new phone with new hardware every 
> >>>> time you want to install a new app.  Regardless of the type of CPU in 
> your 
> >>>> phone, it can be extended in its power of what it might compute only 
> given 
> >>>> some new software.  It is in this sense that computers are 
> "Universal", they 
> >>>> are universal in the same sense that of a universal remote, or in the 
> sense 
> >>>> that a record player is a universal sound imitating device.  A record 
> player 
> >>>> might emulate the sounds of an orchestra, Britney Spears, whale 
> songs, etc., 
> >>>> all it needs is the appropriate record and it can produce the sound. 
> >>>> 
> >>>> In the same sense, all a Turing Machine (computer) needs to imitate 
> (or 
> >>>> emulate) the right program or function is the right software. 
>  Because of 
> >>>> this, anything that can be described in software, be it a brain 
> emulation, 
> >>>> an AI, a virtual environment, a virtual machine or operating system, 
> can 
> >>>> never know what hardware is running it, because the Church-Turing 
> thesis 
> >>>> says that any computer is capable of running it. 
> >>>> 
> >>>> This is why if consciousness is computable (the computational theory 
> of 
> >>>> mind) we cannot know what is computing us (e.g. we could be in a 
> matrix type 
> >>>> simulation for all we know).  The other implication is that if 
> computations 
> >>>> exist in mathematics (and they do), then we exist within mathematics. 
> >>>> Mathematics (or at least the part necessary to describe computations) 
> >>>> becomes the fundamental science of what we experience and what is 
> possible 
> >>>> to experience or what we may predict about our future experiences 
> (physics). 
> >>>> 
> >>>> 
> >>>> Jason 
> >>> 
> >>> 
> >>> If someone digitizes (emulates) the Mona Lisa, is this equivalent to 
> the 
> >>> Mona Lisa? 
> >> 
> >> 
> >> If you digitize a person and put the digitized Mona Lisa before them, 
> it 
> >> is equivalent to the real Mona Lisa to that person, at least as far as 
> they 
> >> can tell. 
> >> 
> >> 
> >>> 
> >>> Can you write a function which is not computable? AG 
> >>> 
> >>> 
> >> 
> >> If by not computable you mean it never returns, then this is easy: 
> >> 
> >> function foo(): 
> >>   while (true) 
> >>   { 
> >>  // loop forever 
> >>   } 
> >> 
> >> There are also programs for which no one knows if they are computable 
> or 
> >> not.  If you can prove whether or not this function ever completes, you 

Re: Church-Turing Thesis

[Telmo Menezes]

On 23 August 2018 at 06:31,   wrote:
>
>
> On Thursday, August 23, 2018 at 2:01:24 AM UTC, Jason wrote:
>>
>>
>>
>> On Wed, Aug 22, 2018 at 4:43 PM  wrote:
>>>
>>>
>>>
>>> On Tuesday, August 21, 2018 at 3:22:04 PM UTC, Jason wrote:
>>>>
>>>>
>>>>
>>>> On Tue, Aug 21, 2018 at 1:16 AM  wrote:
>>>>>
>>>>> I've been looking at the Wiki article on this topic. I find that I
>>>>> really don't understand what it is, or why it's important. Maybe a few
>>>>> succinct words from the usual suspects can be of help. TIA.
>>>>>
>>>>>
>>>>
>>>>
>>>> Bruno provided a great definition and background of the Church-Turing
>>>> Thesis. I will try to answer why it is important and comes up often in our
>>>> discussion.
>>>>
>>>>
>>>> The Church-Turing thesis says that anything that is computable is
>>>> computable by any computer.  In other words, there is nothing that the
>>>> computer in your cell phone can't compute, that your laptop or that a super
>>>> computer (or even a quantum computer) can.  It just comes down to having
>>>> enough time and memory.
>>>>
>>>> This is why you don't need to buy a new phone with new hardware every
>>>> time you want to install a new app.  Regardless of the type of CPU in your
>>>> phone, it can be extended in its power of what it might compute only given
>>>> some new software.  It is in this sense that computers are "Universal", 
>>>> they
>>>> are universal in the same sense that of a universal remote, or in the sense
>>>> that a record player is a universal sound imitating device.  A record 
>>>> player
>>>> might emulate the sounds of an orchestra, Britney Spears, whale songs, 
>>>> etc.,
>>>> all it needs is the appropriate record and it can produce the sound.
>>>>
>>>> In the same sense, all a Turing Machine (computer) needs to imitate (or
>>>> emulate) the right program or function is the right software.  Because of
>>>> this, anything that can be described in software, be it a brain emulation,
>>>> an AI, a virtual environment, a virtual machine or operating system, can
>>>> never know what hardware is running it, because the Church-Turing thesis
>>>> says that any computer is capable of running it.
>>>>
>>>> This is why if consciousness is computable (the computational theory of
>>>> mind) we cannot know what is computing us (e.g. we could be in a matrix 
>>>> type
>>>> simulation for all we know).  The other implication is that if computations
>>>> exist in mathematics (and they do), then we exist within mathematics.
>>>> Mathematics (or at least the part necessary to describe computations)
>>>> becomes the fundamental science of what we experience and what is possible
>>>> to experience or what we may predict about our future experiences 
>>>> (physics).
>>>>
>>>>
>>>> Jason
>>>
>>>
>>> If someone digitizes (emulates) the Mona Lisa, is this equivalent to the
>>> Mona Lisa?
>>
>>
>> If you digitize a person and put the digitized Mona Lisa before them, it
>> is equivalent to the real Mona Lisa to that person, at least as far as they
>> can tell.
>>
>>
>>>
>>> Can you write a function which is not computable? AG
>>>
>>>
>>
>> If by not computable you mean it never returns, then this is easy:
>>
>> function foo():
>>   while (true)
>>   {
>>  // loop forever
>>   }
>>
>> There are also programs for which no one knows if they are computable or
>> not.  If you can prove whether or not this function ever completes, you will
>> be world famous, and may even earn a million dollars (though I think the
>> prize has been retracted, it might be oferred again):
>>
>> Step 1: Set X = 4
>> Step 2: Set R = 0
>> Step 3: For each Y from 1 to X, if both Y and (X – Y) are prime, set R = 1
>> Step 4: If R = 1, Set X = X + 2 and go to Step 2
>> Step 5: If R = 0, print X and halt
>>
>> All you have to prove is the computer either never gets to step 5 or that
>> it does get to step 5.  Mathematicians have been working on a related
>> problem for 300 years, no one has solved it yet.
>>
>>
>> Jason
&

Re: Church-Turing Thesis

[Bruno Marchal]

> On 24 Aug 2018, at 00:53, agrayson2...@gmail.com wrote:
> 
> 
> 
> On Thursday, August 23, 2018 at 5:55:33 PM UTC, agrays...@gmail.com wrote:
> 
> 
> On Thursday, August 23, 2018 at 3:28:13 PM UTC, Brent wrote:
> Why don't we all chip in an buy Alan a computer so he can look stuff up on 
> Wikipedia.
> 
> Brent
> 
> I will when you have the courtesy to explain your contradictory statements 
> about the instantaneous, infinite extent of the wf. Oh BTW, with your big 
> brain, I suppose it never occurred to you that I wanted to hear Bruno's 
> definition, which if experience is worth anything, could be wildly DIFFERENT 
> from Wiki. While you assess all that, why don't you go fuck yourself, and 
> then tell us how it felt. OK? AG
> 
> FWIW, comparing Bruno's description with Wiki, which was my intent, confirms, 
> at least for me, that the postulates of QM are easier to understand, even 
> though many of the defining functions of a Turing Machine are known to those 
> who have programmed modern computers, notwithstanding that the latter use 
> random access memory. I don't see why the use of RAM is decisively important 
> in distinguishing a Turing Machine from how modern computers are designed. AG 
>  


You are right. You can see a von Neumann computer as a Turing machine. As the 
set of symbols, and state are arbitrary, you can even see a brain as a Turing 
machine. That is why eventually Gödel accepted Turing’s argument for the 
Church’s thesis.

Note that the wikipedia is often bad on logic or on computation, ...not 
mentioning computationalism. 

Have you understood Cantor’s diagonal proof of the non enumerability of the set 
of infinite sequence, in my yesterday post. If not I can explain again, with 
different notation. There is a real surprise at the end of that thread, you 
will see (I think and hope).

Bruno




> 
> 
> On 8/22/2018 5:58 PM, John Clark wrote:
>> On Wed, Aug 22, 2018 at 8:26 PM, > wrote:
>> 
>> >> Yes, the Busy Beaver Function is not computable. We know that:
>> 
>> BB(1) =1
>> BB(2) =6
>> BB(3) =21
>> BB(4) =107
>> 
>> > You haven't *written* the function, just its alleged values for 1,2,3,4.  
>> > What is the function? 
>>  
>> 
>> Starting with a all zero tape BB(N) is the number of operations any N state 
>> Turing Machine performs after it writes the largest number of 1's and then 
>> halts. It is very important that it halt, some machines will go on forever 
>> but they don't count. For example we know for sure that BB(5) is at least 
>> 47,176,870 because one 5 state Turing Machine has been found that halts 
>> after it goes through 47,176,870 operations (and prints 4098 1’s on the 
>> tape), but there are 28 other 5 state machines displaying non-regular 
>> behavior that are well past 47,176,870 operations and 4098 1's. If one of 
>> them eventually halts then that larger number of operations will be BB(5), 
>> if none of them ever halts then 47,176,870 really is BB(5); but the trouble 
>> is we'll never be able to know it’s 47,176,870 because we'll never know that 
>> none of those other 28 5 state machines will never halt because the Halting 
>> problem is insolvable.
>> 
>> 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-li...@googlegroups.com <>.
>> To post to this group, send email to everyth...@googlegroups.com <>.
>> Visit this group at https://groups.google.com/group/everything-list 
>> .
>> For more options, visit 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 
> .

-- 
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.

Re: Church-Turing Thesis

[Russell Standish]

On Thu, Aug 23, 2018 at 08:47:12AM -0700, Brent Meeker wrote:
> 
> 
> On 8/22/2018 7:01 PM, Jason Resch wrote:
> > There are also programs for which no one knows if they are computable or
> > not.  If you can prove whether or not this function ever completes, you
> > will be world famous, and may even earn a million dollars (though I
> > think the prize has been retracted, it might be oferred again):
> > 
> > Step 1: Set X = 4
> > Step 2: Set R = 0
> > Step 3: For each Y from 1 to X, if both Y and (X – Y) are prime, set R = 1
> > Step 4: If R = 1, Set X = X + 2 and go to Step 2
> > Step 5: If R = 0, print X and halt
> > 
> > All you have to prove is the computer either never gets to step 5 or
> > that it does get to step 5.  Mathematicians have been working on a
> > related problem for 300 years, no one has solved it yet.
> 
> X=6 so go to Step 2 and Set R=0
> When Y=2 and (X-Y)=4 they are not both prime. Leave R=0.
> Go to step 5 print 6 and halt.

I read step 3 as a loop, ie check all Y from 1 to X (actually 1 to X/2
will suffice) before moving to step 4. In your example, the loop will
check Y=3, and (X-Y)=3, so R=1, and so step 4 mean X=X+2 and step 2 is
executed again.

IIUC, if the twin primes conjecture were true, then the above program
will never halt, but I could be wrong on that.

Cheers
-- 


Dr Russell StandishPhone 0425 253119 (mobile)
Principal, High Performance Coders
Visiting Senior Research Fellowhpco...@hpcoders.com.au
Economics, Kingston University http://www.hpcoders.com.au


-- 
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.

Re: Church-Turing Thesis

[agrayson2000]

On Thursday, August 23, 2018 at 10:53:05 PM UTC, agrays...@gmail.com wrote:
>
>
>
> On Thursday, August 23, 2018 at 5:55:33 PM UTC, agrays...@gmail.com wrote:
>>
>>
>>
>> On Thursday, August 23, 2018 at 3:28:13 PM UTC, Brent wrote:
>>>
>>> Why don't we all chip in an buy Alan a computer so he can look stuff up 
>>> on Wikipedia.
>>>
>>> Brent
>>>
>>
>> *I will when you have the courtesy to explain your contradictory 
>> statements about the instantaneous, infinite extent of the wf. Oh BTW, with 
>> your big brain, I suppose it never occurred to you that I wanted to hear 
>> Bruno's definition, which if experience is worth anything, could be wildly 
>> DIFFERENT from Wiki. While you assess all that, why don't you go fuck 
>> yourself, and then tell us how it felt. OK? AG*
>>
>
> *FWIW, comparing Bruno's description with Wiki, which was my intent, 
> confirms, at least for me, that the postulates of QM are easier to 
> understand, even though many of the defining functions of a Turing Machine 
> are known to those who have programmed modern computers, notwithstanding 
> that the latter use random access memory. I don't see why the use of RAM is 
> decisively important in distinguishing a Turing Machine from how modern 
> computers are designed. AG*  
>


*For example, instead of a "tape" as used when Alan Turing was active, one 
can substitute the instruction pointer, a register that advances with each 
clock pulse, which points to the next executable instruction, where the 
latter are sequentially resident in RAM. AG *

>
>>
>>> On 8/22/2018 5:58 PM, John Clark wrote:
>>>
>>> On Wed, Aug 22, 2018 at 8:26 PM,  wrote:
>>>
>>> >>
> Yes, the Busy Beaver Function is not computable. We know that: 
>
> BB(1) =1
> BB(2) =6
> BB(3) =21
> BB(4) =107
>

 * > You haven't *written* the function, just its alleged values for 
 1,2,3,4.  What is the function? *

>>>  
>>>
>>> Starting with a all zero tape BB(N) is the number of operations any N 
>>> state Turing Machine performs after it writes the largest number of 1's and 
>>> then halts. It is very important that it halt, some machines will go on 
>>> forever but they don't count. For example we know for sure that BB(5) is at 
>>> least 47,176,870 because one 5 state Turing Machine has been found that 
>>> halts after it goes through 47,176,870 operations (and prints 4098 1’s on 
>>> the tape), but there are 28 other 5 state machines displaying non-regular 
>>> behavior that are well past 47,176,870 operations and 4098 1's. If one of 
>>> them eventually halts then that larger number of operations will be BB(5), 
>>> if none of them ever halts then 47,176,870 really is BB(5); but the trouble 
>>> is we'll never be able to know it’s 47,176,870 because we'll never know 
>>> that none of those other 28 5 state machines will never halt because the 
>>> Halting problem is insolvable.
>>>
>>> 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-li...@googlegroups.com.
>>> To post to this group, send email to everyth...@googlegroups.com.
>>> Visit this group at https://groups.google.com/group/everything-list.
>>> For more options, visit 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.

Re: Church-Turing Thesis

[agrayson2000]

On Thursday, August 23, 2018 at 5:55:33 PM UTC, agrays...@gmail.com wrote:
>
>
>
> On Thursday, August 23, 2018 at 3:28:13 PM UTC, Brent wrote:
>>
>> Why don't we all chip in an buy Alan a computer so he can look stuff up 
>> on Wikipedia.
>>
>> Brent
>>
>
> *I will when you have the courtesy to explain your contradictory 
> statements about the instantaneous, infinite extent of the wf. Oh BTW, with 
> your big brain, I suppose it never occurred to you that I wanted to hear 
> Bruno's definition, which if experience is worth anything, could be wildly 
> DIFFERENT from Wiki. While you assess all that, why don't you go fuck 
> yourself, and then tell us how it felt. OK? AG*
>

*FWIW, comparing Bruno's description with Wiki, which was my intent, 
confirms, at least for me, that the postulates of QM are easier to 
understand, even though many of the defining functions of a Turing Machine 
are known to those who have programmed modern computers, notwithstanding 
that the latter use random access memory. I don't see why the use of RAM is 
decisively important in distinguishing a Turing Machine from how modern 
computers are designed. AG*  

>
>
>> On 8/22/2018 5:58 PM, John Clark wrote:
>>
>> On Wed, Aug 22, 2018 at 8:26 PM,  wrote:
>>
>> >>
 Yes, the Busy Beaver Function is not computable. We know that: 

 BB(1) =1
 BB(2) =6
 BB(3) =21
 BB(4) =107

>>>
>>> * > You haven't *written* the function, just its alleged values for 
>>> 1,2,3,4.  What is the function? *
>>>
>>  
>>
>> Starting with a all zero tape BB(N) is the number of operations any N 
>> state Turing Machine performs after it writes the largest number of 1's and 
>> then halts. It is very important that it halt, some machines will go on 
>> forever but they don't count. For example we know for sure that BB(5) is at 
>> least 47,176,870 because one 5 state Turing Machine has been found that 
>> halts after it goes through 47,176,870 operations (and prints 4098 1’s on 
>> the tape), but there are 28 other 5 state machines displaying non-regular 
>> behavior that are well past 47,176,870 operations and 4098 1's. If one of 
>> them eventually halts then that larger number of operations will be BB(5), 
>> if none of them ever halts then 47,176,870 really is BB(5); but the trouble 
>> is we'll never be able to know it’s 47,176,870 because we'll never know 
>> that none of those other 28 5 state machines will never halt because the 
>> Halting problem is insolvable.
>>
>> 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-li...@googlegroups.com.
>> To post to this group, send email to everyth...@googlegroups.com.
>> Visit this group at https://groups.google.com/group/everything-list.
>> For more options, visit 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.

Re: Church-Turing Thesis

[agrayson2000]

On Thursday, August 23, 2018 at 3:28:13 PM UTC, Brent wrote:
>
> Why don't we all chip in an buy Alan a computer so he can look stuff up on 
> Wikipedia.
>
> Brent
>

*I will when you have the courtesy to explain your contradictory statements 
about the instantaneous, infinite extent of the wf. Oh BTW, with you big 
brain, I suppose it never occurred to you that I wanted to hear Bruno's 
definition, which if experience is worth anything, could be wildly 
DIFFERENT from Wiki. While you assess all that, why don't you go fuck 
yourself, and then tell us how it felt. OK? AG* 

>
> On 8/22/2018 5:58 PM, John Clark wrote:
>
> On Wed, Aug 22, 2018 at 8:26 PM, > 
> wrote:
>
> >>
>>> Yes, the Busy Beaver Function is not computable. We know that: 
>>>
>>> BB(1) =1
>>> BB(2) =6
>>> BB(3) =21
>>> BB(4) =107
>>>
>>
>> * > You haven't *written* the function, just its alleged values for 
>> 1,2,3,4.  What is the function? *
>>
>  
>
> Starting with a all zero tape BB(N) is the number of operations any N 
> state Turing Machine performs after it writes the largest number of 1's and 
> then halts. It is very important that it halt, some machines will go on 
> forever but they don't count. For example we know for sure that BB(5) is at 
> least 47,176,870 because one 5 state Turing Machine has been found that 
> halts after it goes through 47,176,870 operations (and prints 4098 1’s on 
> the tape), but there are 28 other 5 state machines displaying non-regular 
> behavior that are well past 47,176,870 operations and 4098 1's. If one of 
> them eventually halts then that larger number of operations will be BB(5), 
> if none of them ever halts then 47,176,870 really is BB(5); but the trouble 
> is we'll never be able to know it’s 47,176,870 because we'll never know 
> that none of those other 28 5 state machines will never halt because the 
> Halting problem is insolvable.
>
> 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-li...@googlegroups.com .
> To post to this group, send email to everyth...@googlegroups.com 
> .
> Visit this group at https://groups.google.com/group/everything-list.
> For more options, visit 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.

Re: Church-Turing Thesis

[Brent Meeker]

On 8/22/2018 7:01 PM, Jason Resch wrote:
There are also programs for which no one knows if they are computable 
or not.  If you can prove whether or not this function ever completes, 
you will be world famous, and may even earn a million dollars (though 
I think the prize has been retracted, it might be oferred again):


Step 1: Set X = 4
Step 2: Set R = 0
Step 3: For each Y from 1 to X, if both Y and (X – Y) are prime, set R = 1
Step 4: If R = 1, Set X = X + 2 and go to Step 2
Step 5: If R = 0, print X and halt

All you have to prove is the computer either never gets to step 5 or 
that it does get to step 5.  Mathematicians have been working on a 
related problem for 300 years, no one has solved it yet.


X=6 so go to Step 2 and Set R=0
When Y=2 and (X-Y)=4 they are not both prime. Leave R=0.
Go to step 5 print 6 and halt.

Brent


--
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.

Re: Church-Turing Thesis

[Brent Meeker]

Why don't we all chip in an buy Alan a computer so he can look stuff up 
on Wikipedia.


Brent

On 8/22/2018 5:58 PM, John Clark wrote:
On Wed, Aug 22, 2018 at 8:26 PM, >wrote:


>>
Yes, the Busy Beaver Function is not computable. We know that:

BB(1) =1
BB(2) =6
BB(3) =21
BB(4) =107


*/
>
You haven't *written* the function, just its alleged values for
1,2,3,4.  What is the function? /*


Starting with a all zero tape BB(N) is the number of operations any N 
state Turing Machine performs after it writes the largest number of 
1's and then halts. It is very important that it halt, some machines 
will go on forever but they don't count. For example we know for sure 
that BB(5) is at least 47,176,870 because one 5 state Turing Machine 
has been found that halts after it goes through 47,176,870 operations 
(and prints 4098 1’s on the tape), but there are 28 other 5 state 
machines displaying non-regular behavior that are well past 47,176,870 
operations and 4098 1's. If one of them eventually halts then that 
larger number of operations will be BB(5), if none of them ever halts 
then 47,176,870 really is BB(5); but the trouble is we'll never be 
able to know it’s 47,176,870 because we'll never know that none of 
those other 28 5 state machines will never halt because the Halting 
problem is insolvable.


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 
.
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.


--
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.

Re: Church-Turing Thesis

[Bruno Marchal]

ame class of functions from N to N.

If there are no two quadruples beginning with the same qi Sj, the machine is 
said deterministic. If not, the machine is said non deterministic.

You can enumerate all Turing machine TM1, TM2, TM3, TM4, … (OK?-

A universal Turing machine is a Turing machine (i.e. finite set quadruplets) 
such that if two numbers are put on its tape, like 12 and 2 below (numbers are 
coded here by 0, 1, 2, …. = 1, 11, 111, …)

101110…

then it will mimic exactly the 12th Turing machine TM12 on the argument 111.

That has been discovered by Post and Kleene independently (ye, Post discovered 
the Turing machine too).



>  
> Post did already,declared that a function is computable if and only if it is 
> computable in his formal definition (Post production system). Post too 
> understood that it was a postulate of high importance. Later it was proved 
> that a function is Post-calculable iff it is Turing calculable, iff it is 
> Church calculable, making all those thesis equivalent.
> 
> Please elaborate. AG 


I will elaborate on this later, but it just means that Turing and Post have 
given very different notion of computability, but then prove their equivalence. 




> 
> So the Church-Post-Kleene-Turing-markov … thesis is that a function (always 
> from N to N) is intuitively (human) computable if and only if it is 
> computable by any of those formal system.
> 
> Please elaborate. AG 


A function is computable means, intuitively, that we can explain (in a finite 
time) how to compute it (in a finite time for each argument).

Unlike provability and definability, which depends on the choice of the 
theory/formalism, computability is the same whatever formalism is used. A 
modern day physical computer is a physical implementation of such formalism, 
and they too compute always the same class of functions. More on this later.




> 
> Gödel will disbelieve in Church thesis, and miss it, despite proving that 
> arithmetic emulates all computable functions, but he was not sure he get them 
> all. Only after reading Turing, will Gödel accept the Church Turing thesis, 
> and thus definition of computable function.
> 
> Please elaborate. AG 


Gödel find hard to believe that we obtained a absolute definition of 
computability. He was the guy showing that this does not exist for provability, 
nor definability. But he will be convinced by his reading of Turing. Despite he 
made the big part of the job, he missed the Church-Turing thesis. He could have 
claimed the contrary, because he get very close to it in a footnote of one of 
his paper, but very honestly declined this honour and admit to have missed it. 
He considered it as a sort of miracle, and he is right on this. The closure of 
computable function for Cantor-like diagonal is indeed the most extraordinary 
fact I have ever lived in my life. I will try to share why later. It took me 
also much time before I accept it.



> 
> Do you know Cantor theorem? Do you know the theorem asserting that the set of 
> functions from N to N (or from N to {0, 1}) is not enumerable?
> .
> Are you referring to Cantor's diagonal proof that the rationals are 
> countable? I've seen that.


Not really. I was referring to cantor’s diagonal proof that the irrationals are 
NOT countable.



> I can believe the latter comment, and can see it's not easy to prove. AG 

The countability of the rationals is easy. The non countability of the reals is 
less easy, but still rather easy.

I will come back on this.



> 
> If yes, I will show you that the Church Turing thesis entails incompleteness 
> of al all formal system rather easily. If no, I will send more explanation.
> 
> Have you tried to follow the thread of the combinators.
> 
> No. AG

I suggest you do. It is a very fundamental theory, at the base of all 
programming languages, practically and theoretically. It is also very simple 
(once we get the notation right).




>  
> This is again a formal system capable of defining all computable functions. 
> So, Church-thesis is equivalent with “all intuitively computable functions 
> are computable by combinators”. I will prove this.
> 
> Tell me if this helped, I am not sure of your background.
> 
> Still pretty vague. I have a BA & MA in mathematics, and an MS in physics, 
> respectively from Cornell University, The University of Michigan, and 
> Northeastern University,  AG 


I suggest you read the combinators thread, or wait for my post on Church thesis.

If you want, you can play the role of the candid guy, in which case I send much 
shorter post, and you answer by saying "OK, I get it", or by “Don’t get it”, 
and I try another explanation.

Computability theory is far more easy than quantum mechanics, and eventually as 
much astonishing (and with mechanism, it becomes ul

Re: Church-Turing Thesis

[agrayson2000]

On Thursday, August 23, 2018 at 2:01:24 AM UTC, Jason wrote:
>
>
>
> On Wed, Aug 22, 2018 at 4:43 PM > wrote:
>
>>
>>
>> On Tuesday, August 21, 2018 at 3:22:04 PM UTC, Jason wrote:
>>>
>>>
>>>
>>> On Tue, Aug 21, 2018 at 1:16 AM  wrote:
>>>
>>>> I've been looking at the Wiki article on this topic. I find that I 
>>>> really don't understand what it is, or why it's important. Maybe a few 
>>>> succinct words from the usual suspects can be of help. TIA.
>>>>
>>>>
>>>>
>>>
>>> Bruno provided a great definition and background of the Church-Turing 
>>> Thesis. I will try to answer why it is important and comes up often in our 
>>> discussion.
>>>
>>>
>>> The Church-Turing thesis says that anything that is computable is 
>>> computable by any computer.  In other words, there is nothing that the 
>>> computer in your cell phone can't compute, that your laptop or that a super 
>>> computer (or even a quantum computer) can.  It just comes down to having 
>>> enough time and memory.
>>>
>>> This is why you don't need to buy a new phone with new hardware every 
>>> time you want to install a new app.  Regardless of the type of CPU in your 
>>> phone, it can be extended in its power of what it might compute only given 
>>> some new software.  It is in this sense that computers are "Universal", 
>>> they are universal in the same sense that of a universal remote, or in the 
>>> sense that a record player is a universal sound imitating device.  A record 
>>> player might emulate the sounds of an orchestra, Britney Spears, whale 
>>> songs, etc., all it needs is the appropriate record and it can produce the 
>>> sound.
>>>
>>> In the same sense, all a Turing Machine (computer) needs to imitate (or 
>>> emulate) the right program or function is the right software.  Because of 
>>> this, anything that can be described in software, be it a brain emulation, 
>>> an AI, a virtual environment, a virtual machine or operating system, can 
>>> never know what hardware is running it, because the Church-Turing thesis 
>>> says that any computer is capable of running it.
>>>
>>> This is why if consciousness is computable (the computational theory of 
>>> mind) we cannot know what is computing us (e.g. we could be in a matrix 
>>> type simulation for all we know).  The other implication is that if 
>>> computations exist in mathematics (and they do), then we exist within 
>>> mathematics.  Mathematics (or at least the part necessary to describe 
>>> computations) becomes the fundamental science of what we experience and 
>>> what is possible to experience or what we may predict about our future 
>>> experiences (physics).
>>>
>>>
>>> Jason
>>>
>>
>> If someone digitizes (emulates) the Mona Lisa, is this equivalent to the 
>> Mona Lisa? 
>>
>
> If you digitize a person and put the digitized Mona Lisa before them, it 
> is equivalent to the real Mona Lisa to that person, at least as far as they 
> can tell.
>
>  
>
>> Can you write a function which is not computable? AG 
>>
>>
>>
> If by not computable you mean it never returns, then this is easy:
>
> function foo():
>   while (true)
>   {
>  // loop forever
>   }
>  
> There are also programs for which no one knows if they are computable or 
> not.  If you can prove whether or not this function ever completes, you 
> will be world famous, and may even earn a million dollars (though I think 
> the prize has been retracted, it might be oferred again):
>
> Step 1: Set X = 4
> Step 2: Set R = 0
> Step 3: For each Y from 1 to X, if both Y and (X – Y) are prime, set R = 1
> Step 4: If R = 1, Set X = X + 2 and go to Step 2
> Step 5: If R = 0, print X and halt
>
> All you have to prove is the computer either never gets to step 5 or that 
> it does get to step 5.  Mathematicians have been working on a related 
> problem for 300 years, no one has solved it yet.
>
>
> Jason
>

*I was asking about a well-defined mathematical function that can be 
written in closed form, or possibly as an infinite series. I believe that 
all such functions are computable. I was not discussing subroutines that 
might never terminate. If all well defined mathematical functions are 
computable, why did computability become a big deal? AG *

-- 
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.

Re: Church-Turing Thesis

[Jason Resch]

On Wed, Aug 22, 2018 at 4:43 PM  wrote:

>
>
> On Tuesday, August 21, 2018 at 3:22:04 PM UTC, Jason wrote:
>>
>>
>>
>> On Tue, Aug 21, 2018 at 1:16 AM  wrote:
>>
>>> I've been looking at the Wiki article on this topic. I find that I
>>> really don't understand what it is, or why it's important. Maybe a few
>>> succinct words from the usual suspects can be of help. TIA.
>>>
>>>
>>>
>>
>> Bruno provided a great definition and background of the Church-Turing
>> Thesis. I will try to answer why it is important and comes up often in our
>> discussion.
>>
>>
>> The Church-Turing thesis says that anything that is computable is
>> computable by any computer.  In other words, there is nothing that the
>> computer in your cell phone can't compute, that your laptop or that a super
>> computer (or even a quantum computer) can.  It just comes down to having
>> enough time and memory.
>>
>> This is why you don't need to buy a new phone with new hardware every
>> time you want to install a new app.  Regardless of the type of CPU in your
>> phone, it can be extended in its power of what it might compute only given
>> some new software.  It is in this sense that computers are "Universal",
>> they are universal in the same sense that of a universal remote, or in the
>> sense that a record player is a universal sound imitating device.  A record
>> player might emulate the sounds of an orchestra, Britney Spears, whale
>> songs, etc., all it needs is the appropriate record and it can produce the
>> sound.
>>
>> In the same sense, all a Turing Machine (computer) needs to imitate (or
>> emulate) the right program or function is the right software.  Because of
>> this, anything that can be described in software, be it a brain emulation,
>> an AI, a virtual environment, a virtual machine or operating system, can
>> never know what hardware is running it, because the Church-Turing thesis
>> says that any computer is capable of running it.
>>
>> This is why if consciousness is computable (the computational theory of
>> mind) we cannot know what is computing us (e.g. we could be in a matrix
>> type simulation for all we know).  The other implication is that if
>> computations exist in mathematics (and they do), then we exist within
>> mathematics.  Mathematics (or at least the part necessary to describe
>> computations) becomes the fundamental science of what we experience and
>> what is possible to experience or what we may predict about our future
>> experiences (physics).
>>
>>
>> Jason
>>
>
> If someone digitizes (emulates) the Mona Lisa, is this equivalent to the
> Mona Lisa?
>

If you digitize a person and put the digitized Mona Lisa before them, it is
equivalent to the real Mona Lisa to that person, at least as far as they
can tell.



> Can you write a function which is not computable? AG
>
>
>
If by not computable you mean it never returns, then this is easy:

function foo():
  while (true)
  {
 // loop forever
  }

There are also programs for which no one knows if they are computable or
not.  If you can prove whether or not this function ever completes, you
will be world famous, and may even earn a million dollars (though I think
the prize has been retracted, it might be oferred again):

Step 1: Set X = 4
Step 2: Set R = 0
Step 3: For each Y from 1 to X, if both Y and (X – Y) are prime, set R = 1
Step 4: If R = 1, Set X = X + 2 and go to Step 2
Step 5: If R = 0, print X and halt

All you have to prove is the computer either never gets to step 5 or that
it does get to step 5.  Mathematicians have been working on a related
problem for 300 years, no one has solved it yet.


Jason

-- 
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.

Re: Church-Turing Thesis

[John Clark]

On Wed, Aug 22, 2018 at 8:26 PM,  wrote:

>>
>> Yes, the Busy Beaver Function is not computable. We know that:
>>
>> BB(1) =1
>> BB(2) =6
>> BB(3) =21
>> BB(4) =107
>>
>
> *>You haven't *written* the function, just its alleged values for
> 1,2,3,4.  What is the function? *
>


Starting with a all zero tape BB(N) is the number of operations any N state
Turing Machine performs after it writes the largest number of 1's and then
halts. It is very important that it halt, some machines will go on forever
but they don't count. For example we know for sure that BB(5) is at least
47,176,870 because one 5 state Turing Machine has been found that halts
after it goes through 47,176,870 operations (and prints 4098 1’s on the
tape), but there are 28 other 5 state machines displaying non-regular
behavior that are well past 47,176,870 operations and 4098 1's. If one of
them eventually halts then that larger number of operations will be BB(5),
if none of them ever halts then 47,176,870 really is BB(5); but the trouble
is we'll never be able to know it’s 47,176,870 because we'll never know
that none of those other 28 5 state machines will never halt because the
Halting problem is insolvable.

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.
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.

Re: Church-Turing Thesis

[agrayson2000]

On Wednesday, August 22, 2018 at 11:05:15 PM UTC, John Clark wrote:
>
> On Wed, Aug 22, 2018 at 5:43 PM, > 
> wrote:
>
> >
>> *Can you write a function which is not computable? *
>
>
> Yes, the Busy Beaver Function is not computable. We know that:
>
> BB(1) =1
> BB(2) =6
> BB(3) =21
> BB(4) =107
>

*You haven't *written* the function, just its alleged values for 1,2,3,4.  
What is the function? AG*

>
> But those are the only values we've be able to calculate with certainty, 
> the problem is the Busy Beaver function grows faster than any computable 
> function. We suspect that BB(5) is 47,176,870 but are far from certain and 
> BB(6) is at least 7.4*10^36534 and BB(7) is at least 10^10^10^10^10^7 but 
> could be much larger. Big as they are all Busy Beaver numbers are finite 
> but after a certain point they are not computable and nobody even knows 
> exactly where that point is. It has been proven that BB(7918) is not 
> computable but what is the smallest non computable-number? Nobody knows but 
> I wouldn't be surprised if it were BB(5).
>
> 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.
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.

Re: Church-Turing Thesis

[John Clark]

On Wed, Aug 22, 2018 at 5:43 PM,  wrote:

>
> *Can you write a function which is not computable? *


Yes, the Busy Beaver Function is not computable. We know that:

BB(1) =1
BB(2) =6
BB(3) =21
BB(4) =107

But those are the only values we've be able to calculate with certainty,
the problem is the Busy Beaver function grows faster than any computable
function. We suspect that BB(5) is 47,176,870 but are far from certain and
BB(6) is at least 7.4*10^36534 and BB(7) is at least 10^10^10^10^10^7 but
could be much larger. Big as they are all Busy Beaver numbers are finite
but after a certain point they are not computable and nobody even knows
exactly where that point is. It has been proven that BB(7918) is not
computable but what is the smallest non computable-number? Nobody knows but
I wouldn't be surprised if it were BB(5).

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.
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.

Re: Church-Turing Thesis

[agrayson2000]

On Tuesday, August 21, 2018 at 3:22:04 PM UTC, Jason wrote:
>
>
>
> On Tue, Aug 21, 2018 at 1:16 AM > wrote:
>
>> I've been looking at the Wiki article on this topic. I find that I really 
>> don't understand what it is, or why it's important. Maybe a few succinct 
>> words from the usual suspects can be of help. TIA.
>>
>>
>>
>
> Bruno provided a great definition and background of the Church-Turing 
> Thesis. I will try to answer why it is important and comes up often in our 
> discussion.
>
>
> The Church-Turing thesis says that anything that is computable is 
> computable by any computer.  In other words, there is nothing that the 
> computer in your cell phone can't compute, that your laptop or that a super 
> computer (or even a quantum computer) can.  It just comes down to having 
> enough time and memory.
>
> This is why you don't need to buy a new phone with new hardware every time 
> you want to install a new app.  Regardless of the type of CPU in your 
> phone, it can be extended in its power of what it might compute only given 
> some new software.  It is in this sense that computers are "Universal", 
> they are universal in the same sense that of a universal remote, or in the 
> sense that a record player is a universal sound imitating device.  A record 
> player might emulate the sounds of an orchestra, Britney Spears, whale 
> songs, etc., all it needs is the appropriate record and it can produce the 
> sound.
>
> In the same sense, all a Turing Machine (computer) needs to imitate (or 
> emulate) the right program or function is the right software.  Because of 
> this, anything that can be described in software, be it a brain emulation, 
> an AI, a virtual environment, a virtual machine or operating system, can 
> never know what hardware is running it, because the Church-Turing thesis 
> says that any computer is capable of running it.
>
> This is why if consciousness is computable (the computational theory of 
> mind) we cannot know what is computing us (e.g. we could be in a matrix 
> type simulation for all we know).  The other implication is that if 
> computations exist in mathematics (and they do), then we exist within 
> mathematics.  Mathematics (or at least the part necessary to describe 
> computations) becomes the fundamental science of what we experience and 
> what is possible to experience or what we may predict about our future 
> experiences (physics).
>
>
> Jason
>

If someone digitizes (emulates) the Mona Lisa, is this equivalent to the 
Mona Lisa? Can you write a function which is not computable? AG 

-- 
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.

Re: Church-Turing Thesis

[agrayson2000]

On Tuesday, August 21, 2018 at 9:59:30 AM UTC, Bruno Marchal wrote:
>
>
> On 21 Aug 2018, at 08:16, agrays...@gmail.com  wrote:
>
> I've been looking at the Wiki article on this topic. I find that I really 
> don't understand what it is, or why it's important. Maybe a few succinct 
> words from the usual suspects can be of help. TIA.
>
>
>
> Actually, I have very recently wrote a long post on exactly this (Church’s 
> thesis), but I have decided to first explain the combinators …
>
> Here I give you a simple explanation of what is Church’s thesis (also 
> called Post thesis, Kleene’s thesis, Turing’s thesis, or very often now; 
> the Church’s Turing thesis).
>
> Do you know hat is a function? Do you know what is a function from N to N 
> (where N is the set of natural numbers, i.e. N = {0, 1, 2, 3, …}).
>

*Yes, They're correspondences between two sets; many-to-one, one-to-one, 
but never one-to many. AG *

>
> Now the set of all functions from N to N is very big, and big sets led 
> often to paradoxes, so people have tried to restrict the notion of 
> function, and one of the restriction has consisted in the “computable 
> function”.
>
> Intuitively, a computable function is a function (from N to N) for which 
> we can explain how to compute it (in a finite time, on its finite argument, 
> and the idea is that the explanation to compute the function have to be 
> encodable in a finite way).
>

*Any subtle problems computing a simple polynomial or trigonometric 
function?  AG*

>
> For example, most functions studied by mathematicians are obviously 
> computable, and it is easy to convince oneself that a function is 
> (intuitively) computable. But people sought a precise definition of 
> computable.
>
> Church invented the “lambda calculus” formalism for that effect, like 
> independently Turing invented the Turing (digital) machine for that effect.
>
> Church just defined a computable function by one that we can encode in his 
> lambda calculus. It is his student Kleene who understood that it is has  to 
> be thesis (overlapping philosophy and mathematics). In fact Kleene will see 
> that the existence of universal formalism entails incompleteness 
> quasi-directly.
>
> Turing just defined a computable function by a function computable by a 
> machine, but he saw too that this was a philosophical thesis.
>
> Turing showed, nevertheless the first equivalence theorem: a function is 
> computable by a Turing machine if and only if it is computable by a lambda 
> calculus expression (or a combinator).
>
> *What is a Turing machine? AG*
 

> Post did already,declared that a function is computable if and only if it 
> is computable in his formal definition (Post production system). Post too 
> understood that it was a postulate of high importance. Later it was proved 
> that a function is Post-calculable iff it is Turing calculable, iff it is 
> Church calculable, making all those thesis equivalent.
>

*Please elaborate. AG* 

>
> So the Church-Post-Kleene-Turing-markov … thesis is that a function 
> (always from N to N) is intuitively (human) computable if and only if it is 
> computable by any of those formal system.
>


*Please elaborate. AG *

>
> Gödel will disbelieve in Church thesis, and miss it, despite proving that 
> arithmetic emulates all computable functions, but he was not sure he get 
> them all. Only after reading Turing, will Gödel accept the Church Turing 
> thesis, and thus definition of computable function.
>

*Please elaborate. AG* 

>
> Do you know Cantor theorem? Do you know the theorem asserting that the set 
> of functions from N to N (or from N to {0, 1}) is not enumerable?
>
.
*Are you referring to Cantor's diagonal proof that the rationals are 
countable? I've seen that. I can believe the latter comment, and can see 
it's not easy to prove. AG *

>
> If yes, I will show you that the Church Turing thesis entails 
> incompleteness of al all formal system rather easily. If no, I will send 
> more explanation.
>
> Have you tried to follow the thread of the combinators.
>

*No. AG*
 

> This is again a formal system capable of defining all computable 
> functions. So, Church-thesis is equivalent with “all intuitively computable 
> functions are computable by combinators”. I will prove this.
>
> Tell me if this helped, I am not sure of your background.
>

*Still pretty vague. I have a BA & MA in mathematics, and an MS in physics, 
respectively from Cornell University, The University of Michigan, and 
Northeastern University,  AG *

>
> Bruno
>
>
>
>
>
>
>
>
> -- 
> You received this message because you are subscribed to the Google Groups 
> "Everything List" group.
>

Re: Church-Turing Thesis

[Jason Resch]

On Tue, Aug 21, 2018 at 1:16 AM  wrote:

> I've been looking at the Wiki article on this topic. I find that I really
> don't understand what it is, or why it's important. Maybe a few succinct
> words from the usual suspects can be of help. TIA.
>
>
>

Bruno provided a great definition and background of the Church-Turing
Thesis. I will try to answer why it is important and comes up often in our
discussion.


The Church-Turing thesis says that anything that is computable is
computable by any computer.  In other words, there is nothing that the
computer in your cell phone can't compute, that your laptop or that a super
computer (or even a quantum computer) can.  It just comes down to having
enough time and memory.

This is why you don't need to buy a new phone with new hardware every time
you want to install a new app.  Regardless of the type of CPU in your
phone, it can be extended in its power of what it might compute only given
some new software.  It is in this sense that computers are "Universal",
they are universal in the same sense that of a universal remote, or in the
sense that a record player is a universal sound imitating device.  A record
player might emulate the sounds of an orchestra, Britney Spears, whale
songs, etc., all it needs is the appropriate record and it can produce the
sound.

In the same sense, all a Turing Machine (computer) needs to imitate (or
emulate) the right program or function is the right software.  Because of
this, anything that can be described in software, be it a brain emulation,
an AI, a virtual environment, a virtual machine or operating system, can
never know what hardware is running it, because the Church-Turing thesis
says that any computer is capable of running it.

This is why if consciousness is computable (the computational theory of
mind) we cannot know what is computing us (e.g. we could be in a matrix
type simulation for all we know).  The other implication is that if
computations exist in mathematics (and they do), then we exist within
mathematics.  Mathematics (or at least the part necessary to describe
computations) becomes the fundamental science of what we experience and
what is possible to experience or what we may predict about our future
experiences (physics).


Jason

-- 
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.

Re: Church-Turing Thesis

[Bruno Marchal]

> On 21 Aug 2018, at 08:16, agrayson2...@gmail.com wrote:
> 
> I've been looking at the Wiki article on this topic. I find that I really 
> don't understand what it is, or why it's important. Maybe a few succinct 
> words from the usual suspects can be of help. TIA.


Actually, I have very recently wrote a long post on exactly this (Church’s 
thesis), but I have decided to first explain the combinators …

Here I give you a simple explanation of what is Church’s thesis (also called 
Post thesis, Kleene’s thesis, Turing’s thesis, or very often now; the Church’s 
Turing thesis).

Do you know hat is a function? Do you know what is a function from N to N 
(where N is the set of natural numbers, i.e. N = {0, 1, 2, 3, …}).

Now the set of all functions from N to N is very big, and big sets led often to 
paradoxes, so people have tried to restrict the notion of function, and one of 
the restriction has consisted in the “computable function”.

Intuitively, a computable function is a function (from N to N) for which we can 
explain how to compute it (in a finite time, on its finite argument, and the 
idea is that the explanation to compute the function have to be encodable in a 
finite way).

For example, most functions studied by mathematicians are obviously computable, 
and it is easy to convince oneself that a function is (intuitively) computable. 
But people sought a precise definition of computable.

Church invented the “lambda calculus” formalism for that effect, like 
independently Turing invented the Turing (digital) machine for that effect.

Church just defined a computable function by one that we can encode in his 
lambda calculus. It is his student Kleene who understood that it is has  to be 
thesis (overlapping philosophy and mathematics). In fact Kleene will see that 
the existence of universal formalism entails incompleteness quasi-directly.

Turing just defined a computable function by a function computable by a 
machine, but he saw too that this was a philosophical thesis.

Turing showed, nevertheless the first equivalence theorem: a function is 
computable by a Turing machine if and only if it is computable by a lambda 
calculus expression (or a combinator).

Post did already,declared that a function is computable if and only if it is 
computable in his formal definition (Post production system). Post too 
understood that it was a postulate of high importance. Later it was proved that 
a function is Post-calculable iff it is Turing calculable, iff it is Church 
calculable, making all those thesis equivalent.

So the Church-Post-Kleene-Turing-markov … thesis is that a function (always 
from N to N) is intuitively (human) computable if and only if it is computable 
by any of those formal system.

Gödel will disbelieve in Church thesis, and miss it, despite proving that 
arithmetic emulates all computable functions, but he was not sure he get them 
all. Only after reading Turing, will Gödel accept the Church Turing thesis, and 
thus definition of computable function.

Do you know Cantor theorem? Do you know the theorem asserting that the set of 
functions from N to N (or from N to {0, 1}) is not enumerable?

If yes, I will show you that the Church Turing thesis entails incompleteness of 
al all formal system rather easily. If no, I will send more explanation.

Have you tried to follow the thread of the combinators. This is again a formal 
system capable of defining all computable functions. So, Church-thesis is 
equivalent with “all intuitively computable functions are computable by 
combinators”. I will prove this.

Tell me if this helped, I am not sure of your background.

Bruno







> 
> -- 
> 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.

Church-Turing Thesis

[agrayson2000]

I've been looking at the Wiki article on this topic. I find that I really 
don't understand what it is, or why it's important. Maybe a few succinct 
words from the usual suspects can be of help. TIA.

-- 
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.

Re: Will boson-sampling ever disprove the Extended Church-Turing thesis?

[Bruno Marchal]

On 03 Nov 2014, at 16:02, yanniru wrote:


This recent paper may be of interest: http://arxiv.org/pdf/1401.2199.pdf



I wish this can work.

Note, though, that the extended Church thesis has few relationships  
with the usual Church thesis (also called Church-Turing thesis) which  
is not related with efficiency.


Bruno










--
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 http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.


http://iridia.ulb.ac.be/~marchal/



--
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 http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.

Will boson-sampling ever disprove the Extended Church-Turing thesis?

[yanniru]

This recent paper may be of interest: http://arxiv.org/pdf/1401.2199.pdf





-- 
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 http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.

Re: Why the Church-Turing thesis?

[benjayk]

Quentin Anciaux-2 wrote:
 
 2012/9/11 Quentin Anciaux allco...@gmail.com
 


 2012/9/11 benjayk benjamin.jaku...@googlemail.com



 Quentin Anciaux-2 wrote:
 
  2012/9/11 benjayk benjamin.jaku...@googlemail.com
 
 
 
  Quentin Anciaux-2 wrote:
  
   2012/9/11 benjayk benjamin.jaku...@googlemail.com
  
  
  
   Quentin Anciaux-2 wrote:
   
2012/9/10 benjayk benjamin.jaku...@googlemail.com
   
   
   
  No program can determine its hardware.  This is a
 consequence
  of
   the
  Church
  Turing thesis.  The particular machine at the lowest level
 has
  no
 bearing
  (from the program's perspective).
 If that is true, we can show that CT must be false, because
 we
  *can*
 define
 a meta-program that has access to (part of) its own
 hardware
   (which
 still
 is intuitively computable - we can even implement it on a
  computer).

   
It's false, the program *can't* know that the hardware it has
  access
   to
is
the *real* hardware and not a simulated hardware. The program
 has
  only
access to hardware through IO, and it can't tell (as never
 ever)
  from
that
interface if what's outside is the *real* outside or simulated
   outside.
\quote
Yes that is true. If anything it is true because the hardware
 is
  not
   even
clearly determined at the base level (quantum uncertainty).
I should have expressed myself more accurately and written 
   hardware
   
or
relative 'hardware'. We can define a (meta-)programs that
 have
   access
to
their hardware in the sense of knowing what they are running
 on
relative
to some notion of hardware. They cannot be emulated using
  universal
turing
machines
   
   
Then it's not a program if it can't run on a universal turing
  machine.
   
   The funny thing is, it *can* run on a universal turing machine.
 Just
  that
   it
   may lose relative correctness if we do that.
  
  
   Then you must be wrong... I don't understand your point. If it's a
  program
   it has access to the outside through IO, hence it is impossible
 for a
   program to differentiate real outside from simulated outside...
 It's
  a
   simple fact, so either you're wrong or what you're describing is
 not
 a
   program, not an algorithm and not a computation.
  OK, it depends on what you mean by program. If you presume that a
  program
  can't access its hardware,
 
 
  I *do not presume it*... it's a *fact*.
 
 
 Well, I presented a model of a program that can do that (on some level,
 not
 on the level of physical hardware), and is a program in the most
 fundamental
 way (doing step-by-step execution of instructions).
 All you need is a program hierarchy where some programs have access to
 programs that are below them in the hierarchy (which are the hardware
 though not the *hardware*).


 What's your point ? How the simulated hardware would fail ? It's
 impossible, so until you're clearer (your point is totally fuzzy), I
 stick
 to you must be wrong.

 
 So either you assume some kind of oracle device, in this case, the thing
 you describe is no more a program, but a program + an oracle, the oracle
 obviously is not simulable on a turing machine, or an infinite regress of
 level.
 
 
The simulated hardware can't fail in the model, just like a turing machine
can't fail. Of course in reality it can fail, that is beside the point.

You are right, my explanation is not that clear, because it is a quite
subtle thing.

Maybe I shouldn't have used the word hardware. The point is just that we
can define (meta-)programs that have access to some aspect of programs that
are below it on the program hierarchy (normal programs), that can't be
accessed by the program themselves. They can't emulated in general, because
sometimes the emulating program will necessarily emulate the wrong level
(because it can't correctly emulate that the meta-program is accessing what
it is *actually* doing on the most fundamental level).
They still are programs in the most fundamental sense.

They don't require oracles or something else that is hard to actually use,
they just have to know something about the hierarchy and the programs
involved (which programs or kind of programs are above or below it) and have
access to the states of other programs. Both are perfectly implementable on
a normal computer. They can even be implemented on a turing machine, but not
in general. They can also be simulated on turing machines, just not
necessarily correctly (the turing machine may incorrectly ignore which level
it is operating on relative to the meta-program).

We can still argue that these aren't programs in every sense but I think
what is executable on a normal computer can be rightfully called program.

benayk
-- 
View this message in context: 
http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34423089.html
Sent from the Everything List mailing list archive at Nabble.com.

-- 
You received this message

Re: Why the Church-Turing thesis?

[Quentin Anciaux]

2012/9/12 benjayk benjamin.jaku...@googlemail.com



 Quentin Anciaux-2 wrote:
 
  2012/9/11 Quentin Anciaux allco...@gmail.com
 
 
 
  2012/9/11 benjayk benjamin.jaku...@googlemail.com
 
 
 
  Quentin Anciaux-2 wrote:
  
   2012/9/11 benjayk benjamin.jaku...@googlemail.com
  
  
  
   Quentin Anciaux-2 wrote:
   
2012/9/11 benjayk benjamin.jaku...@googlemail.com
   
   
   
Quentin Anciaux-2 wrote:

 2012/9/10 benjayk benjamin.jaku...@googlemail.com



   No program can determine its hardware.  This is a
  consequence
   of
the
   Church
   Turing thesis.  The particular machine at the lowest level
  has
   no
  bearing
   (from the program's perspective).
  If that is true, we can show that CT must be false, because
  we
   *can*
  define
  a meta-program that has access to (part of) its own
  hardware
(which
  still
  is intuitively computable - we can even implement it on a
   computer).
 

 It's false, the program *can't* know that the hardware it has
   access
to
 is
 the *real* hardware and not a simulated hardware. The program
  has
   only
 access to hardware through IO, and it can't tell (as never
  ever)
   from
 that
 interface if what's outside is the *real* outside or simulated
outside.
 \quote
 Yes that is true. If anything it is true because the hardware
  is
   not
even
 clearly determined at the base level (quantum uncertainty).
 I should have expressed myself more accurately and written 
hardware

 or
 relative 'hardware'. We can define a (meta-)programs that
  have
access
 to
 their hardware in the sense of knowing what they are running
  on
 relative
 to some notion of hardware. They cannot be emulated using
   universal
 turing
 machines


 Then it's not a program if it can't run on a universal turing
   machine.

The funny thing is, it *can* run on a universal turing machine.
  Just
   that
it
may lose relative correctness if we do that.
   
   
Then you must be wrong... I don't understand your point. If it's a
   program
it has access to the outside through IO, hence it is impossible
  for a
program to differentiate real outside from simulated outside...
  It's
   a
simple fact, so either you're wrong or what you're describing is
  not
  a
program, not an algorithm and not a computation.
   OK, it depends on what you mean by program. If you presume that a
   program
   can't access its hardware,
  
  
   I *do not presume it*... it's a *fact*.
  
  
  Well, I presented a model of a program that can do that (on some level,
  not
  on the level of physical hardware), and is a program in the most
  fundamental
  way (doing step-by-step execution of instructions).
  All you need is a program hierarchy where some programs have access to
  programs that are below them in the hierarchy (which are the hardware
  though not the *hardware*).
 
 
  What's your point ? How the simulated hardware would fail ? It's
  impossible, so until you're clearer (your point is totally fuzzy), I
  stick
  to you must be wrong.
 
 
  So either you assume some kind of oracle device, in this case, the
 thing
  you describe is no more a program, but a program + an oracle, the oracle
  obviously is not simulable on a turing machine, or an infinite regress of
  level.
 
 
 The simulated hardware can't fail in the model, just like a turing machine
 can't fail. Of course in reality it can fail, that is beside the point.

 You are right, my explanation is not that clear, because it is a quite
 subtle thing.

 Maybe I shouldn't have used the word hardware. The point is just that we
 can define (meta-)programs that have access to some aspect of programs that
 are below it on the program hierarchy (normal programs), that can't be
 accessed by the program themselves. They can't emulated in general, because
 sometimes the emulating program will necessarily emulate the wrong level
 (because it can't correctly emulate that the meta-program is accessing what
 it is *actually* doing on the most fundamental level).
 They still are programs in the most fundamental sense.

 They don't require oracles or something else that is hard to actually use,
 they just have to know something about the hierarchy and the programs
 involved (which programs or kind of programs are above or below it) and
 have
 access to the states of other programs. Both are perfectly implementable on
 a normal computer. They can even be implemented on a turing machine, but
 not
 in general. They can also be simulated on turing machines, just not
 necessarily correctly (the turing machine may incorrectly ignore which
 level
 it is operating on relative to the meta-program).


I still don't see why, what you describe is wishful thinking, or you're
wrong, or you can't explain correctly, what I understand from what you
write, is that you

Re: Why the Church-Turing thesis?

[Quentin Anciaux]

2012/9/12 Quentin Anciaux allco...@gmail.com



 2012/9/12 benjayk benjamin.jaku...@googlemail.com



 Quentin Anciaux-2 wrote:
 
  2012/9/11 Quentin Anciaux allco...@gmail.com
 
 
 
  2012/9/11 benjayk benjamin.jaku...@googlemail.com
 
 
 
  Quentin Anciaux-2 wrote:
  
   2012/9/11 benjayk benjamin.jaku...@googlemail.com
  
  
  
   Quentin Anciaux-2 wrote:
   
2012/9/11 benjayk benjamin.jaku...@googlemail.com
   
   
   
Quentin Anciaux-2 wrote:

 2012/9/10 benjayk benjamin.jaku...@googlemail.com



   No program can determine its hardware.  This is a
  consequence
   of
the
   Church
   Turing thesis.  The particular machine at the lowest
 level
  has
   no
  bearing
   (from the program's perspective).
  If that is true, we can show that CT must be false, because
  we
   *can*
  define
  a meta-program that has access to (part of) its own
  hardware
(which
  still
  is intuitively computable - we can even implement it on a
   computer).
 

 It's false, the program *can't* know that the hardware it has
   access
to
 is
 the *real* hardware and not a simulated hardware. The program
  has
   only
 access to hardware through IO, and it can't tell (as never
  ever)
   from
 that
 interface if what's outside is the *real* outside or
 simulated
outside.
 \quote
 Yes that is true. If anything it is true because the hardware
  is
   not
even
 clearly determined at the base level (quantum uncertainty).
 I should have expressed myself more accurately and written 
hardware

 or
 relative 'hardware'. We can define a (meta-)programs that
  have
access
 to
 their hardware in the sense of knowing what they are
 running
  on
 relative
 to some notion of hardware. They cannot be emulated using
   universal
 turing
 machines


 Then it's not a program if it can't run on a universal turing
   machine.

The funny thing is, it *can* run on a universal turing machine.
  Just
   that
it
may lose relative correctness if we do that.
   
   
Then you must be wrong... I don't understand your point. If it's
 a
   program
it has access to the outside through IO, hence it is impossible
  for a
program to differentiate real outside from simulated outside...
  It's
   a
simple fact, so either you're wrong or what you're describing is
  not
  a
program, not an algorithm and not a computation.
   OK, it depends on what you mean by program. If you presume that a
   program
   can't access its hardware,
  
  
   I *do not presume it*... it's a *fact*.
  
  
  Well, I presented a model of a program that can do that (on some
 level,
  not
  on the level of physical hardware), and is a program in the most
  fundamental
  way (doing step-by-step execution of instructions).
  All you need is a program hierarchy where some programs have access to
  programs that are below them in the hierarchy (which are the
 hardware
  though not the *hardware*).
 
 
  What's your point ? How the simulated hardware would fail ? It's
  impossible, so until you're clearer (your point is totally fuzzy), I
  stick
  to you must be wrong.
 
 
  So either you assume some kind of oracle device, in this case, the
 thing
  you describe is no more a program, but a program + an oracle, the oracle
  obviously is not simulable on a turing machine, or an infinite regress
 of
  level.
 
 
 The simulated hardware can't fail in the model, just like a turing machine
 can't fail. Of course in reality it can fail, that is beside the point.

 You are right, my explanation is not that clear, because it is a quite
 subtle thing.

 Maybe I shouldn't have used the word hardware. The point is just that we
 can define (meta-)programs that have access to some aspect of programs
 that
 are below it on the program hierarchy (normal programs), that can't be
 accessed by the program themselves. They can't emulated in general,
 because
 sometimes the emulating program will necessarily emulate the wrong level
 (because it can't correctly emulate that the meta-program is accessing
 what
 it is *actually* doing on the most fundamental level).
 They still are programs in the most fundamental sense.

 They don't require oracles or something else that is hard to actually use,
 they just have to know something about the hierarchy and the programs
 involved (which programs or kind of programs are above or below it) and
 have
 access to the states of other programs. Both are perfectly implementable
 on
 a normal computer. They can even be implemented on a turing machine, but
 not
 in general. They can also be simulated on turing machines, just not
 necessarily correctly (the turing machine may incorrectly ignore which
 level
 it is operating on relative to the meta-program).


 I still don't see why, what you describe is wishful thinking, or you're
 wrong, or you can't explain

Re: Why the Church-Turing thesis?

[benjayk]

Quentin Anciaux-2 wrote:
 
 2012/9/10 benjayk benjamin.jaku...@googlemail.com
 


   No program can determine its hardware.  This is a consequence of the
   Church
   Turing thesis.  The particular machine at the lowest level has no
  bearing
   (from the program's perspective).
  If that is true, we can show that CT must be false, because we *can*
  define
  a meta-program that has access to (part of) its own hardware (which
  still
  is intuitively computable - we can even implement it on a computer).
 

 It's false, the program *can't* know that the hardware it has access to
 is
 the *real* hardware and not a simulated hardware. The program has only
 access to hardware through IO, and it can't tell (as never ever) from
 that
 interface if what's outside is the *real* outside or simulated outside.
 \quote
 Yes that is true. If anything it is true because the hardware is not even
 clearly determined at the base level (quantum uncertainty).
 I should have expressed myself more accurately and written  hardware 
 or
 relative 'hardware'. We can define a (meta-)programs that have access
 to
 their hardware in the sense of knowing what they are running on
 relative
 to some notion of hardware. They cannot be emulated using universal
 turing
 machines
 
 
 Then it's not a program if it can't run on a universal turing machine.
 
The funny thing is, it *can* run on a universal turing machine. Just that it
may lose relative correctness if we do that. We can still use a turing
machine to run it and interpret what the result means.

So for all intents and purposes it is quite like a program. Maybe not a
program as such, OK, but it certainly can be used precisely in a
step-by-step manner, and I think this is what CT thesis means by
algorithmically computable.
Maybe not, but in this case CT is just a statement about specific forms of
algorithms.

-- 
View this message in context: 
http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417440.html
Sent from the Everything List mailing list archive at Nabble.com.

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[Quentin Anciaux]

2012/9/11 benjayk benjamin.jaku...@googlemail.com



 Quentin Anciaux-2 wrote:
 
  2012/9/10 benjayk benjamin.jaku...@googlemail.com
 
 
 
No program can determine its hardware.  This is a consequence of the
Church
Turing thesis.  The particular machine at the lowest level has no
   bearing
(from the program's perspective).
   If that is true, we can show that CT must be false, because we *can*
   define
   a meta-program that has access to (part of) its own hardware (which
   still
   is intuitively computable - we can even implement it on a computer).
  
 
  It's false, the program *can't* know that the hardware it has access to
  is
  the *real* hardware and not a simulated hardware. The program has only
  access to hardware through IO, and it can't tell (as never ever) from
  that
  interface if what's outside is the *real* outside or simulated outside.
  \quote
  Yes that is true. If anything it is true because the hardware is not
 even
  clearly determined at the base level (quantum uncertainty).
  I should have expressed myself more accurately and written  hardware
 
  or
  relative 'hardware'. We can define a (meta-)programs that have access
  to
  their hardware in the sense of knowing what they are running on
  relative
  to some notion of hardware. They cannot be emulated using universal
  turing
  machines
 
 
  Then it's not a program if it can't run on a universal turing machine.
 
 The funny thing is, it *can* run on a universal turing machine. Just that
 it
 may lose relative correctness if we do that.


Then you must be wrong... I don't understand your point. If it's a program
it has access to the outside through IO, hence it is impossible for a
program to differentiate real outside from simulated outside... It's a
simple fact, so either you're wrong or what you're describing is not a
program, not an algorithm and not a computation.

Quentin


 We can still use a turing
 machine to run it and interpret what the result means.

 So for all intents and purposes it is quite like a program. Maybe not a
 program as such, OK, but it certainly can be used precisely in a
 step-by-step manner, and I think this is what CT thesis means by
 algorithmically computable.
 Maybe not, but in this case CT is just a statement about specific forms of
 algorithms.

 --
 View this message in context:
 http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417440.html
 Sent from the Everything List mailing list archive at Nabble.com.

 --
 You received this message because you are subscribed to the Google Groups
 Everything List group.
 To post to this group, send email to everything-list@googlegroups.com.
 To unsubscribe from this group, send email to
 everything-list+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/everything-list?hl=en.




-- 
All those moments will be lost in time, like tears in rain.

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[benjayk]

Quentin Anciaux-2 wrote:
 
 2012/9/11 benjayk benjamin.jaku...@googlemail.com
 


 Quentin Anciaux-2 wrote:
 
  2012/9/10 benjayk benjamin.jaku...@googlemail.com
 
 
 
No program can determine its hardware.  This is a consequence of
 the
Church
Turing thesis.  The particular machine at the lowest level has no
   bearing
(from the program's perspective).
   If that is true, we can show that CT must be false, because we *can*
   define
   a meta-program that has access to (part of) its own hardware
 (which
   still
   is intuitively computable - we can even implement it on a computer).
  
 
  It's false, the program *can't* know that the hardware it has access
 to
  is
  the *real* hardware and not a simulated hardware. The program has only
  access to hardware through IO, and it can't tell (as never ever) from
  that
  interface if what's outside is the *real* outside or simulated
 outside.
  \quote
  Yes that is true. If anything it is true because the hardware is not
 even
  clearly determined at the base level (quantum uncertainty).
  I should have expressed myself more accurately and written 
 hardware
 
  or
  relative 'hardware'. We can define a (meta-)programs that have
 access
  to
  their hardware in the sense of knowing what they are running on
  relative
  to some notion of hardware. They cannot be emulated using universal
  turing
  machines
 
 
  Then it's not a program if it can't run on a universal turing machine.
 
 The funny thing is, it *can* run on a universal turing machine. Just that
 it
 may lose relative correctness if we do that.
 
 
 Then you must be wrong... I don't understand your point. If it's a program
 it has access to the outside through IO, hence it is impossible for a
 program to differentiate real outside from simulated outside... It's a
 simple fact, so either you're wrong or what you're describing is not a
 program, not an algorithm and not a computation.
OK, it depends on what you mean by program. If you presume that a program
can't access its hardware, then what I am describing is indeed not a
program.

But most definitions don't preclude that. Carrying out instructions
precisely and step-by-step can be done with or without access to your
hardware.

Anyway, meta-programs can be instantiated using real computer (a program
can, in principle, know and utilize part of a more basic computational layer
if programmed correctly), so we at least know that real computers are beyond
turing machines.

benjayk

-- 
View this message in context: 
http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417676.html
Sent from the Everything List mailing list archive at Nabble.com.

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[Quentin Anciaux]

2012/9/11 benjayk benjamin.jaku...@googlemail.com



 Quentin Anciaux-2 wrote:
 
  2012/9/11 benjayk benjamin.jaku...@googlemail.com
 
 
 
  Quentin Anciaux-2 wrote:
  
   2012/9/10 benjayk benjamin.jaku...@googlemail.com
  
  
  
 No program can determine its hardware.  This is a consequence of
  the
 Church
 Turing thesis.  The particular machine at the lowest level has no
bearing
 (from the program's perspective).
If that is true, we can show that CT must be false, because we
 *can*
define
a meta-program that has access to (part of) its own hardware
  (which
still
is intuitively computable - we can even implement it on a
 computer).
   
  
   It's false, the program *can't* know that the hardware it has access
  to
   is
   the *real* hardware and not a simulated hardware. The program has
 only
   access to hardware through IO, and it can't tell (as never ever) from
   that
   interface if what's outside is the *real* outside or simulated
  outside.
   \quote
   Yes that is true. If anything it is true because the hardware is not
  even
   clearly determined at the base level (quantum uncertainty).
   I should have expressed myself more accurately and written 
  hardware
  
   or
   relative 'hardware'. We can define a (meta-)programs that have
  access
   to
   their hardware in the sense of knowing what they are running on
   relative
   to some notion of hardware. They cannot be emulated using universal
   turing
   machines
  
  
   Then it's not a program if it can't run on a universal turing machine.
  
  The funny thing is, it *can* run on a universal turing machine. Just
 that
  it
  may lose relative correctness if we do that.
 
 
  Then you must be wrong... I don't understand your point. If it's a
 program
  it has access to the outside through IO, hence it is impossible for a
  program to differentiate real outside from simulated outside... It's a
  simple fact, so either you're wrong or what you're describing is not a
  program, not an algorithm and not a computation.
 OK, it depends on what you mean by program. If you presume that a program
 can't access its hardware,


I *do not presume it*... it's a *fact*.

Quentin


 then what I am describing is indeed not a
 program.

 But most definitions don't preclude that. Carrying out instructions
 precisely and step-by-step can be done with or without access to your
 hardware.

 Anyway, meta-programs can be instantiated using real computer (a program
 can, in principle, know and utilize part of a more basic computational
 layer
 if programmed correctly), so we at least know that real computers are
 beyond
 turing machines.

 benjayk

 --
 View this message in context:
 http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417676.html
 Sent from the Everything List mailing list archive at Nabble.com.

 --
 You received this message because you are subscribed to the Google Groups
 Everything List group.
 To post to this group, send email to everything-list@googlegroups.com.
 To unsubscribe from this group, send email to
 everything-list+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/everything-list?hl=en.




-- 
All those moments will be lost in time, like tears in rain.

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[benjayk]

Quentin Anciaux-2 wrote:
 
 2012/9/11 benjayk benjamin.jaku...@googlemail.com
 


 Quentin Anciaux-2 wrote:
 
  2012/9/11 benjayk benjamin.jaku...@googlemail.com
 
 
 
  Quentin Anciaux-2 wrote:
  
   2012/9/10 benjayk benjamin.jaku...@googlemail.com
  
  
  
 No program can determine its hardware.  This is a consequence
 of
  the
 Church
 Turing thesis.  The particular machine at the lowest level has
 no
bearing
 (from the program's perspective).
If that is true, we can show that CT must be false, because we
 *can*
define
a meta-program that has access to (part of) its own hardware
  (which
still
is intuitively computable - we can even implement it on a
 computer).
   
  
   It's false, the program *can't* know that the hardware it has
 access
  to
   is
   the *real* hardware and not a simulated hardware. The program has
 only
   access to hardware through IO, and it can't tell (as never ever)
 from
   that
   interface if what's outside is the *real* outside or simulated
  outside.
   \quote
   Yes that is true. If anything it is true because the hardware is
 not
  even
   clearly determined at the base level (quantum uncertainty).
   I should have expressed myself more accurately and written 
  hardware
  
   or
   relative 'hardware'. We can define a (meta-)programs that have
  access
   to
   their hardware in the sense of knowing what they are running on
   relative
   to some notion of hardware. They cannot be emulated using
 universal
   turing
   machines
  
  
   Then it's not a program if it can't run on a universal turing
 machine.
  
  The funny thing is, it *can* run on a universal turing machine. Just
 that
  it
  may lose relative correctness if we do that.
 
 
  Then you must be wrong... I don't understand your point. If it's a
 program
  it has access to the outside through IO, hence it is impossible for a
  program to differentiate real outside from simulated outside... It's
 a
  simple fact, so either you're wrong or what you're describing is not a
  program, not an algorithm and not a computation.
 OK, it depends on what you mean by program. If you presume that a
 program
 can't access its hardware,
 
 
 I *do not presume it*... it's a *fact*.
 
 
Well, I presented a model of a program that can do that (on some level, not
on the level of physical hardware), and is a program in the most fundamental
way (doing step-by-step execution of instructions).
All you need is a program hierarchy where some programs have access to
programs that are below them in the hierarchy (which are the hardware
though not the *hardware*).

So apparently it is not so much a fact about programs in a common sense way,
but about a narrow conception of what programs can be.

benjayk
-- 
View this message in context: 
http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417762.html
Sent from the Everything List mailing list archive at Nabble.com.

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[Quentin Anciaux]

2012/9/11 benjayk benjamin.jaku...@googlemail.com



 Quentin Anciaux-2 wrote:
 
  2012/9/11 benjayk benjamin.jaku...@googlemail.com
 
 
 
  Quentin Anciaux-2 wrote:
  
   2012/9/11 benjayk benjamin.jaku...@googlemail.com
  
  
  
   Quentin Anciaux-2 wrote:
   
2012/9/10 benjayk benjamin.jaku...@googlemail.com
   
   
   
  No program can determine its hardware.  This is a consequence
  of
   the
  Church
  Turing thesis.  The particular machine at the lowest level has
  no
 bearing
  (from the program's perspective).
 If that is true, we can show that CT must be false, because we
  *can*
 define
 a meta-program that has access to (part of) its own hardware
   (which
 still
 is intuitively computable - we can even implement it on a
  computer).

   
It's false, the program *can't* know that the hardware it has
  access
   to
is
the *real* hardware and not a simulated hardware. The program has
  only
access to hardware through IO, and it can't tell (as never ever)
  from
that
interface if what's outside is the *real* outside or simulated
   outside.
\quote
Yes that is true. If anything it is true because the hardware is
  not
   even
clearly determined at the base level (quantum uncertainty).
I should have expressed myself more accurately and written 
   hardware
   
or
relative 'hardware'. We can define a (meta-)programs that have
   access
to
their hardware in the sense of knowing what they are running on
relative
to some notion of hardware. They cannot be emulated using
  universal
turing
machines
   
   
Then it's not a program if it can't run on a universal turing
  machine.
   
   The funny thing is, it *can* run on a universal turing machine. Just
  that
   it
   may lose relative correctness if we do that.
  
  
   Then you must be wrong... I don't understand your point. If it's a
  program
   it has access to the outside through IO, hence it is impossible for
 a
   program to differentiate real outside from simulated outside... It's
  a
   simple fact, so either you're wrong or what you're describing is not a
   program, not an algorithm and not a computation.
  OK, it depends on what you mean by program. If you presume that a
  program
  can't access its hardware,
 
 
  I *do not presume it*... it's a *fact*.
 
 
 Well, I presented a model of a program that can do that (on some level, not
 on the level of physical hardware), and is a program in the most
 fundamental
 way (doing step-by-step execution of instructions).
 All you need is a program hierarchy where some programs have access to
 programs that are below them in the hierarchy (which are the hardware
 though not the *hardware*).


What's your point ? How the simulated hardware would fail ? It's
impossible, so until you're clearer (your point is totally fuzzy), I stick
to you must be wrong.


 So apparently it is not so much a fact about programs in a common sense
 way,
 but about a narrow conception of what programs can be.

 benjayk
 --
 View this message in context:
 http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417762.html
 Sent from the Everything List mailing list archive at Nabble.com.

 --
 You received this message because you are subscribed to the Google Groups
 Everything List group.
 To post to this group, send email to everything-list@googlegroups.com.
 To unsubscribe from this group, send email to
 everything-list+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/everything-list?hl=en.




-- 
All those moments will be lost in time, like tears in rain.

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[Quentin Anciaux]

2012/9/11 Quentin Anciaux allco...@gmail.com



 2012/9/11 benjayk benjamin.jaku...@googlemail.com



 Quentin Anciaux-2 wrote:
 
  2012/9/11 benjayk benjamin.jaku...@googlemail.com
 
 
 
  Quentin Anciaux-2 wrote:
  
   2012/9/11 benjayk benjamin.jaku...@googlemail.com
  
  
  
   Quentin Anciaux-2 wrote:
   
2012/9/10 benjayk benjamin.jaku...@googlemail.com
   
   
   
  No program can determine its hardware.  This is a consequence
  of
   the
  Church
  Turing thesis.  The particular machine at the lowest level
 has
  no
 bearing
  (from the program's perspective).
 If that is true, we can show that CT must be false, because we
  *can*
 define
 a meta-program that has access to (part of) its own hardware
   (which
 still
 is intuitively computable - we can even implement it on a
  computer).

   
It's false, the program *can't* know that the hardware it has
  access
   to
is
the *real* hardware and not a simulated hardware. The program has
  only
access to hardware through IO, and it can't tell (as never ever)
  from
that
interface if what's outside is the *real* outside or simulated
   outside.
\quote
Yes that is true. If anything it is true because the hardware is
  not
   even
clearly determined at the base level (quantum uncertainty).
I should have expressed myself more accurately and written 
   hardware
   
or
relative 'hardware'. We can define a (meta-)programs that have
   access
to
their hardware in the sense of knowing what they are running on
relative
to some notion of hardware. They cannot be emulated using
  universal
turing
machines
   
   
Then it's not a program if it can't run on a universal turing
  machine.
   
   The funny thing is, it *can* run on a universal turing machine. Just
  that
   it
   may lose relative correctness if we do that.
  
  
   Then you must be wrong... I don't understand your point. If it's a
  program
   it has access to the outside through IO, hence it is impossible
 for a
   program to differentiate real outside from simulated outside...
 It's
  a
   simple fact, so either you're wrong or what you're describing is not
 a
   program, not an algorithm and not a computation.
  OK, it depends on what you mean by program. If you presume that a
  program
  can't access its hardware,
 
 
  I *do not presume it*... it's a *fact*.
 
 
 Well, I presented a model of a program that can do that (on some level,
 not
 on the level of physical hardware), and is a program in the most
 fundamental
 way (doing step-by-step execution of instructions).
 All you need is a program hierarchy where some programs have access to
 programs that are below them in the hierarchy (which are the hardware
 though not the *hardware*).


 What's your point ? How the simulated hardware would fail ? It's
 impossible, so until you're clearer (your point is totally fuzzy), I stick
 to you must be wrong.


So either you assume some kind of oracle device, in this case, the thing
you describe is no more a program, but a program + an oracle, the oracle
obviously is not simulable on a turing machine, or an infinite regress of
level.

Halting problem is not new, I still don't see your point or something new
here.

Quentin


 So apparently it is not so much a fact about programs in a common sense
 way,
 but about a narrow conception of what programs can be.

 benjayk
 --
 View this message in context:
 http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417762.html
 Sent from the Everything List mailing list archive at Nabble.com.

 --
 You received this message because you are subscribed to the Google Groups
 Everything List group.
 To post to this group, send email to everything-list@googlegroups.com.
 To unsubscribe from this group, send email to
 everything-list+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/everything-list?hl=en.




 --
 All those moments will be lost in time, like tears in rain.




-- 
All those moments will be lost in time, like tears in rain.

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[benjayk]

  No program can determine its hardware.  This is a consequence of the
  Church
  Turing thesis.  The particular machine at the lowest level has no
 bearing
  (from the program's perspective).
 If that is true, we can show that CT must be false, because we *can*
 define
 a meta-program that has access to (part of) its own hardware (which
 still
 is intuitively computable - we can even implement it on a computer).


It's false, the program *can't* know that the hardware it has access to is
the *real* hardware and not a simulated hardware. The program has only
access to hardware through IO, and it can't tell (as never ever) from that
interface if what's outside is the *real* outside or simulated outside.
\quote
Yes that is true. If anything it is true because the hardware is not even
clearly determined at the base level (quantum uncertainty).
I should have expressed myself more accurately and written  hardware  or
relative 'hardware'. We can define a (meta-)programs that have access to
their hardware in the sense of knowing what they are running on relative
to some notion of hardware. They cannot be emulated using universal turing
machines (in general - in specific instances, where the hardware is fixed on
the right level, they might be). They can be simulated, though, but in this
case the simulation may be incorrect in the given context and we have to put
it into the right context to see what it is actually emulating (not the
meta-program itself, just its behaviour relative to some other context). 
 
We can also define an infinite hierarchy of meta-meta--programs (n
metas) to show that there is no universal notion of computation at all.
There is always a notion of computation that is more powerful than the
current one, because it can reflect more deeply upon its own hardware.

See my post concerning meta-programs for further details.
-- 
View this message in context: 
http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34413719.html
Sent from the Everything List mailing list archive at Nabble.com.

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[Quentin Anciaux]

2012/9/10 benjayk benjamin.jaku...@googlemail.com



   No program can determine its hardware.  This is a consequence of the
   Church
   Turing thesis.  The particular machine at the lowest level has no
  bearing
   (from the program's perspective).
  If that is true, we can show that CT must be false, because we *can*
  define
  a meta-program that has access to (part of) its own hardware (which
  still
  is intuitively computable - we can even implement it on a computer).
 

 It's false, the program *can't* know that the hardware it has access to is
 the *real* hardware and not a simulated hardware. The program has only
 access to hardware through IO, and it can't tell (as never ever) from that
 interface if what's outside is the *real* outside or simulated outside.
 \quote
 Yes that is true. If anything it is true because the hardware is not even
 clearly determined at the base level (quantum uncertainty).
 I should have expressed myself more accurately and written  hardware 
 or
 relative 'hardware'. We can define a (meta-)programs that have access to
 their hardware in the sense of knowing what they are running on relative
 to some notion of hardware. They cannot be emulated using universal
 turing
 machines


Then it's not a program if it can't run on a universal turing machine.


 (in general - in specific instances, where the hardware is fixed on
 the right level, they might be). They can be simulated, though, but in this
 case the simulation may be incorrect in the given context and we have to
 put
 it into the right context to see what it is actually emulating (not the
 meta-program itself, just its behaviour relative to some other context).

 We can also define an infinite hierarchy of meta-meta--programs (n
 metas) to show that there is no universal notion of computation at all.
 There is always a notion of computation that is more powerful than the
 current one, because it can reflect more deeply upon its own hardware.

 See my post concerning meta-programs for further details.
 --
 View this message in context:
 http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34413719.html
 Sent from the Everything List mailing list archive at Nabble.com.

 --
 You received this message because you are subscribed to the Google Groups
 Everything List group.
 To post to this group, send email to everything-list@googlegroups.com.
 To unsubscribe from this group, send email to
 everything-list+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/everything-list?hl=en.




-- 
All those moments will be lost in time, like tears in rain.

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[Stephen P. King]

On 9/10/2012 11:40 AM, benjayk wrote:



No program can determine its hardware.  This is a consequence of the
Church
Turing thesis.  The particular machine at the lowest level has no

bearing

(from the program's perspective).

If that is true, we can show that CT must be false, because we *can*
define
a meta-program that has access to (part of) its own hardware (which
still
is intuitively computable - we can even implement it on a computer).


It's false, the program *can't* know that the hardware it has access to is
the *real* hardware and not a simulated hardware. The program has only
access to hardware through IO, and it can't tell (as never ever) from that
interface if what's outside is the *real* outside or simulated outside.
\quote
Yes that is true. If anything it is true because the hardware is not even
clearly determined at the base level (quantum uncertainty).
I should have expressed myself more accurately and written  hardware  or
relative 'hardware'. We can define a (meta-)programs that have access to
their hardware in the sense of knowing what they are running on relative
to some notion of hardware. They cannot be emulated using universal turing
machines (in general - in specific instances, where the hardware is fixed on
the right level, they might be). They can be simulated, though, but in this
case the simulation may be incorrect in the given context and we have to put
it into the right context to see what it is actually emulating (not the
meta-program itself, just its behaviour relative to some other context).
  
We can also define an infinite hierarchy of meta-meta--programs (n

metas) to show that there is no universal notion of computation at all.
There is always a notion of computation that is more powerful than the
current one, because it can reflect more deeply upon its own hardware.

See my post concerning meta-programs for further details.

Dear benjayk,

Is there any means by which the resource requirements paly a role 
for a single program? No, because of this indeterminacy (the 1p 
indeterminacy) as Bruno has explained well. But while this is true, if 
you consider multiple computations that are accessing shared resources 
things are not so clear. I wish that some thought might be given to the 
problem of concurrency.


--
Onward!

Stephen

http://webpages.charter.net/stephenk1/Outlaw/Outlaw.html


--
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[Bruno Marchal]

On 07 Sep 2012, at 12:24, benjayk wrote:




Bruno Marchal wrote:



On 28 Aug 2012, at 21:57, benjayk wrote:



It seems that the Church-Turing thesis, that states that an
universal turing
machine can compute everything that is intuitively computable, has
near
universal acceptance among computer scientists.


Yes indeed. I think there are two strong arguments for this.

The empirical one: all attempts to define the set of computable
functions have led to the same class of functions, and this despite
the quite independent path leading to the definitions (from Church
lambda terms, Post production systems, von Neumann machine, billiard
ball, combinators, cellular automata ... up to modular functor,
quantum topologies, quantum computers, etc.).

OK, now I understand it better. Apparently if we express a  
computation in
terms of a computable function we can always arrive at the same  
computable

function using a different computation of an abitrary turing universal
machine. That seems right to me.

But in this case I don't get why it is often claimed that CT thesis  
claims
that all computations can be done by a universal turing machine, not  
merely
that they lead to the same class of computable functions (if  
converted

appriopiately).


This is due to a theorem applying to all universal programming  
language, or universal system. They all contain a universal machine.  
This makes CT equivalent with the thesis that there is a universal  
machine with respect to (intuitive) computability.


It entails also an intensional Church thesis. Not only all universal  
system can compute what each others can compute, but they can compute  
the function in the same manner. This comes from the fact that a game  
of life pattern (say) can exist and compute the universal function of  
some other universal system, like a lisp interpreter for example. This  
makes all result on computations working also on the notions of  
simulation and emulation.







The latter is a far weaker statement, since computable functions  
abstract

from many relevant things about the machine.

And even this weaker statement doesn't seem true with regards to more
powerful models like super-recursive functions, as computable  
functions just

give finite results, while super-recursive machine can give
infinite/unlimited results.


Computability concerns finite or infinite generable things.
Then you can weaken comp indeed, and many results remains valid, but  
are longer to prove. I use comp and numbers as it is easier.








Bruno Marchal wrote:


The conceptual one: the class of computable functions is closed for
the most transcendental operation in math: diagonalization. This is
not the case for the notions of definability, provability,
cardinality, etc.

I don't really know what this means. Do you mean that there are just
countable many computations? If yes, what has this do with whether all
universal turing machines are equivalent?


It means that the notion of computability, despite being epistemic, is  
well defined in math. It is the only such notion. The diagnonalization  
cannot been applied to find a new computable function already not in  
the class of the one given by any universal machine.
It makes comp far more explanatively close than any concept in math  
and physics.









Bruno Marchal wrote:




I really wonder why this is so, given that there are simple cases
where we
can compute something that an abitrary turing machine can not
compute using
a notion of computation that is not extraordinary at all (and quite
relevant
in reality).
For example, given you have a universal turing machine A that uses  
the
alphabet {1,0} and a universal turing machine B that uses the  
alphabet

{-1,0,1}.
Now it is quite clear that the machine A cannot directly answer any
questions that relates to -1. For example it cannot directly compute
-1*-1=1. Machine A can only be used to use an encoded input value  
and

encoded description of machine B, and give an output that is correct
given
the right decoding scheme.
But for me this already makes clear that machine A is less
computationally
powerful than machine B.


Church thesis concerns only the class of computable functions.
Hm, maybe the wikipedia article is a bad one, since it mentioned  
computable
functions just as means of explaining it, not as part of its  
definition.



Bruno Marchal wrote:


The  alphabet used by the Turing machine, having 1, 2, or enumerable
alphabet does not change the class. If you dovetail on the works of 1
letter Turing machine, you will unavoidably emulate all Turing
machines on all finite and enumerable letters alphabets. This can be
proved. Nor does the number of tapes, and/or  parallelism change that
class.
Of course, some machine can be very inefficient, but this, by
definition, does not concern Church thesis.
Even so, CT thesis makes a claim about the equivalence of machines,  
not of

emulability.


It does, by the intensional CT, which follows

Re: Why the Church-Turing thesis?

[benjayk]

I just respond to some parts of your posts, because I'd rather discuss the
main points than get sidetracked with issues that are less fundamental.


Jason Resch-2 wrote:
 

 I admit that for numbers this is not so relevant because number relations
 can be quite clearly expressed using numerous symbols (they have very few
 and simple relations), but it is much more relevant for more complex
 relations.

 
 Complex relation can be expressed in terms of a series of interrelated
 simpler relations (addition, multiplication, comparison, etc.).  You are
 focused on the very lowest level and it is no wonder you cannot see the
 higher-level possibilities for meaning, relations, intelligence,
 consciousness, etc. that a machine can create.
The complex relations can often only be expressed as simple relations on a
meta-level (which is a very big step of abstraction). You can express
rational numbers using natural numbers, but only using an additional layer
of interpretation (which is a *huge* abstraction - it's the difference
between description and what is being described).

The natural numbers itself don't lead to the rational numbers (except by
adding additional relations, like the inverse of multiplication).


Jason Resch-2 wrote:
 
 The relation of hot vs. cold as experienced by you is also the
 production of a long series of multiplications, additions, comparisons,
 and
 other operations. 
You assume reductionism or emergentism here. Of course you can defend the CT
thesis if you assume that the lowest level can magically lead to higher
levels (or the higher levels are not real in the first place).
The problem is that this magic would precisely be the higher levels that you
wanted to derive.


Jason Resch-2 wrote:
 


 Jason Resch-2 wrote:
 
  For example it cannot directly compute
   -1*-1=1. Machine A can only be used to use an encoded input value
 and
   encoded description of machine B, and give an output that is
 correct
   given
   the right decoding scheme.
  
  
   1's or 0's, X's or O's, what the symbols are don't have any bearing
 on
   what
   they can compute.
  
  That's just an assertion of the belief I am trying to question here.
  In reality, it *does* matter which symbols/things we use to compute. A
  computer that only uses one symbol (for example a computer that adds
  using
  marbles) would be pretty useless.
  It does matter in many different ways: Speed of computations,
 effciency
  of
  computation, amount of memory, efficiency of memory, ease of
 programming,
  size of programs, ease of interpreting the result, amount of layers of
  programming to interpret the result and to program efficiently, ease
 of
  introspecting into the state of a computer...
 
 
  Practically they might matter but not theoretically.
 In the right theoretical model, it does matter. I am precisely doubting
 the
 value of adhering to our simplistic theoretical model of computation as
 the
 essence of what computation means.


 What model do you propose to replace it?
 
 The Church-Turing thesis plays a similar role in computer science as the
 fundamental theorem of arithmetic does in number theory.
None. There is no one correct model of computations. There are infinite
models that express different facets of what computation is. Different
turing machines express different things, super-recursive turing machines
express another thing, etc...
I think computer scientists just don't want to accept it, because it takes
their bible away. We like to have an easy answer, even if it is the wrong
one.


Jason Resch-2 wrote:
 

 Jason Resch-2 wrote:
 
 
  Why would we abstract from all that and then reduce computation to our
  one
  very abstract and imcomplete model of computation?
  If we do this we could as well abstract from the process of
 computation
  and
  say every string can be used to emulate any machine, because if you
 know
  what program it expresses, you know what it would compute (if
 correctly
  interpreted). There's no fundamental difference. Strings need to be
  interpreted to make sense as a program, and a turing machine without
  negative numbers needs to be interpreted to make sense as a program
  computing the result of an equation using negative numbers.
 
 
  I agree, strings need to be interpreted.  This is what the Turing
 machine
  does.  The symbols on the tape become interrelated in the context of
 the
  machine that interprets the symbols and it is these relations that
 become
  equivalent.
 That is like postulating some magic in the turing machine. It just
 manipulates symbols.

 
 No, it is not magic.  It is equivalent to saying the laws of physics
 interrelate every electron and quark to each other.
It is more like saying that the laws of physics show how to create humans
from atoms.
This is not the case. Nothing in the laws of nature says that some atoms
form a human. Still it is evidently the case that there are humans, meaning
that the laws of nature just don't describe the higher

Re: Why the Church-Turing thesis?

[benjayk]

As far as I see, we mostly agree on content. 

I just can't make sense of reducing computation to emulability.
For me the intuitive sene of computation is much more rich than this.

But still, as I think about it, we can also create a model of computation
(in the sense of being intuitively computational and being implementable on
a computer) where there are computations that can't be emulated by universal
turing machine, using level breaking languages (which explicitly refer to
what is being computed on the base level). I'll write another post on this.

benjayk
-- 
View this message in context: 
http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34406986.html
Sent from the Everything List mailing list archive at Nabble.com.

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[Quentin Anciaux]

2012/9/8 benjayk benjamin.jaku...@googlemail.com


 I just respond to some parts of your posts, because I'd rather discuss the
 main points than get sidetracked with issues that are less fundamental.


 Jason Resch-2 wrote:
 
 
  I admit that for numbers this is not so relevant because number
 relations
  can be quite clearly expressed using numerous symbols (they have very
 few
  and simple relations), but it is much more relevant for more complex
  relations.
 
 
  Complex relation can be expressed in terms of a series of interrelated
  simpler relations (addition, multiplication, comparison, etc.).  You are
  focused on the very lowest level and it is no wonder you cannot see the
  higher-level possibilities for meaning, relations, intelligence,
  consciousness, etc. that a machine can create.
 The complex relations can often only be expressed as simple relations on a
 meta-level (which is a very big step of abstraction). You can express
 rational numbers using natural numbers, but only using an additional layer
 of interpretation (which is a *huge* abstraction - it's the difference
 between description and what is being described).

 The natural numbers itself don't lead to the rational numbers (except by
 adding additional relations, like the inverse of multiplication).


 Jason Resch-2 wrote:
 
  The relation of hot vs. cold as experienced by you is also the
  production of a long series of multiplications, additions, comparisons,
  and
  other operations.
 You assume reductionism or emergentism here. Of course you can defend the
 CT
 thesis if you assume that the lowest level can magically lead to higher
 levels (or the higher levels are not real in the first place).
 The problem is that this magic would precisely be the higher levels that
 you
 wanted to derive.


 Jason Resch-2 wrote:
 
 
 
  Jason Resch-2 wrote:
  
   For example it cannot directly compute
-1*-1=1. Machine A can only be used to use an encoded input value
  and
encoded description of machine B, and give an output that is
  correct
given
the right decoding scheme.
   
   
1's or 0's, X's or O's, what the symbols are don't have any bearing
  on
what
they can compute.
   
   That's just an assertion of the belief I am trying to question here.
   In reality, it *does* matter which symbols/things we use to compute.
 A
   computer that only uses one symbol (for example a computer that adds
   using
   marbles) would be pretty useless.
   It does matter in many different ways: Speed of computations,
  effciency
   of
   computation, amount of memory, efficiency of memory, ease of
  programming,
   size of programs, ease of interpreting the result, amount of layers
 of
   programming to interpret the result and to program efficiently, ease
  of
   introspecting into the state of a computer...
  
  
   Practically they might matter but not theoretically.
  In the right theoretical model, it does matter. I am precisely doubting
  the
  value of adhering to our simplistic theoretical model of computation as
  the
  essence of what computation means.
 
 
  What model do you propose to replace it?
 
  The Church-Turing thesis plays a similar role in computer science as the
  fundamental theorem of arithmetic does in number theory.
 None. There is no one correct model of computations. There are infinite
 models that express different facets of what computation is. Different
 turing machines express different things, super-recursive turing machines
 express another thing, etc...
 I think computer scientists just don't want to accept it, because it takes
 their bible away. We like to have an easy answer, even if it is the wrong
 one.


 Jason Resch-2 wrote:
 
 
  Jason Resch-2 wrote:
  
  
   Why would we abstract from all that and then reduce computation to
 our
   one
   very abstract and imcomplete model of computation?
   If we do this we could as well abstract from the process of
  computation
   and
   say every string can be used to emulate any machine, because if you
  know
   what program it expresses, you know what it would compute (if
  correctly
   interpreted). There's no fundamental difference. Strings need to be
   interpreted to make sense as a program, and a turing machine without
   negative numbers needs to be interpreted to make sense as a program
   computing the result of an equation using negative numbers.
  
  
   I agree, strings need to be interpreted.  This is what the Turing
  machine
   does.  The symbols on the tape become interrelated in the context of
  the
   machine that interprets the symbols and it is these relations that
  become
   equivalent.
  That is like postulating some magic in the turing machine. It just
  manipulates symbols.
 
 
  No, it is not magic.  It is equivalent to saying the laws of physics
  interrelate every electron and quark to each other.
 It is more like saying that the laws of physics show how to create humans
 from atoms.
 This is not the case. Nothing

Re: Why the Church-Turing thesis?

[Bruno Marchal]

On 28 Aug 2012, at 21:57, benjayk wrote:



It seems that the Church-Turing thesis, that states that an  
universal turing
machine can compute everything that is intuitively computable, has  
near

universal acceptance among computer scientists.


Yes indeed. I think there are two strong arguments for this.

The empirical one: all attempts to define the set of computable  
functions have led to the same class of functions, and this despite  
the quite independent path leading to the definitions (from Church  
lambda terms, Post production systems, von Neumann machine, billiard  
ball, combinators, cellular automata ... up to modular functor,  
quantum topologies, quantum computers, etc.).


The conceptual one: the class of computable functions is closed for  
the most transcendental operation in math: diagonalization. This is  
not the case for the notions of definability, provability,  
cardinality, etc.






I really wonder why this is so, given that there are simple cases  
where we
can compute something that an abitrary turing machine can not  
compute using
a notion of computation that is not extraordinary at all (and quite  
relevant

in reality).
For example, given you have a universal turing machine A that uses the
alphabet {1,0} and a universal turing machine B that uses the alphabet
{-1,0,1}.
Now it is quite clear that the machine A cannot directly answer any
questions that relates to -1. For example it cannot directly compute
-1*-1=1. Machine A can only be used to use an encoded input value and
encoded description of machine B, and give an output that is correct  
given

the right decoding scheme.
But for me this already makes clear that machine A is less  
computationally

powerful than machine B.


Church thesis concerns only the class of computable functions. The  
alphabet used by the Turing machine, having 1, 2, or enumerable  
alphabet does not change the class. If you dovetail on the works of 1  
letter Turing machine, you will unavoidably emulate all Turing  
machines on all finite and enumerable letters alphabets. This can be  
proved. Nor does the number of tapes, and/or  parallelism change that  
class.
Of course, some machine can be very inefficient, but this, by  
definition, does not concern Church thesis.


There was a thesis, often attributed to Cook (but I met him and he  
claims it is not his thesis), that all Turing machine can emulate  
themselves in polynomial time. This will plausibly be refuted by the  
existence of quantum computers (unless P = NP, or things like that).  
It is an open problem, but most scientists believe that in general a  
classical computer cannot emulate an arbitrary quantum computer in  
polynomial time. But I insist, quantum computer have not violated the  
Church Turing Post Markov thesis.






Its input and output when emulating B do only make
sense with respect to what the machine B does if we already know what
machine B does, and if it is known how we chose to reflect this in  
the input
of machine A (and the interpretation of its output). Otherwise we  
have no
way of even saying whether it emulates something, or whether it is  
just

doing a particular computation on the alphabet {1,0}.
I realize that it all comes down to the notion of computation. But  
why do
most choose to use such a weak notion of computation? How does  
machine B not

compute something that A doesn't by any reasonable standard?
Saying that A can compute what B computes is like saying that  
orange can
express the same as the word apple, because we can encode the word  
apple
as orange. It is true in a very limited sense, but it seems mad to  
treat
it as the foundation of what it means for words to express something  
(and

the same goes for computation).
If we use such trivial notions of computation, why not say that the  
program
return input emulates all turing-machines because given the right  
input it

gives the right output (we just give it the solution as input).
I get that we can simply use the Church-turing as the definition of
computation means. But why is it (mostly) treated as being the one  
and only
correct notion of computation (especially in a computer science  
context)?
The only explanation I have is that it is dogma. To question it  
would change
to much and would be too complicated and uncomfortable. It would  
make
computation an irreducibly complex and relative notion or - heaven  
forbid -
even an inherently subjective notion (computation from which  
perspective?).


That was what everybody believed before the rise of the universal  
machine and lambda calculus. Gödel called the closure of the  
computable functions for diagonalization a miracle, and he took time  
before assessing it. See:


DAVIS M., 1982, Why Gödel Didn't Have Church's Thesis, Information and  
Control

54,.pp. 3-24.


http://iridia.ulb.ac.be/~marchal/



--
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post

Re: Why the Church-Turing thesis?

[benjayk]

Bruno Marchal wrote:
 
 
 On 28 Aug 2012, at 21:57, benjayk wrote:
 

 It seems that the Church-Turing thesis, that states that an  
 universal turing
 machine can compute everything that is intuitively computable, has  
 near
 universal acceptance among computer scientists.
 
 Yes indeed. I think there are two strong arguments for this.
 
 The empirical one: all attempts to define the set of computable  
 functions have led to the same class of functions, and this despite  
 the quite independent path leading to the definitions (from Church  
 lambda terms, Post production systems, von Neumann machine, billiard  
 ball, combinators, cellular automata ... up to modular functor,  
 quantum topologies, quantum computers, etc.).
 
OK, now I understand it better. Apparently if we express a computation in
terms of a computable function we can always arrive at the same computable
function using a different computation of an abitrary turing universal
machine. That seems right to me.
 
But in this case I don't get why it is often claimed that CT thesis claims
that all computations can be done by a universal turing machine, not merely
that they lead to the same class of computable functions (if converted
appriopiately).
The latter is a far weaker statement, since computable functions abstract
from many relevant things about the machine.

And even this weaker statement doesn't seem true with regards to more
powerful models like super-recursive functions, as computable functions just
give finite results, while super-recursive machine can give
infinite/unlimited results.

 

Bruno Marchal wrote:
 
 The conceptual one: the class of computable functions is closed for  
 the most transcendental operation in math: diagonalization. This is  
 not the case for the notions of definability, provability,  
 cardinality, etc.
I don't really know what this means. Do you mean that there are just
countable many computations? If yes, what has this do with whether all
universal turing machines are equivalent?



Bruno Marchal wrote:
 

 I really wonder why this is so, given that there are simple cases  
 where we
 can compute something that an abitrary turing machine can not  
 compute using
 a notion of computation that is not extraordinary at all (and quite  
 relevant
 in reality).
 For example, given you have a universal turing machine A that uses the
 alphabet {1,0} and a universal turing machine B that uses the alphabet
 {-1,0,1}.
 Now it is quite clear that the machine A cannot directly answer any
 questions that relates to -1. For example it cannot directly compute
 -1*-1=1. Machine A can only be used to use an encoded input value and
 encoded description of machine B, and give an output that is correct  
 given
 the right decoding scheme.
 But for me this already makes clear that machine A is less  
 computationally
 powerful than machine B.
 
 Church thesis concerns only the class of computable functions.
Hm, maybe the wikipedia article is a bad one, since it mentioned computable
functions just as means of explaining it, not as part of its definition.


Bruno Marchal wrote:
 
  The  alphabet used by the Turing machine, having 1, 2, or enumerable  
 alphabet does not change the class. If you dovetail on the works of 1  
 letter Turing machine, you will unavoidably emulate all Turing  
 machines on all finite and enumerable letters alphabets. This can be  
 proved. Nor does the number of tapes, and/or  parallelism change that  
 class.
 Of course, some machine can be very inefficient, but this, by  
 definition, does not concern Church thesis.
Even so, CT thesis makes a claim about the equivalence of machines, not of
emulability.
Why are two machines that can be used to emlate each other regarded to be
equivalent?
In my view, there is a big difference between computing the same and being
able to emulate each other. Most importantly, emulation only makes sense
relative to another machine that is being emulated, and a correct
interpretation.

benjayk

-- 
View this message in context: 
http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34401986.html
Sent from the Everything List mailing list archive at Nabble.com.

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[benjayk]

Jason Resch-2 wrote:
 
 On Thu, Sep 6, 2012 at 12:47 PM, benjayk
 benjamin.jaku...@googlemail.comwrote:
 


 Jason Resch-2 wrote:
 
  On Tue, Aug 28, 2012 at 2:57 PM, benjayk
  benjamin.jaku...@googlemail.comwrote:
 
 
  It seems that the Church-Turing thesis, that states that an universal
  turing
  machine can compute everything that is intuitively computable, has
 near
  universal acceptance among computer scientists.
 
  I really wonder why this is so, given that there are simple cases
 where
  we
  can compute something that an abitrary turing machine can not compute
  using
  a notion of computation that is not extraordinary at all (and quite
  relevant
  in reality).
  For example, given you have a universal turing machine A that uses the
  alphabet {1,0} and a universal turing machine B that uses the alphabet
  {-1,0,1}.
  Now it is quite clear that the machine A cannot directly answer any
  questions that relates to -1.

 
 I see this at all being the case at all.  What is the symbol for -1
 supposed to look like?  Do you agree that a turing machine that used A, B,
 and C as symbols could work the same as one that used -1, 0, and 1?
Well, the symbol for -1 could be -1?
To answer your latter question, no, not necessarily. I don't take the
symbols not to be mere symbols, but to contain meaning (which they do), and
so it matters what symbols the machine use, because that changes the meaning
of its computation. Often times the meaning of the symbols also constrain
the possible relations (for example -1 * -1 normally needs to be 1, while A
* A could be A, B or C).

CT thesis wants to abstract from things like meaning, but I don't really see
the great value in acting like this is necessarily the correct theoretical
way of thinking about computations. It is only valuable as one possible,
very strongly abstracted, limited and representational model of computation
with respect to emulability.


Jason Resch-2 wrote:
 
 Everything is a representation, but what is important is that the Turing
 machine preserves the relationships.  E.g., if ABBBABAA is greater than
 AAABBAAB then 01110100 is greater than 00011001, and all the other
 properties can hold, irrespective of what symbols are used.
The problem is that relationships don't make sense apart from symbols. We
can theoretically express the natural numbers using an infinite numbers of
unique symbols for both numbers and operations (like A or B or C or X for
10, ´ or ? or [ or ° for +), but in this case it won't be clear that we are
expresing natural numbers at all (without a lengthy explanation of what the
symbols mean).
Or if we are using binary numbers to express the natural numbers, it will
also be not very clear that we mean numbers, because often binary
expressions mean something entirely else. If we then add 1 to this number
it will not be clear that we actually added one, or if we just flipped a
bit.

I admit that for numbers this is not so relevant because number relations
can be quite clearly expressed using numerous symbols (they have very few
and simple relations), but it is much more relevant for more complex
relations.


Jason Resch-2 wrote:
 
 For example it cannot directly compute
  -1*-1=1. Machine A can only be used to use an encoded input value and
  encoded description of machine B, and give an output that is correct
  given
  the right decoding scheme.
 
 
  1's or 0's, X's or O's, what the symbols are don't have any bearing on
  what
  they can compute.
 
 That's just an assertion of the belief I am trying to question here.
 In reality, it *does* matter which symbols/things we use to compute. A
 computer that only uses one symbol (for example a computer that adds
 using
 marbles) would be pretty useless.
 It does matter in many different ways: Speed of computations, effciency
 of
 computation, amount of memory, efficiency of memory, ease of programming,
 size of programs, ease of interpreting the result, amount of layers of
 programming to interpret the result and to program efficiently, ease of
 introspecting into the state of a computer...

 
 Practically they might matter but not theoretically.
In the right theoretical model, it does matter. I am precisely doubting the
value of adhering to our simplistic theoretical model of computation as the
essence of what computation means.


Jason Resch-2 wrote:
 

 Why would we abstract from all that and then reduce computation to our
 one
 very abstract and imcomplete model of computation?
 If we do this we could as well abstract from the process of computation
 and
 say every string can be used to emulate any machine, because if you know
 what program it expresses, you know what it would compute (if correctly
 interpreted). There's no fundamental difference. Strings need to be
 interpreted to make sense as a program, and a turing machine without
 negative numbers needs to be interpreted to make sense as a program
 computing the result of an equation using negative numbers.

 
 I agree

Re: Why the Church-Turing thesis?

[Stephen P. King]

On 9/7/2012 6:24 AM, benjayk wrote:

Why are two machines that can be used to emlate each other regarded to be
equivalent?
In my view, there is a big difference between computing the same and being
able to emulate each other. Most importantly, emulation only makes sense
relative to another machine that is being emulated, and a correct
interpretation.

Dear benjayk,

This is what is discussed under the header of Bisimilarity and 
bisimulation equivalence iff simulation = emulation.


http://en.wikipedia.org/wiki/Bisimulation

a bisimulation is a binary relation between state transition systems, 
associating systems which behave in the same way in the sense that one 
system simulates the other and vice-versa.


My own use of the term seeks a more generalized version that does 
not assume that the relation is necessarily binary nor strictly 
monotonic. The key is that a pair of machines can have an image of 
each other and that they are capable of acting on that image.


--
Onward!

Stephen

http://webpages.charter.net/stephenk1/Outlaw/Outlaw.html


--
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Why the Church-Turing thesis?

[benjayk]

Jason Resch-2 wrote:
 
 On Tue, Aug 28, 2012 at 2:57 PM, benjayk
 benjamin.jaku...@googlemail.comwrote:
 

 It seems that the Church-Turing thesis, that states that an universal
 turing
 machine can compute everything that is intuitively computable, has near
 universal acceptance among computer scientists.

 I really wonder why this is so, given that there are simple cases where
 we
 can compute something that an abitrary turing machine can not compute
 using
 a notion of computation that is not extraordinary at all (and quite
 relevant
 in reality).
 For example, given you have a universal turing machine A that uses the
 alphabet {1,0} and a universal turing machine B that uses the alphabet
 {-1,0,1}.
 Now it is quite clear that the machine A cannot directly answer any
 questions that relates to -1. For example it cannot directly compute
 -1*-1=1. Machine A can only be used to use an encoded input value and
 encoded description of machine B, and give an output that is correct
 given
 the right decoding scheme.

 
 1's or 0's, X's or O's, what the symbols are don't have any bearing on
 what
 they can compute.
 
That's just an assertion of the belief I am trying to question here.
In reality, it *does* matter which symbols/things we use to compute. A
computer that only uses one symbol (for example a computer that adds using
marbles) would be pretty useless.
It does matter in many different ways: Speed of computations, effciency of
computation, amount of memory, efficiency of memory, ease of programming,
size of programs, ease of interpreting the result, amount of layers of
programming to interpret the result and to program efficiently, ease of
introspecting into the state of a computer...

Why would we abstract from all that and then reduce computation to our one
very abstract and imcomplete model of computation?
If we do this we could as well abstract from the process of computation and
say every string can be used to emulate any machine, because if you know
what program it expresses, you know what it would compute (if correctly
interpreted). There's no fundamental difference. Strings need to be
interpreted to make sense as a program, and a turing machine without
negative numbers needs to be interpreted to make sense as a program
computing the result of an equation using negative numbers.


Jason Resch-2 wrote:
 
 Consider: No physical computer today uses 1's or 0's, they use voltages,
 collections of more or fewer electrons.
OK, but in this case abstraction makes sense for computer scientist because
progamers don't have access to that level. You are right, though that a chip
engineer shouldn't abstract from that level if he actually wants to build a
computer.


Jason Resch-2 wrote:
 
 This doesn't mean that our computers can only directly compute what
 electrons do.
In fact they do much more.  Electrons express strictly more than just 0 and
1. So it's not a good anology, because 0 and 1 express *less* than 0, 1 and
-1.


Jason Resch-2 wrote:
 
 But for me this already makes clear that machine A is less computationally
 powerful than machine B. Its input and output when emulating B do only
 make
 sense with respect to what the machine B does if we already know what
 machine B does, and if it is known how we chose to reflect this in the
 input
 of machine A (and the interpretation of its output). Otherwise we have no
 way of even saying whether it emulates something, or whether it is just
 doing a particular computation on the alphabet {1,0}.

 
 These are rather convincing:
 http://en.wikipedia.org/wiki/Video_game_console_emulator
 
 There is software that emulates the unique architectures of an Atari,
 Nintendo, Supernintendo, PlayStation, etc. systems.  These emulators can
 also run on any computer, whether its Intel X86, x86_64, PowerPC, etc. 
 You
 will have a convincing experience of playing an old Atari game like space
 invaders, even though the original creators of that program never intended
 it to run on a computer architecture that wouldn't be invented for another
 30 years, and the original programmers didn't have to be called in to
 re-write their program to do so.
Yes, I use them as well. They are indeed convincing. But this doesn't really
relate to the question very much.
First, our modern computers are pretty much strictly more computationally
powerful in every practical and theoretical way. It would be more of an
argument if you would simulate a windows on a nintendo (but you can't). I am
not saying that a turing machine using 0, 1 and -1 can't emulate a machine
using only 0 and 1.
Secondly, even this emulations are just correct as far as our playing
experience goes (well, at least if you are not nostalgic about hardware).
The actual process going on in the computer is very different, and thus it
makes sense to say that it computes something else. Its computation just
have a similar results in terms of experience, but they need vastly more
ressources and compute something more (all

Re: Why the Church-Turing thesis?

[Jason Resch]

On Thu, Sep 6, 2012 at 12:47 PM, benjayk benjamin.jaku...@googlemail.comwrote:



 Jason Resch-2 wrote:
 
  On Tue, Aug 28, 2012 at 2:57 PM, benjayk
  benjamin.jaku...@googlemail.comwrote:
 
 
  It seems that the Church-Turing thesis, that states that an universal
  turing
  machine can compute everything that is intuitively computable, has near
  universal acceptance among computer scientists.
 
  I really wonder why this is so, given that there are simple cases where
  we
  can compute something that an abitrary turing machine can not compute
  using
  a notion of computation that is not extraordinary at all (and quite
  relevant
  in reality).
  For example, given you have a universal turing machine A that uses the
  alphabet {1,0} and a universal turing machine B that uses the alphabet
  {-1,0,1}.
  Now it is quite clear that the machine A cannot directly answer any
  questions that relates to -1.


I see this at all being the case at all.  What is the symbol for -1
supposed to look like?  Do you agree that a turing machine that used A, B,
and C as symbols could work the same as one that used -1, 0, and 1?
Everything is a representation, but what is important is that the Turing
machine preserves the relationships.  E.g., if ABBBABAA is greater than
AAABBAAB then 01110100 is greater than 00011001, and all the other
properties can hold, irrespective of what symbols are used.


 For example it cannot directly compute
  -1*-1=1. Machine A can only be used to use an encoded input value and
  encoded description of machine B, and give an output that is correct
  given
  the right decoding scheme.
 
 
  1's or 0's, X's or O's, what the symbols are don't have any bearing on
  what
  they can compute.
 
 That's just an assertion of the belief I am trying to question here.
 In reality, it *does* matter which symbols/things we use to compute. A
 computer that only uses one symbol (for example a computer that adds using
 marbles) would be pretty useless.
 It does matter in many different ways: Speed of computations, effciency of
 computation, amount of memory, efficiency of memory, ease of programming,
 size of programs, ease of interpreting the result, amount of layers of
 programming to interpret the result and to program efficiently, ease of
 introspecting into the state of a computer...


Practically they might matter but not theoretically.



 Why would we abstract from all that and then reduce computation to our one
 very abstract and imcomplete model of computation?
 If we do this we could as well abstract from the process of computation and
 say every string can be used to emulate any machine, because if you know
 what program it expresses, you know what it would compute (if correctly
 interpreted). There's no fundamental difference. Strings need to be
 interpreted to make sense as a program, and a turing machine without
 negative numbers needs to be interpreted to make sense as a program
 computing the result of an equation using negative numbers.


I agree, strings need to be interpreted.  This is what the Turing machine
does.  The symbols on the tape become interrelated in the context of the
machine that interprets the symbols and it is these relations that become
equivalent.




 Jason Resch-2 wrote:
 
  Consider: No physical computer today uses 1's or 0's, they use voltages,
  collections of more or fewer electrons.
 OK, but in this case abstraction makes sense for computer scientist because
 progamers don't have access to that level. You are right, though that a
 chip
 engineer shouldn't abstract from that level if he actually wants to build a
 computer.


 Jason Resch-2 wrote:
 
  This doesn't mean that our computers can only directly compute what
  electrons do.
 In fact they do much more.  Electrons express strictly more than just 0 and
 1. So it's not a good anology, because 0 and 1 express *less* than 0, 1 and
 -1.


 Jason Resch-2 wrote:
 
  But for me this already makes clear that machine A is less
 computationally
  powerful than machine B. Its input and output when emulating B do only
  make
  sense with respect to what the machine B does if we already know what
  machine B does, and if it is known how we chose to reflect this in the
  input
  of machine A (and the interpretation of its output). Otherwise we have
 no
  way of even saying whether it emulates something, or whether it is just
  doing a particular computation on the alphabet {1,0}.
 
 
  These are rather convincing:
  http://en.wikipedia.org/wiki/Video_game_console_emulator
 
  There is software that emulates the unique architectures of an Atari,
  Nintendo, Supernintendo, PlayStation, etc. systems.  These emulators can
  also run on any computer, whether its Intel X86, x86_64, PowerPC, etc.
  You
  will have a convincing experience of playing an old Atari game like space
  invaders, even though the original creators of that program never
 intended
  it to run on a computer architecture that wouldn't be invented for
 another

Re: Why the Church-Turing thesis?

[Jason Resch]

On Tue, Aug 28, 2012 at 2:57 PM, benjayk benjamin.jaku...@googlemail.comwrote:


 It seems that the Church-Turing thesis, that states that an universal
 turing
 machine can compute everything that is intuitively computable, has near
 universal acceptance among computer scientists.

 I really wonder why this is so, given that there are simple cases where we
 can compute something that an abitrary turing machine can not compute using
 a notion of computation that is not extraordinary at all (and quite
 relevant
 in reality).
 For example, given you have a universal turing machine A that uses the
 alphabet {1,0} and a universal turing machine B that uses the alphabet
 {-1,0,1}.
 Now it is quite clear that the machine A cannot directly answer any
 questions that relates to -1. For example it cannot directly compute
 -1*-1=1. Machine A can only be used to use an encoded input value and
 encoded description of machine B, and give an output that is correct given
 the right decoding scheme.


1's or 0's, X's or O's, what the symbols are don't have any bearing on what
they can compute.

Consider: No physical computer today uses 1's or 0's, they use voltages,
collections of more or fewer electrons.

This doesn't mean that our computers can only directly compute what
electrons do.

But for me this already makes clear that machine A is less computationally
 powerful than machine B. Its input and output when emulating B do only make
 sense with respect to what the machine B does if we already know what
 machine B does, and if it is known how we chose to reflect this in the
 input
 of machine A (and the interpretation of its output). Otherwise we have no
 way of even saying whether it emulates something, or whether it is just
 doing a particular computation on the alphabet {1,0}.


These are rather convincing:
http://en.wikipedia.org/wiki/Video_game_console_emulator

There is software that emulates the unique architectures of an Atari,
Nintendo, Supernintendo, PlayStation, etc. systems.  These emulators can
also run on any computer, whether its Intel X86, x86_64, PowerPC, etc.  You
will have a convincing experience of playing an old Atari game like space
invaders, even though the original creators of that program never intended
it to run on a computer architecture that wouldn't be invented for another
30 years, and the original programmers didn't have to be called in to
re-write their program to do so.


 I realize that it all comes down to the notion of computation. But why do
 most choose to use such a weak notion of computation? How does machine B
 not
 compute something that A doesn't by any reasonable standard?
 Saying that A can compute what B computes is like saying that orange can
 express the same as the word apple, because we can encode the word
 apple
 as orange.


System A (using its own language of representation for system A), can
predict exactly all future states of another system B (and vice versa).  A
and B have different symbols, states, instructions, etc., so perhaps this
is why you think system A can't perfectly emulate system B, but this is a
little like saying there are things that can only be described by Spanish
speakers that no other language (French, English, etc.) could describe.
 Sure, a translation needs to occur to communicate a Spanish idea into an
English one, but just because spanish and english speakers use a different
language doesn't mean there are problems only speakers of one language can
solve.


 It is true in a very limited sense, but it seems mad to treat
 it as the foundation of what it means for words to express something (and
 the same goes for computation).
 If we use such trivial notions of computation, why not say that the program
 return input emulates all turing-machines because given the right input
 it
 gives the right output (we just give it the solution as input).


Many programs have no input and/or no output, but they still can be
rightfully said to perform different computations.


 I get that we can simply use the Church-turing as the definition of
 computation means. But why is it (mostly) treated as being the one and only
 correct notion of computation (especially in a computer science context)?


I think it more comes into play in the a definition of a universal machine,
than in the definition of computation.

It is useful because it makes it easy to prove.  All you need to do is show
how some machine can be used to emulate any other known turning universal
machine.




The only explanation I have is that it is dogma. To question it would change
 to much and would be too complicated and uncomfortable. It would make
 computation an irreducibly complex and relative notion or - heaven forbid -
 even an inherently subjective notion (computation from which perspective?).


Reverse engineering machine language code is very difficult, but there are
automated programs for doing this that can provide much more readable
program code.  Code too, can be difficult

Physical Church-Turing thesis and QM

[ronaldheld]

http://arxiv.org/PS_cache/arxiv/pdf/1102/1102.1612v1.pdf
Any comments?
Ronald

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Physical Church-Turing thesis and QM

[Stephen Paul King]

Hi Ronald,

-Original Message- 
From: ronaldheld

Sent: Wednesday, February 09, 2011 7:15 AM
To: Everything List
Subject: Physical Church-Turing thesis and QM

http://arxiv.org/PS_cache/arxiv/pdf/1102/1102.1612v1.pdf
Any comments?
   Ronald
***
   A very cool paper! One thing I noticed is that one could use this to 
examine the difficulties that manifest when trying to reconcile GR with QM. 
For one thing, any (non-Ricci?) curvature would disrupt the homogeneity of 
space and time that are required of the PCTT. Accelerations are known to 
induce phase shifts in the wave functions that can easily break 
quiescence... The problem of Locality is also a difficulty.


Onward!

Stephen 


--
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: Physical Church-Turing thesis and QM

[Bruno Marchal]

I will take a look asap. At first sight the authors do not use the  
David Deutsch physical Church-Turing thesis. OK?


Bruno


On 09 Feb 2011, at 13:15, ronaldheld wrote:


http://arxiv.org/PS_cache/arxiv/pdf/1102/1102.1612v1.pdf
Any comments?
   Ronald

--
You received this message because you are subscribed to the Google  
Groups Everything List group.

To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com 
.
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en 
.




http://iridia.ulb.ac.be/~marchal/



--
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Re: church-turing thesis

[Bruno Marchal]

Hmm ... I may come back on this difficult and interesting question (Is  
Church thesis provable) when we will pursue the seventh step serie  
thread.


My feeling is that if Church thesis was provable, we would become  
capable of defining the natural number in a categorical first order  
language theory, which is impossible.


Church thesis is a necessary informal truth. It can have many formal  
counterpart (like some intuitionist Church thesis), but those are  
different theses.
Yet CT is a scientific thesis, because it may be formally refute. It  
is really at the intersection of science and philosophy/theology.


A weakening of Church thesis is: It exists a universal digital  
machine. From this you can prove already by one (double)  
diagonalization the incompleteness of its many relative provability  
powers, like you can prove, that IF ever that machine believes in the  
induction axioms i.e. [{A(0)  for all n, A(n) - A(n+1)} - {for all  
n, A(n)}], for all formula A expressible in its language, THEN the  
machine becomes Löbian, and is able to prove its own incompleteness,  
and is capable of intuiting the truth in its many modal (person  
perspectives) ways.


The key of understanding Church thesis, is that it makes both the  
notion of computability an absolute, and of provability a relative  
notion. But all Löbian provabilities obeys to the same (double) self- 
referential laws (G and G*).


But I am not sure everyone get the 8th point (movie graph). If a  
computer is active from t to t+dt, and does not use register 24 during  
the computation, would the absence of that register (during t and t 
+dt) break the supervenience of consciousness on the computation  
implemented by that machine?


My opinion is that such a break would contradict either comp or  
physical supervenience. But I am not sure how much

are convinced by this.
It is needed to understand that a universal machine cannot distinguish  
physical, virtual, and arithmetical realities, so that the first  
person indeterminacy bears on the sigma_1 sentences and their  
(possibly infinite) proofs (with oracle, ...).


Thanks for the link Mirek,

Bruno


On 13 May 2010, at 00:36, Miroslav Dobsicek wrote:


A link for those who like to wrap their brain around prospects of
proving Church-Turing thesis.

http://www.logicmatters.net/resources/pdfs/KreiselSqueezing.pdf

Mirek

--
You received this message because you are subscribed to the Google  
Groups Everything List group.

To post to this group, send email to everything-l...@googlegroups.com.
To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com 
.
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en 
.




http://iridia.ulb.ac.be/~marchal/



--
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-l...@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

church-turing thesis

[Miroslav Dobsicek]

A link for those who like to wrap their brain around prospects of
proving Church-Turing thesis.

http://www.logicmatters.net/resources/pdfs/KreiselSqueezing.pdf

Mirek

-- 
You received this message because you are subscribed to the Google Groups 
Everything List group.
To post to this group, send email to everything-l...@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

realism vs. Church-Turing Thesis

[Wei Dai]

On Fri, Jul 12, 2002 at 06:47:46PM +0200, Bruno Marchal wrote:
 Those I have encapsulated in the label comp. Precisely it consists in
 1)accepting a minimal amount of arithmetical realism, i.e. the truth of
 elementary statements of arithmetic does not depend of me or us ...
 2) the Church Thesis (also called the Church Turing Thesis, or the 
 Post Law, etc.)
 i.e. all universal machine are equivalent with respect to their simulation
 abilities (making abstraction of the duration of those simulation).
 3) [skipped]

Couple of questions that arise from reading Hartley Rogers's book. Why
stop at arithmetical realism? Why not analytical realism (truth of
statements of analysis does not depend on us) or set theoretic realism
(truth of statements of set theory does not depend on us), both of which 
are stronger than arithmetical realism?

Isn't (even) arithmetical realism incompatible with the Church-Turing
Thesis, because no Turing machine can enumerate all true statements of
elementary number theory?  (BTW, according to
http://plato.stanford.edu/entries/church-turing/, there is quite a bit of
confusion about what people mean by the Church-Turing Thesis. Could you
take a look at that article and tell me which version of the Thesis you
have in mind? For now I'll assume that you mean what the article refers to
as Thesis M.)  So why do you restict your Universal Dovetailer to be a
Turing machine? Why not one of the more powerful machines surveyed in
http://www.phil.canterbury.ac.nz/jack_copeland/pub/broad.pdf?