Reachability for infinite -time Turing machines with long tapes

65 views
Skip to first unread message

Philip Thrift

unread,
Mar 10, 2020, 11:16:38 AM3/10/20
to Everything List

Lawrence Crowell

unread,
Mar 11, 2020, 10:31:43 AM3/11/20
to Everything List
On Tuesday, March 10, 2020 at 10:16:38 AM UTC-5, Philip Thrift wrote:

It looks to be a version of the busy beaver problem. The scale of the problem grows beyond computable bounds.

LC 

spudb...@aol.com

unread,
Mar 12, 2020, 12:21:55 AM3/12/20
to goldenfield...@gmail.com, everyth...@googlegroups.com
You're ignoring quantum and photonic computing??!! 


--
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 view this discussion on the web visit
https://groups.google.com/d/msgid/everything-list/78b7f972-953b-48a2-94b3-112693535723%40googlegroups.com
.

Philip Thrift

unread,
Mar 12, 2020, 5:48:04 AM3/12/20
to Everything List


There is a "contest" of essays on the hyper-super-beyond-computable:

FQXi FORUM: Undecidability, Uncomputability, and Unpredictability Essay Contest


If I wrote an essay the theme would be that undecidability and uncomputability are useless to science. 

Suppose we found some actual matter that does infinite-time computing

We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. 

and actual experiments that supported that conclusion!

Then we he would have matter that does compute infinitely.

@philipthrift

Lawrence Crowell

unread,
Mar 12, 2020, 9:07:27 AM3/12/20
to Everything List
On Wednesday, March 11, 2020 at 11:21:55 PM UTC-5, spudb...@aol.com wrote:
You're ignoring quantum and photonic computing??!! 


No, quantum computing does not even map NP problems into P. I does not get around incompleteness results of Turing and Goedel.

LC
 

-----Original Message-----
From: Lawrence Crowell <goldenfield...@gmail.com>
To: Everything List <everyth...@googlegroups.com>
Sent: Wed, Mar 11, 2020 10:31 am
Subject: Re: Reachability for infinite -time Turing machines with long tapes

On Tuesday, March 10, 2020 at 10:16:38 AM UTC-5, Philip Thrift wrote:

It looks to be a version of the busy beaver problem. The scale of the problem grows beyond computable bounds.

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

Bruno Marchal

unread,
Mar 14, 2020, 6:15:26 AM3/14/20
to everyth...@googlegroups.com
It concerns also infinite machine. With mechanism, they have a natural role in the phenomenology, but get problematic if we add them to the ontology.

Bruno




LC 

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

Bruno Marchal

unread,
Mar 14, 2020, 6:23:53 AM3/14/20
to everyth...@googlegroups.com
On 12 Mar 2020, at 14:07, Lawrence Crowell <goldenfield...@gmail.com> wrote:

On Wednesday, March 11, 2020 at 11:21:55 PM UTC-5, spudb...@aol.com wrote:
You're ignoring quantum and photonic computing??!! 


No, quantum computing does not even map NP problems into P. I does not get around incompleteness results of Turing and Goedel.

That’s right. In fact super-hyper-machine does not escape incompleteness and can even be super-hyper-incomplete.Using the infinite to escape Gödel incompleteness does not work, or becomes trivial. 

I will consider admitting the infinite in the ontology the day I got an infinite salary :)

Even the induction axioms are not allowed in the ontology, despite being the main axiom about what is an observer.

Quantum computing (and I guess photonic computing) does not violate the Church-Turing thesis. David Deustch saw this clearly already in its main quantum computability paper.

Bruno




LC
 

-----Original Message-----
From: Lawrence Crowell <goldenfield...@gmail.com>
To: Everything List <everyth...@googlegroups.com>
Sent: Wed, Mar 11, 2020 10:31 am
Subject: Re: Reachability for infinite -time Turing machines with long tapes

On Tuesday, March 10, 2020 at 10:16:38 AM UTC-5, Philip Thrift wrote:

It looks to be a version of the busy beaver problem. The scale of the problem grows beyond computable bounds.

LC 
--
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/78b7f972-953b-48a2-94b3-112693535723%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-li...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/1c06645a-2f80-44ee-9d49-6a179e8a7892%40googlegroups.com.

Philip Thrift

unread,
Mar 14, 2020, 7:22:35 AM3/14/20
to Everything List


On Saturday, March 14, 2020 at 5:23:53 AM UTC-5, Bruno Marchal wrote:

On 12 Mar 2020, at 14:07, Lawrence Crowell <goldenfield...@gmail.com> wrote:

On Wednesday, March 11, 2020 at 11:21:55 PM UTC-5, spudb...@aol.com wrote:
You're ignoring quantum and photonic computing??!! 


No, quantum computing does not even map NP problems into P. I does not get around incompleteness results of Turing and Goedel.

That’s right. In fact super-hyper-machine does not escape incompleteness and can even be super-hyper-incomplete.Using the infinite to escape Gödel incompleteness does not work, or becomes trivial. 

I will consider admitting the infinite in the ontology the day I got an infinite salary :)

Even the induction axioms are not allowed in the ontology, despite being the main axiom about what is an observer.

