Post #2298374
2026-03-02 15:12 UTC
@stylus@social.afront.org that probabilistic argument _sounds_ like a joke to me. Arguments of that kind have their place; for example, the general belief that there are likely to be infinitely many Mersenne primes and finitely many Fermat ones is derived from just that kind of argument, based on how many candidate numbers there are and (under a natural random model of primality) what probability each one has of being prime. But it's hard to see how you'd have any prior judgment at all of the probability of a randomly selected program solving a problem you have no idea how to solve. It's hard enough to make a guess at how likely a random program is to solve a problem you _do_ know how to solve!
Replies (1)
-
@stylus@social.afront.org 2026-03-02 16:22
@simontatham@hachyderm.io Ah wikipedia has a link to the discussion I'm thinking of. It's actually an expression of pessmism about settling the question of P=NP. As you say, I've come to believe that P = NP, namely that there does exist an integer M and an algorithm 𝒜 that will solve every n-bit problem belonging to the class N P in nM elementary steps. [...]Although I think M probably exists, I also think human beings will never know such a value. (Knuth, 2014)