Busy Beaver

[DT_]

Could God compute BB(10^100)?

https://www.scottaaronson.com/papers/bb.pdf

https://plato.stanford.edu/entries/turing-machine/#CompTuriMach

Edited August 24, 2022 by DT_

[ksfisher]

6 minutes ago, DT_ said:

Could God compute BB(10^100)?

https://www.scottaaronson.com/papers/bb.pdf

You'd have to ask Him.

[DT_]

2 hours ago, ksfisher said:

You'd have to ask Him.

I'm interested in your opinion.

Edited August 24, 2022 by DT_

[ksfisher]

3 minutes ago, DT_ said:

I'm interested in your opinion.

I would say that I'm unqualified to answer. 

[webbles]

3 hours ago, DT_ said:

Could God compute BB(10^100)?

https://www.scottaaronson.com/papers/bb.pdf

https://plato.stanford.edu/entries/turing-machine/#CompTuriMach

Interesting question.  I think humans might be able to solve it at some point if we can solve P=NP and then figure out quantum computers.  There might be a non-quantum solution to it but using math that we haven't discovered.  So, since I think humans be able to pull it off at some point, then I would say that God can compute it.

[DT_]

5 hours ago, ksfisher said:

I would say that I'm unqualified to answer. 

Do you believe God is all-powerful?

[DT_]

4 hours ago, webbles said:

 then figure out quantum computers. 

As you are probably aware, the Busy Beaver function is not computable by algorithm, see the proof by contradiction. [1] Why do you think quantum computers would change that?

[1]https://math.mit.edu/research/highschool/primes/circle/documents/2022/Esther & Sarah.pdf

4 hours ago, webbles said:

Interesting question.  I think humans might be able to solve it

I think I have to disagree here. Assuming BB is computable, it still wouldn't be possible to solve BB (10^100) because it's too big. Maybe up to BB (5), but not BB (10^100).

[webbles]

1 hour ago, DT_ said:

As you are probably aware, the Busy Beaver function is not computable by algorithm, see the proof by contradiction. [1] Why do you think quantum computers would change that?

[1]https://math.mit.edu/research/highschool/primes/circle/documents/2022/Esther & Sarah.pdf

I think I have to disagree here. Assuming BB is computable, it still wouldn't be possible to solve BB (10^100) because it's too big. Maybe up to BB (5), but not BB (10^100).

Yes, I'm aware of that.  It is uncomputable by Turing machines.  So we have to figure out something that isn't Turing machines.  Our current understanding of quantum computing has them as Turing machines but there is an idea of so-called "hypercomputation" using quantum.  It is purely theoretical at this point and a lot of people don't believe it is possible, but there have been some work in whether it could happen.  See https://en.wikipedia.org/wiki/Hypercomputation#Quantum_models

[DT_]

21 hours ago, webbles said:

Yes, I'm aware of that.  It is uncomputable by Turing machines.

Correct. Turing machines (theoretical) simulate computer algorithms.

21 hours ago, webbles said:

 Our current understanding of quantum computing has them as Turing machines but there is an idea of so-called "hypercomputation" using quantum.  It is purely theoretical at this point and a lot of people don't believe it is possible, but there have been some work in whether it could happen.  See https://en.wikipedia.org/wiki/Hypercomputation#Quantum_models

Very interesting! I'll have to read about that.

21 hours ago, webbles said:

 So we have to figure out something that isn't Turing machines. 

I agree. Do you think God would know the maximum number of 1s printed by BB (10^100)?

Edited August 25, 2022 by DT_

[webbles]

27 minutes ago, DT_ said:

I agree. Do you think God would know the maximum number of 1's printed by BB (10^100)?

What 1s are we talking about?  The number of 1s in the number of steps (and is this binary, decimal, hex, etc) or the number of 1s in the tape (and is this 2, 3, 4, etc symbol BB)?