Quantum computing (and I guess photonic computing) does not violate the Church-Turing thesis. David Deustch saw this clearly already in its main quantum computability paper.

Bruno






“It's absolutely possible that there are multiple worlds where you made different decisions. We're just obeying the laws of physics,” says Sean Carroll, a theoretical physicist at the California Institute of Technology and the author of a new book on many worlds titled "Something Deeply Hidden." Just how many versions of you might there be? “We don't know whether the number of worlds is finite or infinite, but it's certainly a very large number," Carroll says. "There’s no way it’s, like, five.”

Renowned theorist Roger Penrose of Oxford University dismisses the idea as “reductio ad absurdum”: physics reduced to absurdity. On the other hand, Penrose’s former collaborator, the late Stephen Hawking, described the many worlds interpretation as “self-evidently true.”

Coming at the critique from a different angle, Oxford's Roger Penrose argues that the whole idea of many worlds is flawed, because it’s based on an overly simplistic version of quantum mechanics that doesn’t account for gravity. “The rules must change when gravity is involved,” he says.

In a more complete quantum theory, Penrose argues, gravity helps anchor reality and blurry events will have only one allowable outcome. He points to a potentially decisive experiment now being carried out at the University of California, Santa Barbara, and Leiden University in the Netherlands that's designed to directly observe how an object transforms from many possible locations to a single, fixed reality.

Carroll is unmoved by these alternative explanations, which he considers overly complicated and unsupported by data. The notion of multiple yous can be unnerving, he concedes. But to him the underlying concept of many worlds is “crisp, clear, beautiful, simple and pure.”

If he's right, he's not the only Sean Carroll who feels that way.

@philipthrift 

Brent Meeker

unread,
Mar 14, 2020, 2:48:43 PM3/14/20
to everyth...@googlegroups.com
Did you not follow the discussion with Bruce and Smitra?  It is far from “crisp, clear, beautiful, simple and pure.” when you actually try to fill out how it works.

Brent


If he's right, he's not the only Sean Carroll who feels that way.

@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-li...@googlegroups.com.

Lawrence Crowell

unread,
Mar 14, 2020, 5:42:15 PM3/14/20
to Everything List
On Saturday, March 14, 2020 at 5:23:53 AM UTC-5, Bruno Marchal wrote:

On 12 Mar 2020, at 14:07, Lawrence Crowell <goldenfield...@gmail.com> wrote:

On Wednesday, March 11, 2020 at 11:21:55 PM UTC-5, spudb...@aol.com wrote:
You're ignoring quantum and photonic computing??!! 


No, quantum computing does not even map NP problems into P. I does not get around incompleteness results of Turing and Goedel.

That’s right. In fact super-hyper-machine does not escape incompleteness and can even be super-hyper-incomplete.Using the infinite to escape Gödel incompleteness does not work, or becomes trivial. 

I will consider admitting the infinite in the ontology the day I got an infinite salary :)

Even the induction axioms are not allowed in the ontology, despite being the main axiom about what is an observer.

Quantum computing (and I guess photonic computing) does not violate the Church-Turing thesis. David Deustch saw this clearly already in its main quantum computability paper.

Bruno



Quantum computers obey the CT thesis. What might be called black hole computers the same holds. Quantum gravitation is the same, and my essay on FQXi explores this.

LC

Philip Thrift

unread,
Mar 15, 2020, 2:35:28 AM3/15/20
to Everything List


On Saturday, March 14, 2020 at 1:48:43 PM UTC-5, Brent wrote:


On 3/14/2020 4:22 AM, Philip Thrift wrote:


On Saturday, March 14, 2020 at 5:23:53 AM UTC-5, Bruno Marchal wrote:

On 12 Mar 2020, at 14:07, Lawrence Crowell <goldenfield...@gmail.com> wrote:

On Wednesday, March 11, 2020 at 11:21:55 PM UTC-5, spudb...@aol.com wrote:
You're ignoring quantum and photonic computing??!! 


No, quantum computing does not even map NP problems into P. I does not get around incompleteness results of Turing and Goedel.

That’s right. In fact super-hyper-machine does not escape incompleteness and can even be super-hyper-incomplete.Using the infinite to escape Gödel incompleteness does not work, or becomes trivial. 

I will consider admitting the infinite in the ontology the day I got an infinite salary :)

Even the induction axioms are not allowed in the ontology, despite being the main axiom about what is an observer.

Quantum computing (and I guess photonic computing) does not violate the Church-Turing thesis. David Deustch saw this clearly already in its main quantum computability paper.

Bruno






“It's absolutely possible that there are multiple worlds where you made different decisions. We're just obeying the laws of physics,” says Sean Carroll, a theoretical physicist at the California Institute of Technology and the author of a new book on many worlds titled "Something Deeply Hidden." Just how many versions of you might there be? “We don't know whether the number of worlds is finite or infinite, but it's certainly a very large number," Carroll says. "There’s no way it’s, like, five.”

Renowned theorist Roger Penrose of Oxford University dismisses the idea as “reductio ad absurdum”: physics reduced to absurdity. On the other hand, Penrose’s former collaborator, the late Stephen Hawking, described the many worlds interpretation as “self-evidently true.”

