Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

BB(3, 3) is Hard

sligocki.com

Post reply on HN
Print view View original

101–110 of 146 posts

Re: BB(3, 3) is Hard

#101

Post by neilkk »

dullcrisp wrote: post #69
l33t7332273 wrote: post #56

Earlier quoted context omitted.

Oh, sure. I was just pointing out that the hardness is in determining the busy beaver number and that it didn’t matter if your algorithm halts iff ZFC is consistent or if it’s an algorithm that halts iff ZFC is inconsistent.

No, if you had an algorithm that (you could prove) halts iff ZFC is consistent, then if that algorithm halts, you’ll have a proof that ZFC is consistent, which isn’t possible. Thus, the existence of such an algorithm would be a contradiction that proves the inconsistency of ZFC. The problem with your construction is that it relies on knowing the value of BB(754), which is impossible to know so long as ZFC is consiste…

The intuition is that a monkey typing randomly on a typewriter can come up with texts which either are or aren't valid proofs of ZFC or not, and each one which is a valid proof either is a proof of a contradiction or not. To check either of these things is mechanical. If ZFC is inconsistent, eventually the monkey should hit on the inconsistency.

Re: BB(3, 3) is Hard

#102

Post by adrianN »

smaudet wrote: post #86
Sharlin wrote: post #68

Earlier quoted context omitted.

It doesn't matter whether we can physically do it, as long as we can mathematically do it. In math running a TM for an arbitrary, finite number of steps is not a problem. The actual answer to OP's question was given in one of the other subthreads, namely: the result tells us that BB(754) is not computable in ZFC. Some 754-state TMs halt, others run forever, but there is no way to figure out (without an oracle) which…

>"It doesn't matter whether we can physically do it," Hmm. I'm not sure that I agree - philosophically if you could prove that something is computable mathematically and yet at the same time know that physically it cannot be done due to the laws of physics, I would say that imposes a "second order" halting problem. By which I mean if you had some mathematical algorithm that could be proven to tell you some property o…

If you restrict yourself to problems that fit in the physical universe, everything can be done using finite automata. That’s a bit boring.

Re: BB(3, 3) is Hard

#103

Post by auggierose »

thaumasiotes wrote: post #71
auggierose wrote: post #62

Earlier quoted context omitted.

Interesting, Sipser starts the natural numbers with 1 in this book, instead of 0. I like this choice, and I would like to use it myself. But if ℕ starts with 1, what do I call {0} ∪ ℕ? I guess ℕ₀ is a reasonable choice.

> I like this choice, and I would like to use it myself. It's not a great choice, purely for the reason that there's already a convenient name for the positive integers, ℤ⁺.

I've just checked with a few math books I like, and they are using ℕ and ℕ₀ throughout. What I don't like about ℤ⁺ is that 1) it talks about integers, although negative numbers might not be relevant in the current context at all, and 2) it's not really clear if ℤ⁺ denotes ℕ or ℕ₀. Of course, you have the same ambiguity problem with ℕ.

Oh, see how I numbered this 1) and 2), not 0) and 1)?

Re: BB(3, 3) is Hard

#104

Post by sligocki »

FartyMcFarter wrote: post #84
sligocki wrote: post #35

Earlier quoted context omitted.

Yeah, I've oversimplified a bit with this title. The more accurate statement is in the first paragraph of the article: "Solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem." I also agree somewhat on the one trajectory vs. multiple trajectories point. However, note that (assuming we live in the world where this TM never halts) proving a single trajectory in this system is "harder" tha…

> "Solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem." > How hard is this Collatz-like problem? Well, let's see if anyone can solve it :) I thought John Conway already proved that all instances of the halting problem can be converted to a Collatz-like problem [1]. So one could say this about all BB values, not just BB(3, 3). Some will be easy, some will be hard, but all are reducib…

You are right that every TM can be converted into a Collatz-like problem using Conway's Fractran compilation. So technically the statement "Solving the BB(n, k) problem is at least as hard as solving a Collatz-like problem." is true in general.

