Nov 11, 2018

I'd recommend reading the relevant portions (or just all of) this paper:

The conventional way of knowing a number is specifying it in a way that we can quickly determine what it is and operate on it.

If I say "the next prime after 9^9^9^9^9^9^9^9^9", or indeed "the next prime after busy beaver(1000)" I have specified a precise number. But you don't think I have it in any useful sense, because I can't compute it quickly (or in my second example at all).

Edit: And it should be noted that the above is more akin to the busy beaver example, no matter how long you operate that turing machine, if M' happens to be of the sort that doesn't halt but doesn't provably not halt, then you will never be able to tell me whether the number I "have" is 0 or pi.

Jun 29, 2018

Thanks! This is indeed related and part of my inspiration for this question.

Some other interesting references:

- The waterfall argument in paragraph 6 of the mind-boggling "Why Philosophers Should Care About Computational Complexity".

- "NP-complete Problems and Physical Reality"

May 30, 2018

See also this fascinating paper by Scott Aaronson [1].

[1] Aaronson, Scott. Why Philosophers Should Care About Computer Science.

Mar 19, 2018

Using logic similar to chapter six of , though, you can still draw a meaningful distinction between a normal JPG decoder, and your proposed JPG decoder that interprets the Declaration of Independence as illegal child porn. Your decoder must inevitably have a much higher information content in it, and is a "reduction doing all the work" in that case. So while you've got a mathematical point (no sarcasm, I understand what you are getting at), even on purely mathematical grounds I can argue a meaningful distinction; legally it'll be even easier.

Interestingly, it's a distinction that happens to more-or-less match our own intuitions about the situation, which is something interesting to ruminate about a bit.