News for hackers. Stuff that matters.
Re:BB(3, 3) is Hard by neilkk on Tuesday October 17, 2023 @08:19AM (#37913834)
I think the point here is that it was not known whether all 3,3 halting problems are reducible to trivial Collatz-like problems. Unless someone is able to observe that sligicko's is actually trivial, then this provides a counterexample.
Re:BB(3, 3) is Hard by FartyMcFarter on Tuesday October 17, 2023 @08:56AM (#37914212)
> 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.

Re:BB(3, 3) is Hard by neilkk on Tuesday October 17, 2023 @09:16AM (#37914519)
'trivial' isn't a mathematical concept. If no one has shown why this problem is trivial, it isn't trivial.
Re:BB(3, 3) is Hard by FartyMcFarter on Thursday October 19, 2023 @07:28AM (#37941353)
This problem isn't trivial, but neither are the ones we could already reduce BB(3, 3) to (via Conway's construction).
Re:BB(3, 3) is Hard by neilkk on Saturday October 21, 2023 @08:25AM (#37966233)
Some reductions via Conway's method give non-trivial Collatz problems even though other simple techniques should the halting question for those machines to be trivial; the Conway reduction sometimes reduces trivial Turing machines to non-trivial Collatz problems.