However, the Collatz-like problems you will get from this completion will be gigantic, they will not have distilled the problem into a similar description of it's behavior, but instead created a more complicated way of observing that behavior. The Collatz-like problem I present here is a simplification of the behavior of this TM. If you observe the machine running you will see that it is effectively completing these transitions.

In other words, I am not arbitrarily choosing to convert this to a Collatz-like problem simply because it is possible. I am looking at the behavior of this machine and that behavior turns out to be Collatz-like naturally.

Of course none of this proves that my Collatz-like problem really is hard ... but as someone else here mentioned, being hard is not a mathematical thing, it is a belief we have about certain problems we cannot solve after considerable effort.

Re: BB(3, 3) is Hard

#105

Post by [deleted] »

neilkk wrote: post #98
FartyMcFarter wrote: post #96

Earlier quoted context omitted.

> I think the point here is that it was not known whether all 3,3 halting problems are reducible to trivial Collatz-like problems. True, but it still isn't known either way. Nothing changed in that regard.

'trivial' isn't a mathematical concept. If no one has shown why this problem is trivial, it isn't trivial.

[deleted]

Re: BB(3, 3) is Hard

#106

Post by thaumasiotes »

auggierose wrote: post #103
thaumasiotes wrote: post #71

Earlier quoted context omitted.

> I like this choice, and I would like to use it myself. It's not a great choice, purely for the reason that there's already a convenient name for the positive integers, ℤ⁺.

I've just checked with a few math books I like, and they are using ℕ and ℕ₀ throughout. What I don't like about ℤ⁺ is that 1) it talks about integers, although negative numbers might not be relevant in the current context at all, and 2) it's not really clear if ℤ⁺ denotes ℕ or ℕ₀. Of course, you have the same ambiguity problem with ℕ. Oh, see how I numbered this 1) and 2), not 0) and 1)?

> Oh, see how I numbered this 1) and 2), not 0) and 1)?

So what?

> 2) it's not really clear if ℤ⁺ denotes ℕ or ℕ₀.

On the contrary. ℕ is ambiguous between the positive integers and nonnegative integers, though in my experience it's usually the nonnegative integers.

But ℤ⁺ is absolutely unambiguous. It's the positive integers.

And since you frequently need to refer to the nonnegatives, it makes sense to have a symbol for them too. There's almost no benefit to having ℕ available as a synonym for ℤ⁺. There's a lot of benefit to having it available as a synonym for ℤ\ℤ⁻.

Re: BB(3, 3) is Hard

#107

Post by Pet_Ant »

abetusk wrote: post #73

BB(3,3) is busy beaver (BB) problem, a subset of Turing machines (TM) [0], with 3 states (A,B,C) and three symbols (0,1,2) that can be written onto the infinitely long tape. An additional criteria for a Busy Beaver-like Turing machine is that there is a "halt" state, which can be seen in the article's table for state C reading input 0. The table in the article (under "The Machine" section) describes the state on the…

Why does BB sometimes take one number and sometimes 2? What is the difference between BB(3,3) and BB(3)?

Re: BB(3, 3) is Hard

#108

Post by irchans »

smaudet wrote: post #86
Sharlin wrote: post #68

Earlier quoted context omitted.

It doesn't matter whether we can physically do it, as long as we can mathematically do it. In math running a TM for an arbitrary, finite number of steps is not a problem. The actual answer to OP's question was given in one of the other subthreads, namely: the result tells us that BB(754) is not computable in ZFC. Some 754-state TMs halt, others run forever, but there is no way to figure out (without an oracle) which…

>"It doesn't matter whether we can physically do it," Hmm. I'm not sure that I agree - philosophically if you could prove that something is computable mathematically and yet at the same time know that physically it cannot be done due to the laws of physics, I would say that imposes a "second order" halting problem. By which I mean if you had some mathematical algorithm that could be proven to tell you some property o…

