How the Slowest Computer Programs Illuminate Math’s Fundamental Limits

Re:How the Slowest Computer Programs Illuminate Math’s Funda... by lisper on Friday December 11, 2020 @03:07PM (#25390281)

> Note that under this definition when the machine halts it does NOT write the tape or move the head.

That's a good point. This is a more parsimonious definition because if it's going to halt we don't really care what it does immediately before.

I guess the real lesson here is that it's pointless to quibble about this because the number turns on arbitrary features of your definitions. (Also, if you think Scott Aaronson has made a mistake, even a trivial one, you are almost certainly wrong :-)

[ Parent | on HN ]

Re:How the Slowest Computer Programs Illuminate Math’s Funda... by tromp on Friday December 11, 2020 @03:56PM (#25390881)

> if it's going to halt we don't really care what it does immediately before.

The final move does not matter, but the symbol written matters to the extent that BB(n) is defined as the number of 1s on the tape upon halting.

So, while redundant, the 4(n+1) count is chosen for parsimony. If one is willing to specialize the transition to halt to have no move and a mandatory write of 1, then a count of 4n+1 still agrees upon the same value of BB(n).

[ Parent | on HN ]

Re:How the Slowest Computer Programs Illuminate Math’s Funda... by lisper on Friday December 11, 2020 @04:10PM (#25391037)

Is there really any point in quibbling over a difference of +/- 1 when contemplating (because that's really all we can do) the value of BB(n)?

[ Parent | on HN ]