jacb · HackerTrans

hace 4 añosdiscuss

Ha! Certainly none of us will get anywhere close to this bound, no matter how much time we log in Anki. But the OP asked "Would an infinitely-long-lived, but forgetful person be able to recall an infinite number of facts using this method?", and the answer is a surprising "no, you turn into a black hole".

jacb

hace 4 añosdiscuss

More than semi-fallacious - the math doesn't add up, because you run into the Bekenstein bound, which limits how much information you can pack into a volume.

jacb

hace 6 añosdiscuss

Ah, I misunderstood you! I apologize. :)

jacb

hace 6 añosdiscuss

That's not how arguments from contradiction work. You've assumed H (halting problem is decidable), prove B (beauty decidable), then say "but actually !H, therefore !B". All you've proven is that H => B. An actual argument from contradiction is "assume H, using H we can prove an obviously false statement, therefore not-H". And indeed, you have assumed something false (H), and shown a contradiction (various proofs for !H), so your original assumption was wrong (!H).

A concrete example: say Beauty(R,D) is trivially decidable (say it returns (popcount(R)+popcount(D))%2. Your argument "proves" this property is undecidable, but it's definitely decidable. So some step in your argument is wrong.

Another concrete example: Assume the halting problem is decidable. I would like a cookie. But the halting problem is not decidable. Therefore I would not like a cookie.

jacb

hace 6 añosdiscuss

I might be missing something - why would this be a breakthrough? It sounds complicated to generate the interfaces, sure, but is there a theoretical problem blocking this, or just practical?

jacb

hace 6 añosdiscuss

https://www.microcovid.org/ is a similar tool, with more knobs to adjust risk factors (distance, outside vs inside, the other person's risk profile, etc.). Friends living in shared apartments have used it to budget, estimate and manage their risk from different activities. Seems like a neat tool.

jacb

hace 6 añosdiscuss

This is really upsetting. I didn't go to TJHS, but the sense I got from the three people I know who did was that it had that critical mass of nerdy science-and-tech-obsessed teenagers.

At least in Canada, it's more common to have smaller programs operating within a larger high school - my program was 30 people, mostly humanities kids with maybe 8-10 STEM kids. There wasn't anything approaching that sort of critical mass. Plus, as a subset of a smaller school, you still had to play politics with everyone else. TJHS always sounded like one of the only places that, somehow, did have that critical mass and managed to maintain it for decades.

Maybe this sort of public school is just politically infeasible now - which is a pity, since locating and nurturing the talents of disadvantaged youth benefits all of us.

jacb

hace 6 añosdiscuss

> The problem is, increasing taxes on gas will disproportionately affect the poor who can't afford to buy an EV (and again, are unlikely to live somewhere with a charger)

But banning ICE cars is clearly even worse for those unable to afford an EV, right? Unless policy-makers think that precommitting to ban ICE cars by 2035 will lead to a sudden flurry of new EV development _that wouldn't have happened if they had just precommitted to adding large carbon taxes by 2035.

jacb

hace 6 añosdiscuss

Perhaps it's consistent with computation being done in many "parallel universes," but with heavily restricted communication - in this model it's almost trivial to parallelize work (flip a quantum coin, do A if heads else B), what's tough is making sure that you don't get parallelized along with the work (i.e. that you don't become entangled with the computation) and making sure there's a way to accumulate the parallel computation into something that's singly-readable and useful.

jacb

hace 6 añosdiscuss

> how well a compiler does is mostly dependent on how many of those transformations happen to apply to your program at hand

Right, there's an infinite number of distinct useful code optimizations, there's a cost to checking if any given optimization can be applied, and some optimizations have _massive_ costs for very rare and specific savings, so any given compiler is making a practical decision to include some optimizations and omit others. There was some discussion in the Rust community about LLVM having a period where they weren't tracking regressions in compile times - so "the perfect optimizing compiler" isn't really a coherent goal. But I still wonder how much faster Optimal Chromium would be. Just another interesting number I'll never know, I suppose.

> I think it's almost certainly not even in NP

Yeah, that was sloppy of me, I think this is undecidable by Rice's theorem. Nice catch!

jacb

hace 6 añosdiscuss

Have there been attempts to measure modern compilers' ability to optimize large programs against "perfect" machine code? The few times I've poked through demo scene binaries, I've felt a sense of awe at the complexity described by just a few instructions, but demos aren't starting from a specification and trying to find a compressed representation, they're trying to create small binaries that expand into something complex and interesting. Clearly this problem is NP-hard as hell (and most software doesn't need to be optimized instruction-by-instruction), but it would be incredibly neat to have an estimate of _how much worse_ our compilers might be.

I'm reminded of the old story about someone who tried to evolve an FPGA configuration to perform signal processing, and the final generation exploited imperfections in the chip to use fewer gates.

jacb

hace 6 añosdiscuss

It seems like a common misconception that humans have some secret power to solve undecidable problems that computers lack. But "this problem is undecidable in general" doesn't mean "computers cannot solve small instances of the problem", it means "there's no single algorithm that will correctly solve all instances of this problem". Typically undecidability results in language theory rely on embedding a Turing machine in the language and going "Turing machines halting is undecidable, therefore this is undecidable in general". But this only tells you that _some_ problem instances are undecidable (at least those that correspond to Turing machine embeddings, and probably many more). Smaller problems (that aren't big enough to be disguised Turing machines) can still be decidable, and I suspect that any problem simple enough to happen in an exam is decidable.

Another example of this: theorem-proving is undecidable, yet automated thoerem provers are definitely capable of solving simple problems. The undecidability result means that any given automated theorem provers isn't capable of proving the truth/falsity of all statements. But this isn't some crazy limitation - this is true of humans as well. You can solve some math problems, but if someone showed up with an exabyte-long statement about how a problem-solver-who-is-identical-to-you-in-every-capability solves problems and asked you to prove it, obviously you wouldn't be able to do that.

jacb

hace 6 añosdiscuss

That's a good point! I guess you'd still have to make sure that variants with alignment requirements don't get unaligned. One way to do that would be to add leading padding if they follow an unaligned variant. Adds some complexity to the representation, I guess, and I suspect there's other ways of doing it. Neat problem.

jacb

hace 6 añosdiscuss

If you want random access into an array of enums, you need them all to be the same size (there are also alignment concerns, which is why it's tough to use only 1 bit of overhead to discriminate an enum with two variants). I guess you could add indirection and have an enum with variants A(Box<AType>), B(Box<BType>), etc. This is good practice if you care about space and you have a variant with a type that's a few hundred bytes (not heap-allocated like with Vec). But it's not worth adding the indirection and potential cache miss to save a byte, when most cache lines can fit at least 32 bytes.

comments