I think that it would be fairly easy (meaning that I think I could do it in 8 hours) to build a Turing Machine that prints 10^1000 1's on its tape and then halts. We would not be able to construct and run physical Turing machine that could do every move physically (by moving electrons) within 100 billion years, but we can still write the proof that it halts, probably with less than 3 pages. (In fact, we could probably tell you which state it is in for any i in the set {1, ...., halting step} without ever constructing and running a physical machine.)

On the other hand, if the "shortest" proof of halting is more than 10^20 pages long, then we would have major problems "writing" it.

Re: BB(3, 3) is Hard

#109

Post by FartyMcFarter »

Pet_Ant wrote: post #107
abetusk wrote: post #73

BB(3,3) is busy beaver (BB) problem, a subset of Turing machines (TM) [0], with 3 states (A,B,C) and three symbols (0,1,2) that can be written onto the infinitely long tape. An additional criteria for a Busy Beaver-like Turing machine is that there is a "halt" state, which can be seen in the article's table for state C reading input 0. The table in the article (under "The Machine" section) describes the state on the…

Why does BB sometimes take one number and sometimes 2? What is the difference between BB(3,3) and BB(3)?

BB(n) refers to Turing machines that have n states and 2 symbols. The version with two arguments lets you specify the number of states and the number of symbols respectively.

So BB(n) = BB(n, 2) .

Re: BB(3, 3) is Hard

#110

Post by auggierose »

thaumasiotes wrote: post #106
auggierose wrote: post #103

Earlier quoted context omitted.

I've just checked with a few math books I like, and they are using ℕ and ℕ₀ throughout. What I don't like about ℤ⁺ is that 1) it talks about integers, although negative numbers might not be relevant in the current context at all, and 2) it's not really clear if ℤ⁺ denotes ℕ or ℕ₀. Of course, you have the same ambiguity problem with ℕ. Oh, see how I numbered this 1) and 2), not 0) and 1)?

> Oh, see how I numbered this 1) and 2), not 0) and 1)? So what? > 2) it's not really clear if ℤ⁺ denotes ℕ or ℕ₀. On the contrary. ℕ is ambiguous between the positive integers and nonnegative integers, though in my experience it's usually the nonnegative integers. But ℤ⁺ is absolutely unambiguous. It's the positive integers. And since you frequently need to refer to the nonnegatives, it makes sense to have a symbol…

> So what?

Well, it means I usually need either ℕ or ℤ, not ℕ₀.

> And since you frequently need to refer to the nonnegatives

It depends on the context. You don't use ℕ₀ much, if you agree that counting starts at 1. You then use either ℕ or ℤ, which just looks cleaner. No reason to complicate such a simple concept as {1, 2, 3, ...} with something complicated such as ℤ⁺. As I said before, to understand {1, 2, 3, ...}, you don't need the concept of negative numbers at all, so why drag it in through confusing symbols?

> But ℤ⁺ is absolutely unambiguous. It's the positive integers.

Or the non-negative integers. And that's not just my opinion. Here is what ChatGPT has to say about that:

*system*: You are a mathematics professor, and happy to chat about mathematics and the philosophy of mathematics.

--------------------

*user*: What would you say ℤ⁺ stands for? Are there multiple options?

--------------------

*assistant*: ℤ⁺ typically stands for the set of positive integers. This usually includes all the whole numbers greater than zero. However, there can be some variation in its definition depending on the context.

In some contexts, ℤ⁺ might be defined to include zero, so it would represent the set of non-negative integers. This is less common, but it does occur in some areas of mathematics.

The symbol ℤ comes from the German word "Zahlen," which means "numbers." The superscript "+" is used to denote that we're only considering the positive members of this set (or non-negative, in some cases).

So, yes, there can be multiple options for what ℤ⁺ represents, but they are all closely related. It's always a good idea to clarify these kinds of notational issues when they arise, to avoid any potential confusion.

Post reply on HN