Coming at the critique from a different angle, Oxford's Roger Penrose argues that the whole idea of many worlds is flawed, because it’s based on an overly simplistic version of quantum mechanics that doesn’t account for gravity. “The rules must change when gravity is involved,” he says.

In a more complete quantum theory, Penrose argues, gravity helps anchor reality and blurry events will have only one allowable outcome. He points to a potentially decisive experiment now being carried out at the University of California, Santa Barbara, and Leiden University in the Netherlands that's designed to directly observe how an object transforms from many possible locations to a single, fixed reality.

Carroll is unmoved by these alternative explanations, which he considers overly complicated and unsupported by data. The notion of multiple yous can be unnerving, he concedes. But to him the underlying concept of many worlds is “crisp, clear, beautiful, simple and pure.”

Did you not follow the discussion with Bruce and Smitra?  It is far from “crisp, clear, beautiful, simple and pure.” when you actually try to fill out how it works.

Brent



Roger Penrose is right:


Roger Penrose of Oxford University dismisses [many worlds] as “reductio ad absurdum”: physics reduced to absurdity.

@philipthrift 

Bruno Marchal

unread,
Mar 15, 2020, 5:41:49 AM3/15/20
to everyth...@googlegroups.com
On 14 Mar 2020, at 12:22, Philip Thrift <cloud...@gmail.com> wrote:



On Saturday, March 14, 2020 at 5:23:53 AM UTC-5, Bruno Marchal wrote:

On 12 Mar 2020, at 14:07, Lawrence Crowell <goldenfield...@gmail.com> wrote:

On Wednesday, March 11, 2020 at 11:21:55 PM UTC-5, spudb...@aol.com wrote:
You're ignoring quantum and photonic computing??!! 


No, quantum computing does not even map NP problems into P. I does not get around incompleteness results of Turing and Goedel.

That’s right. In fact super-hyper-machine does not escape incompleteness and can even be super-hyper-incomplete.Using the infinite to escape Gödel incompleteness does not work, or becomes trivial. 

I will consider admitting the infinite in the ontology the day I got an infinite salary :)

Even the induction axioms are not allowed in the ontology, despite being the main axiom about what is an observer.

Quantum computing (and I guess photonic computing) does not violate the Church-Turing thesis. David Deustch saw this clearly already in its main quantum computability paper.

Bruno






“It's absolutely possible that there are multiple worlds where you made different decisions. We're just obeying the laws of physics,” says Sean Carroll, a theoretical physicist at the California Institute of Technology and the author of a new book on many worlds titled "Something Deeply Hidden." Just how many versions of you might there be? “We don't know whether the number of worlds is finite or infinite, but it's certainly a very large number," Carroll says. "There’s no way it’s, like, five.”

Yes, Mechanism enforces this. I have semi-rigorous evidence that for the illusion of matter we might need even very large cardinals. But they belong to the phenomenology. (Assuming mechanism) there are zero worlds, but from inside, there might be a cardinal of Laver of consistent histories, as far as I know.





Renowned theorist Roger Penrose of Oxford University dismisses the idea as “reductio ad absurdum”: physics reduced to absurdity. On the other hand, Penrose’s former collaborator, the late Stephen Hawking, described the many worlds interpretation as “self-evidently true.”

Coming at the critique from a different angle, Oxford's Roger Penrose argues that the whole idea of many worlds is flawed, because it’s based on an overly simplistic version of quantum mechanics that doesn’t account for gravity. “The rules must change when gravity is involved,” he says.

We can always speculate about a new theory. Penrose speculates also that Mechanism is false, and its use of Gödel’s theorem is invalid. Gödel’s theorem does not show that we are not machine, it shows only that if we are machine we cannot know which one, and indeed that is intuitively true, and is the base of the reduction of physics to a statistic on all computation.




In a more complete quantum theory, Penrose argues, gravity helps anchor reality and blurry events will have only one allowable outcome. He points to a potentially decisive experiment now being carried out at the University of California, Santa Barbara, and Leiden University in the Netherlands that's designed to directly observe how an object transforms from many possible locations to a single, fixed reality.

Carroll is unmoved by these alternative explanations, which he considers overly complicated and unsupported by data.

Carroll is right on this, with respect to mechanism. He remains physicalist thought and apparently unaware of the (computationalist) mind-body problem. That is just a tradition since 1500 years.



The notion of multiple yous can be unnerving, he concedes. But to him the underlying concept of many worlds is “crisp, clear, beautiful, simple and pure.”

If he's right, he's not the only Sean Carroll who feels that way.


If two identical brain/computer do exactly the same 3p activity at the right substitution level, would you say that there is two people? If yes, then indeed, there are an infinity of Sean Carroll feeling that way. If no, then we have to define “Sean Carroll” by the quotient of the computational histories/states for a first person non-distinguishability relations, and the number will be finite.

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-li...@googlegroups.com.

Bruno Marchal

unread,
Mar 15, 2020, 5:47:10 AM3/15/20
to everyth...@googlegroups.com
On 14 Mar 2020, at 22:42, Lawrence Crowell <goldenfield...@gmail.com> wrote:

On Saturday, March 14, 2020 at 5:23:53 AM UTC-5, Bruno Marchal wrote:

On 12 Mar 2020, at 14:07, Lawrence Crowell <goldenfield...@gmail.com> wrote:

On Wednesday, March 11, 2020 at 11:21:55 PM UTC-5, spudb...@aol.com wrote:
You're ignoring quantum and photonic computing??!! 


No, quantum computing does not even map NP problems into P. I does not get around incompleteness results of Turing and Goedel.

That’s right. In fact super-hyper-machine does not escape incompleteness and can even be super-hyper-incomplete.Using the infinite to escape Gödel incompleteness does not work, or becomes trivial. 

I will consider admitting the infinite in the ontology the day I got an infinite salary :)

Even the induction axioms are not allowed in the ontology, despite being the main axiom about what is an observer.

Quantum computing (and I guess photonic computing) does not violate the Church-Turing thesis. David Deustch saw this clearly already in its main quantum computability paper.

Bruno



Quantum computers obey the CT thesis. What might be called black hole computers the same holds. Quantum gravitation is the same, and my essay on FQXi explores this.


You might recall us the link. I tend to agree with you. Of course we don’t know, as we have not yet a coherent theory of gravitation and quantum mechanics. But it is not good practice to speculate on the wrongness of a theory to satisfy some philosophical desire, like Penrose seems to have done. Gödel’s theorem and the quantum theory are until now rather strong evidence that mechanism is true. But then the theory of everything, unifying all forces, (love included!) is very simple, and any Turing complete first order theory, without induction, nor axiom of infinity will do the job. Physics is “machine independent” as we say in computer science.

Bruno



LC
 


LC
 

-----Original Message-----
From: Lawrence Crowell <goldenfield...@gmail.com>
To: Everything List <everyth...@googlegroups.com>
Sent: Wed, Mar 11, 2020 10:31 am
Subject: Re: Reachability for infinite -time Turing machines with long tapes

On Tuesday, March 10, 2020 at 10:16:38 AM UTC-5, Philip Thrift wrote:

It looks to be a version of the busy beaver problem. The scale of the problem grows beyond computable bounds.

LC 

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

Lawrence Crowell

unread,
Mar 15, 2020, 11:39:29 AM3/15/20
to Everything List
On Sunday, March 15, 2020 at 4:47:10 AM UTC-5, Bruno Marchal wrote:

On 14 Mar 2020, at 22:42, Lawrence Crowell <goldenfield...@gmail.com> wrote:

On Saturday, March 14, 2020 at 5:23:53 AM UTC-5, Bruno Marchal wrote:

On 12 Mar 2020, at 14:07, Lawrence Crowell <goldenfield...@gmail.com> wrote:

On Wednesday, March 11, 2020 at 11:21:55 PM UTC-5, spudb...@aol.com wrote:
You're ignoring quantum and photonic computing??!! 


No, quantum computing does not even map NP problems into P. I does not get around incompleteness results of Turing and Goedel.

That’s right. In fact super-hyper-machine does not escape incompleteness and can even be super-hyper-incomplete.Using the infinite to escape Gödel incompleteness does not work, or becomes trivial. 

I will consider admitting the infinite in the ontology the day I got an infinite salary :)

Even the induction axioms are not allowed in the ontology, despite being the main axiom about what is an observer.

Quantum computing (and I guess photonic computing) does not violate the Church-Turing thesis. David Deustch saw this clearly already in its main quantum computability paper.

Bruno



Quantum computers obey the CT thesis. What might be called black hole computers the same holds. Quantum gravitation is the same, and my essay on FQXi explores this.


You might recall us the link. I tend to agree with you. Of course we don’t know, as we have not yet a coherent theory of gravitation and quantum mechanics. But it is not good practice to speculate on the wrongness of a theory to satisfy some philosophical desire, like Penrose seems to have done. Gödel’s theorem and the quantum theory are until now rather strong evidence that mechanism is true. But then the theory of everything, unifying all forces, (love included!) is very simple, and any Turing complete first order theory, without induction, nor axiom of infinity will do the job. Physics is “machine independent” as we say in computer science.

Bruno


This is from a post I wrote on Hossenfelder's blog:

Superdeterminism has characteristics very similar to hypercomputation. A hyper-Turing machine is one able to circumvent the restrictions of the Gödel-Turing uncomputability limit. A sort of Zeno machine may illustrate this. If I were to flip a switch at one second, then flip again at ½ second, then flip again at ¼ second and so forth, what is the state of the switch after 2 seconds? Well the rapid increase in energy required to oscillate the switch means that even if the switch does not fly apart it will face an energy limit where it is a black hole. Hence, at least from the outside general relativity appears to spoil the dream of circumventing Gödel and Turing.

What if we go into the black hole? The inner event horizon is in the pure eternal solution continuous with I^∞. This would permit a sort of Zeno computation to be observed. This means one could in principle witness this end of switch toggling. So, if that switch is toggled or not toggled with each half-partitioned integral of time any possible algorithm can be computed and its output logged. However, this idealism is spoiled by quantum mechanics, for the black hole will emit Hawking radiation and the inner horizon is no longer continuous with I^∞. Thus, quantum mechanics rescues Gödel and Turing, where both QM and GR appear to respect the Church-Turing thesis of computation so computed outputs are from first order primitive recursive algorithms.