Technically, human technology can solve this but it will just take an infinity (probably lots of infinities).  Since God has infinity plus access to much more powerful computers (and possibly theoretical hypercomputers and maybe things we haven't yet imagined), I would say that yes, He could calculate that.  Does He just know it?  I'm not a believer of true omniscience so I can go either way.

[Stargazer]

20 hours ago, webbles said:

if we can solve P=NP

That made me laugh heartily!

[Stargazer]

On 8/24/2022 at 3:36 PM, DT_ said:

Could God compute BB(10^100)?

https://www.scottaaronson.com/papers/bb.pdf

https://plato.stanford.edu/entries/turing-machine/#CompTuriMach

I have every faith that He could. Don't ask me how.

But why would He want to?

Edited August 25, 2022 by Stargazer

[Stargazer]

On 8/24/2022 at 3:36 PM, DT_ said:

Could God compute BB(10^100)?

https://www.scottaaronson.com/papers/bb.pdf

https://plato.stanford.edu/entries/turing-machine/#CompTuriMach

This is a non-sequitur, but your post reminds me of the famous Arthur C. Clarke short story, "The Nine Billion Names of God". <-- see the link for a description.

Inasmuch as the story is about Tibetan lamas, it might be worth pointing out that in the 2003, Clarke reported having been told that the Dalai Lama had read the story and wrote the author a "charming letter" in response to it, in which he said he found the story "very amusing."

Edited August 25, 2022 by Stargazer

[DT_]

18 hours ago, webbles said:

What 1s are we talking about?  The number of 1s in the number of steps (and is this binary, decimal, hex, etc) or the number of 1s in the tape (and is this 2, 3, 4, etc symbol BB)?

The maximum number of 1s that can be printed (in the finished tape) with a 10^100-state, 2-color halting Turing machine starting from a blank tape before halting. Here's a helpful source

https://en.wikipedia.org/wiki/Busy_beaver#Known_values_for_Σ_and_S

18 hours ago, webbles said:

Technically, human technology can solve this but it will just take an infinity (probably lots of infinities).  Since God has infinity plus access to much more powerful computers (and possibly theoretical hypercomputers and maybe things we haven't yet imagined), I would say that yes, He could calculate that.  Does He just know it?  I'm not a believer of true omniscience so I can go either way.

Interesting. 

BB (6) is already bigger than the universe, so do you think God would need an infinite-size computer to calculate BB (10^100) in less than one minute?  

Edited August 25, 2022 by DT_

[DT_]

7 hours ago, Stargazer said:

I have every faith that He could. Don't ask me how.

I honestly didn't expect that answer from you. You previously told me God can't count to infinity.

BB (6) is already unimaginably bigger than our universe, BB (10^100) is incomprehensible.  

https://en.wikipedia.org/wiki/Busy_beaver#Known_values_for_Σ_and_S

Edited August 25, 2022 by DT_

[pogi]

So this is where the nerds hang out! 

[CV75]

On 8/24/2022 at 10:36 AM, DT_ said:

Could God compute BB(10^100)?

https://www.scottaaronson.com/papers/bb.pdf

https://plato.stanford.edu/entries/turing-machine/#CompTuriMach

I challenge you to ask God!

[webbles]

2 hours ago, DT_ said:

BB (6) is already bigger than the universe, so do you think God would need an infinite-size computer to calculate BB (10^100) in less than one minute?  

In less than one minute?  I have no idea.  But considering we are now dealing with infinite-size computers, I think we've gone way past the theoretical.  If I had an infinite amount of infinite-size computers in an infinite-cluster that can do infinite calculations in 1/infinite seconds, I think it can be calculated in less than one minute.

Edited to add: someone needs to come up with a unit of time that means 10^(-1*infinity) seconds.  It would really help in discussing this topic

Edited August 26, 2022 by webbles

[Stargazer]

2 hours ago, DT_ said:

I honestly didn't expect that answer from you. You previously told me God can't count to infinity.

BB (6) is already unimaginably bigger than our universe, BB (10^100) is incomprehensible.  

https://en.wikipedia.org/wiki/Busy_beaver#Known_values_for_Σ_and_S

God can't count to infinity, because it's impossible to count to infinity, because infinity can never be reached. But BB(10^100)? It's huge, sure, but it's still not infinity.

Look, writing out a googolplex, a 1 followed by a googol zeroes, where we use every single elementary particle in the universe to represent one of the zeroes, would require a googol particles. However, aside from dark matter, there are only 10^97 (a high estimate) elementary particles existing in the visible universe, so there wouldn't be enough. Obviously a googolplex is a pip compared to BB(10^100). I don't think we could calculate how many similar universes God would have to create in order to represent it. Maybe God could actually calculate it. 

But again I ask: why would God want to count it? Why would He need to count it? Surely He has more important things to do?

If you really wanted to know, perhaps he would hand you an infinite whiteboard and an infinite marker and say: "Start counting! Let me know what you find out!" Perhaps that is the customized hell He has planned for you!

Surely God has a sense of humor. He created you, after all! 😄 

Edited August 26, 2022 by Stargazer

[Stargazer]

35 minutes ago, webbles said:

In less than one minute?  I have no idea.  But considering we are now dealing with infinite-size computers, I think we've gone way past the theoretical.  If I had an infinite amount of infinite-size computers in an infinite-cluster that can do infinite calculations in 1/infinite seconds, I think it can be calculated in less than one minute.

Edited to add: someone needs to come up with a unit of time that means 10^(-1*infinity) seconds.  It would really help in discussing this topic

Nice try!

10^(-1*infinity) seconds is indefinable, because infinity is not a number. Ten to the power of minus (something approaching infinity) is infinitely shorter than the shortest possible interval of time, which is the Planck time. In other words, it's impossible, and hence of no help at all in discussing this topic. 😁

The Planck time tP is the time required for light to travel a distance of 1 Planck length in a vacuum, which is a time interval of approximately 5.39×10−44 s. That is the shortest possible time interval. In this universe, at least.

Edited August 26, 2022 by Stargazer

[Stargazer]

I have a question to ask @DT_.

Do you think, if God existed, that he could solve P = NP? There's a prize for the first valid solution.

It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution. What would God do with His winnings?

Perhaps He has already solved it, but is leaving the solution to us as an exercise?

[DT_]

18 hours ago, webbles said:

Edited to add: someone needs to come up with a unit of time that means 10^(-1*infinity) seconds.  It would really help in discussing this topic

Indeed. 

[DT_]

18 hours ago, Stargazer said:

God can't count to infinity, because it's impossible to count to infinity, because infinity can never be reached. But BB(10^100)? It's huge, sure, but it's still not infinity.

How many finite numbers are possible in the real world? Can God count them all?

18 hours ago, Stargazer said:

Perhaps that is the customized hell He has planned for you!

I wouldn't doubt it.

18 hours ago, Stargazer said:

Do you think, if God existed, that he could solve P = NP? There's a prize for the first valid solution.

To give you my best guess you would have to define God. I'm not convinced P = NP, I hope it's true, but we simply don't know. 

[ksfisher]

1 hour ago, DT_ said:

How many finite numbers are possible in the real world? Can God count them all?

You seem very concerned with God's qualifications as a mathematician. 

[Stargazer]

1 hour ago, DT_ said:

How many finite numbers are possible in the real world? Can God count them all?

I can't tell you how many finite numbers are possible in the real world, but I don't think the real world has numbers at all. Numbers are concepts or ideas. They have no existence outside of our imaginations. They are abstract, not material.

1 hour ago, DT_ said:

To give you my best guess you would have to define God. I'm not convinced P = NP, I hope it's true, but we simply don't know. 

I have kind of defined God here, somewhat at least. 

As for the P = NP problem, as I understand it, it is widely believed among mathematicians that P ≠ NP.