As Peter Shor keeps harping on superdeterminism, with its real nesting of fractal loops or orbits, implies a vast or even infinite number of degrees of freedom. This does appear to be a serious minefield to go through, However, if these are nonlocal they are not real degrees of freedom that communicate information. They respect the no-signaling theorem of QM. If we could really output all of these nested loops or paths this would be a sort of hypercomputation. But we can’t, I illustrate this with the Matiyasevich theorem in the uncomputability of p-adic sets, while Palmer appeals to a funny idea of uncomputability of fractal or recursively enumerable sets by Blum, Shub, and Smale.
Hypercomputing is an interesting concept, but spacetime configurations that permit it violate conditions such as Hawking-Penrose energy conditions or chronology protection. Quantum mechanics and general relativity have conditions that in some ways are equivalent. For instance, the no-cloning theorem of QM is equivalent to chronology protection, for a wormhole would permit quantum cloning of states.  

For hypercomputation a spacetime with closed timelike curves would suffice as well. The answer to an undecidable problem could come from a time machine if one sends the results back in time to yourself later. Anti-de Sitter spacetimes permit this. Curiously AdS and de Sitter (dS) spacetimes have the same quantum information, for the two spacetimes share asymptotic infinity. The de Sitter spacetime of inflation may then have a correspondence with an AdS in a quantum computing system. We may think of a computer with a closed timelike curve CTC register plus a chronology respecting register. As the two are quantum states or waves they then constructively and destructively interfere with each other. 

quantum computer with closed timelike curves.png


The CTC corresponds to the chronology violating AdS and the CR is chronology respecting register. The self-interference of quantum waves imprints a quantum computing output in the R_{ctc} and quantum information in the R_{cr} corresponding to it has constructive interference. This is then how quantum computing in quantum gravitation or cosmology may work.

However, event horizons protect us from observing the data stack in R_{ctc} and this is then not hypercomputation. In this way spacetime and in general classical einselected outcomes occur, but we are shielded away from knowing how it occurs. It is not Turing computable. If theorems of QM and those of GR are formally equivalent, then this carries over to superdeterminism. This means there is no extra information we can obtain from superdeterminism that beats Gödel and Turing.

LC
 


LC
 


LC
 

-----Original Message-----
From: Lawrence Crowell <goldenfield...@gmail.com>
To: Everything List <everyth...@googlegroups.com>
Sent: Wed, Mar 11, 2020 10:31 am
Subject: Re: Reachability for infinite -time Turing machines with long tapes

On Tuesday, March 10, 2020 at 10:16:38 AM UTC-5, Philip Thrift wrote:

It looks to be a version of the busy beaver problem. The scale of the problem grows beyond computable bounds.

LC 

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

Bruno Marchal

unread,
Mar 16, 2020, 10:24:17 AM3/16/20
to everyth...@googlegroups.com
On 15 Mar 2020, at 16:39, Lawrence Crowell <goldenfield...@gmail.com> wrote:

On Sunday, March 15, 2020 at 4:47:10 AM UTC-5, Bruno Marchal wrote:

On 14 Mar 2020, at 22:42, Lawrence Crowell <goldenfield...@gmail.com> wrote:

On Saturday, March 14, 2020 at 5:23:53 AM UTC-5, Bruno Marchal wrote:

On 12 Mar 2020, at 14:07, Lawrence Crowell <goldenfield...@gmail.com> wrote:

On Wednesday, March 11, 2020 at 11:21:55 PM UTC-5, spudb...@aol.com wrote:
You're ignoring quantum and photonic computing??!! 


No, quantum computing does not even map NP problems into P. I does not get around incompleteness results of Turing and Goedel.

That’s right. In fact super-hyper-machine does not escape incompleteness and can even be super-hyper-incomplete.Using the infinite to escape Gödel incompleteness does not work, or becomes trivial. 

I will consider admitting the infinite in the ontology the day I got an infinite salary :)

Even the induction axioms are not allowed in the ontology, despite being the main axiom about what is an observer.

Quantum computing (and I guess photonic computing) does not violate the Church-Turing thesis. David Deustch saw this clearly already in its main quantum computability paper.

Bruno



Quantum computers obey the CT thesis. What might be called black hole computers the same holds. Quantum gravitation is the same, and my essay on FQXi explores this.


You might recall us the link. I tend to agree with you. Of course we don’t know, as we have not yet a coherent theory of gravitation and quantum mechanics. But it is not good practice to speculate on the wrongness of a theory to satisfy some philosophical desire, like Penrose seems to have done. Gödel’s theorem and the quantum theory are until now rather strong evidence that mechanism is true. But then the theory of everything, unifying all forces, (love included!) is very simple, and any Turing complete first order theory, without induction, nor axiom of infinity will do the job. Physics is “machine independent” as we say in computer science.

Bruno


This is from a post I wrote on Hossenfelder's blog:

Superdeterminism has characteristics very similar to hypercomputation. A hyper-Turing machine is one able to circumvent the restrictions of the Gödel-Turing uncomputability limit. A sort of Zeno machine may illustrate this. If I were to flip a switch at one second, then flip again at ½ second, then flip again at ¼ second and so forth, what is the state of the switch after 2 seconds? Well the rapid increase in energy required to oscillate the switch means that even if the switch does not fly apart it will face an energy limit where it is a black hole. Hence, at least from the outside general relativity appears to spoil the dream of circumventing Gödel and Turing.

What if we go into the black hole? The inner event horizon is in the pure eternal solution continuous with I^∞. This would permit a sort of Zeno computation to be observed. This means one could in principle witness this end of switch toggling. So, if that switch is toggled or not toggled with each half-partitioned integral of time any possible algorithm can be computed and its output logged. However, this idealism is spoiled by quantum mechanics, for the black hole will emit Hawking radiation and the inner horizon is no longer continuous with I^∞. Thus, quantum mechanics rescues Gödel and Turing, where both QM and GR appear to respect the Church-Turing thesis of computation so computed outputs are from first order primitive recursive algorithms.

I agree, except on some minute vocabulary use, but I will not bother you with this, unless necessary at some point.
Note that a universal machine can compute/emulate all algorithms, but of course not decide all provability question, and less so semantical question, but not less than us, apparently.





As Peter Shor keeps harping on superdeterminism, with its real nesting of fractal loops or orbits, implies a vast or even infinite number of degrees of freedom. This does appear to be a serious minefield to go through, However, if these are nonlocal they are not real degrees of freedom that communicate information. They respect the no-signaling theorem of QM. If we could really output all of these nested loops or paths this would be a sort of hypercomputation. But we can’t, I illustrate this with the Matiyasevich theorem in the uncomputability of p-adic sets,

I know (and teaches) Matiyasevic’s result that the diophantine polynomial equations are Turing Universal, and thus that Hilbert 10th problem is undedicadable (assuming CT). But I am not aware he worked on the p-adic numbers. If you have a link?






while Palmer appeals to a funny idea of uncomputability of fractal or recursively enumerable sets by Blum, Shub, and Smale.


OK. Unfortunately with a non standard notion of computability on the reals (or on any rings). They ahem shown that the Mandelbrot set, for example, is uneducable in that sense, but the question “is the (rational) Mandelbrot set Turing universal is still an open problem.




Hypercomputing is an interesting concept,

To be honest, I have not yet find a satisfying definition of “hyper-computation”.  It always look like computation + magic, which is not different from Turing computability + oracle. Note that all my results go through for the machine + oracle.
Or, in some case, hypercomputaion is more than that, but then all functions are computable, and it is not clear if this is meant classicaly, (in which case it is a trivial) or intutionistically, in which case we get a very restricted subset of the Turing-computable.



but spacetime configurations that permit it violate conditions such as Hawking-Penrose energy conditions or chronology protection. Quantum mechanics and general relativity have conditions that in some ways are equivalent. For instance, the no-cloning theorem of QM is equivalent to chronology protection, for a wormhole would permit quantum cloning of states.  

That is interesting. If you can explain the relation between non-cloning theorem (which I got from mechanism even before I heard about quantum mechanics), that would be interesting to get some “chronology protection” in arithmetic. It might help to fight the “white rabbits” which pullulated a priori the arithmetical reality. 




For hypercomputation a spacetime with closed timelike curves would suffice as well. The answer to an undecidable problem could come from a time machine if one sends the results back in time to yourself later. Anti-de Sitter spacetimes permit this. Curiously AdS and de Sitter (dS) spacetimes have the same quantum information, for the two spacetimes share asymptotic infinity. The de Sitter spacetime of inflation may then have a correspondence with an AdS in a quantum computing system. We may think of a computer with a closed timelike curve CTC register plus a chronology respecting register. As the two are quantum states or waves they then constructively and destructively interfere with each other. 

<quantum computer with closed timelike curves.png>


The CTC corresponds to the chronology violating AdS and the CR is chronology respecting register. The self-interference of quantum waves imprints a quantum computing output in the R_{ctc} and quantum information in the R_{cr} corresponding to it has constructive interference. This is then how quantum computing in quantum gravitation or cosmology may work.


Hmm… Once a machine is trapped on a loop, it can no more exploit its universality. Now, if the loop is gigantic, that does not matter in principle, FAPP, but it does matter in the derivation of the physical laws from the elementary arithmetical ontology (which is need to solve the mind-body problem in the Computationalist frame).




However, event horizons protect us from observing the data stack in R_{ctc} and this is then not hypercomputation. In this way spacetime and in general classical einselected outcomes occur, but we are shielded away from knowing how it occurs. It is not Turing computable. If theorems of QM and those of GR are formally equivalent, then this carries over to superdeterminism. This means there is no extra information we can obtain from superdeterminism that beats Gödel and Turing.


I agree.

Bruno




LC
 


LC
 


LC
 

-----Original Message-----
From: Lawrence Crowell <goldenfield...@gmail.com>
To: Everything List <everyth...@googlegroups.com>
Sent: Wed, Mar 11, 2020 10:31 am
Subject: Re: Reachability for infinite -time Turing machines with long tapes

On Tuesday, March 10, 2020 at 10:16:38 AM UTC-5, Philip Thrift wrote:

It looks to be a version of the busy beaver problem. The scale of the problem grows beyond computable bounds.

LC 

--
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/5aa35cd1-1ff2-4c5f-88b6-360ddb734e9a%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-li...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/8e3fbe02-a9d6-49bd-9915-4edc0ae11db7%40googlegroups.com.

Philip Thrift

unread,
Mar 16, 2020, 2:31:15 PM3/16/20
to Everything List
A question is not what anyone's theory of physics (their favorite equations) entails, but instead

What would be the kind of a collection of raw *data* (aka observations) from labs or telescopes or whatevers that would be needed to lead one to surmise a beyond-Turing theory would be needed (without any prior bias towards one's favorite theory)?

@philipthrift

Lawrence Crowell

unread,
Mar 16, 2020, 2:44:42 PM3/16/20
to Everything List
On Monday, March 16, 2020 at 9:24:17 AM UTC-5, Bruno Marchal wrote:

On 15 Mar 2020, at 16:39, Lawrence Crowell <goldenfield...@gmail.com> wrote:

This is from a post I wrote on Hossenfelder's blog:

Superdeterminism has characteristics very similar to hypercomputation. A hyper-Turing machine is one able to circumvent the restrictions of the Gödel-Turing uncomputability limit. A sort of Zeno machine may illustrate this. If I were to flip a switch at one second, then flip again at ½ second, then flip again at ¼ second and so forth, what is the state of the switch after 2 seconds? Well the rapid increase in energy required to oscillate the switch means that even if the switch does not fly apart it will face an energy limit where it is a black hole. Hence, at least from the outside general relativity appears to spoil the dream of circumventing Gödel and Turing.

What if we go into the black hole? The inner event horizon is in the pure eternal solution continuous with I^∞. This would permit a sort of Zeno computation to be observed. This means one could in principle witness this end of switch toggling. So, if that switch is toggled or not toggled with each half-partitioned integral of time any possible algorithm can be computed and its output logged. However, this idealism is spoiled by quantum mechanics, for the black hole will emit Hawking radiation and the inner horizon is no longer continuous with I^∞. Thus, quantum mechanics rescues Gödel and Turing, where both QM and GR appear to respect the Church-Turing thesis of computation so computed outputs are from first order primitive recursive algorithms.

I agree, except on some minute vocabulary use, but I will not bother you with this, unless necessary at some point.
Note that a universal machine can compute/emulate all algorithms, but of course not decide all provability question, and less so semantical question, but not less than us, apparently.



The UTM is an emulator, and it can't determine the halting status of all TMs. A part of the reason is that as an emulator it has to emulate itself emulating other TMs. which leads to the Cantor diagonal slash result.

 



As Peter Shor keeps harping on superdeterminism, with its real nesting of fractal loops or orbits, implies a vast or even infinite number of degrees of freedom. This does appear to be a serious minefield to go through, However, if these are nonlocal they are not real degrees of freedom that communicate information. They respect the no-signaling theorem of QM. If we could really output all of these nested loops or paths this would be a sort of hypercomputation. But we can’t, I illustrate this with the Matiyasevich theorem in the uncomputability of p-adic sets,

I know (and teaches) Matiyasevic’s result that the diophantine polynomial equations are Turing Universal, and thus that Hilbert 10th problem is undedicadable (assuming CT). But I am not aware he worked on the p-adic numbers. If you have a link?



The Gödel incompleteness comes with the p-adic number system used to define a field over this set or Cantor set. The set of frequencies or periodicities means this Cantor set in a certain “limit” has an unbounded set of primes for p-adic number systems. Then enters Martin Davis, Hilary Putnam, Julia Robinson and in particular Yuri Matiyasevich (DPRM). Hilbert asked if all Diophantine equations could be solved by a single method in his 10th problem. Diophantine equations were found to be equivalent to p-adic sets, and subsequently Yuri Matiyasevich proved these sets were not computable by a single method. This is a Gödel incompleteness result, where a proof for all possible p-adic is a form of Cantor diagonal slash. Solutions to Diophantine equations, which are associated with the nested frequencies or periodicities of orbits, can be solved locally, but there is no global solution method. This is a form of Szangolies’ epistemic horizon. The Cantor set here then has some undecidable properties in the p-adic setting, where any global field of numerical operations in a p-adic setting is incomplete. 

Martin Davis has a book on computability, Computability and Unsolvability and in a Dover edition, that on page 114 shows how all Diophantine equations are equivalent to a genera p-adic set. This was solved by DPR where M then used this in a Gödel incompleteness result. This is one of a few cases where Gödel incompleteness impacts what might be called real mathematics.
 




while Palmer appeals to a funny idea of uncomputability of fractal or recursively enumerable sets by Blum, Shub, and Smale.


OK. Unfortunately with a non standard notion of computability on the reals (or on any rings). They ahem shown that the Mandelbrot set, for example, is uneducable in that sense, but the question “is the (rational) Mandelbrot set Turing universal is still an open problem.



I have been arm wrestling with Hossenfelder and Palmer over this. This is a non-standard meaning to uncomputability, which defines recursively enumerable sets as uncomputable because a final output does not occur. It is really the complement that is uncomputable. This is why I much prefer the DPRM approach with p-adic sets.
 


Hypercomputing is an interesting concept,

To be honest, I have not yet find a satisfying definition of “hyper-computation”.  It always look like computation + magic, which is not different from Turing computability + oracle. Note that all my results go through for the machine + oracle.
Or, in some case, hypercomputaion is more than that, but then all functions are computable, and it is not clear if this is meant classicaly, (in which case it is a trivial) or intutionistically, in which case we get a very restricted subset of the Turing-computable.



A hyper-Turing machine is one able to circumvent the restrictions of the Gödel-Turing uncomputability limit. A sort of Zeno machine may illustrate this. If I were to flip a switch at one second, then flip again at ½ second, then flip again at ¼ second and so forth, what is the state of the switch after 2 seconds? Well the rapid increase in energy required to oscillate the switch means that even if the switch does not fly apart it will face an energy limit where it is a black hole. Hence, at least from the outside general relativity appears to spoil the dream of circumventing Gödel and Turing.

What if we go into the black hole? The inner event horizon is in the pure eternal solution continuous with I^∞. This would permit a sort of Zeno computation to be observed. This means one could in principle witness this end of switch toggling. So, if that switch is toggled or not toggled with each half-partitioned integral of time any possible algorithm can be computed and its output logged. However, this idealism is spoiled by quantum mechanics, for the black hole will emit Hawking radiation and the inner horizon is no longer continuous with I^∞. Thus, quantum mechanics rescues Gödel and Turing, where both QM and GR appear to respect the Church-Turing thesis of computation so computed outputs are from first order primitive recursive algorithms.
 
but spacetime configurations that permit it violate conditions such as Hawking-Penrose energy conditions or chronology protection. Quantum mechanics and general relativity have conditions that in some ways are equivalent. For instance, the no-cloning theorem of QM is equivalent to chronology protection, for a wormhole would permit quantum cloning of states.  

That is interesting. If you can explain the relation between non-cloning theorem (which I got from mechanism even before I heard about quantum mechanics), that would be interesting to get some “chronology protection” in arithmetic. It might help to fight the “white rabbits” which pullulated a priori the arithmetical reality. 



If you have a wormhole that connects two regions of spacetime in a multiply connected topological way, you can then accelerate one opening out to close to the speed of light and the accelerate it back and then to rest near the other opening. By the results of special relativity the clock on this opening you sent on this round trip will be behind the first. So if I jump into this opening I will exit the first opening back in time. Now suppose I have a quantum state |ψ⟩ = a|1⟩ + b|2⟩ and I duplicate this as |ψ⟩ → |ψ⟩|ψ⟩. However, there is an ambiguity here, for this duplication could occur in the |1⟩ and |2⟩ basis so that |1⟩ → |1⟩|1⟩ and |2⟩ → |2⟩|2⟩. These two duplications can easily be seen to be inequivalent. So this is not a unitary process. The impossibility of wormholes and violations of Hawking-Penrose energy conditions is at least consistent with there being no unitary means for duplicating quantum states.


For hypercomputation a spacetime with closed timelike curves would suffice as well. The answer to an undecidable problem could come from a time machine if one sends the results back in time to yourself later. Anti-de Sitter spacetimes permit this. Curiously AdS and de Sitter (dS) spacetimes have the same quantum information, for the two spacetimes share asymptotic infinity. The de Sitter spacetime of inflation may then have a correspondence with an AdS in a quantum computing system. We may think of a computer with a closed timelike curve CTC register plus a chronology respecting register. As the two are quantum states or waves they then constructively and destructively interfere with each other. 

quantum computer with closed timelike curves.png

<quantum computer with closed timelike curves.png>


The CTC corresponds to the chronology violating AdS and the CR is chronology respecting register. The self-interference of quantum waves imprints a quantum computing output in the R_{ctc} and quantum information in the R_{cr} corresponding to it has constructive interference. This is then how quantum computing in quantum gravitation or cosmology may work.


Hmm… Once a machine is trapped on a loop, it can no more exploit its universality. Now, if the loop is gigantic, that does not matter in principle, FAPP, but it does matter in the derivation of the physical laws from the elementary arithmetical ontology (which is need to solve the mind-body problem in the Computationalist frame).



The closed timelike curves of the AdS and the strange hypercomputing aspects of that are only commensurate with quantum computations in our observable dS, or local FLRW region thereof, spacetime because of this correlation between their asymptotic infinite information. After all Gödel's theorem does tell us that somethings are true by self-referential inference. We just can't causally compute them. It is like Peano arithmetic, we can always compute the successor of a natural number, but we can't compute the evident fact it is infinite. That is a sort of inference by induction, which is not strictly computable. The same happens here; we "frogish" observers in this patch on a de Sitter spacetime can't observe it all, which in effect enforces the Church-Turing thesis.

LC
Reply all
Reply to author
Forward
0 new messages