>>2761624most programmers work on easy problems, and problems that can be turned into easy ones. in planning, instead of finding the exact solution for a linear program, which is almost certainly NP, we can instead find an approximate solution, which is P
for an example of spooky things happening in the upper echelons of computing, look into the Busy Beaver problem. castorologists have identified Collatz-esque problems to be the big stumbling block at present, and this is for BB(6). that is, we do not know for how long the longest-running terminating 6-state Turing machine will actually run for
Wikipedia has a nice summary of why the Busy Beaver problem is mathematically relevant:
>One of the most consequential aspects of the busy beaver game is that, if it were possible to compute the functions Σ(n) and S(n) for all n, then this would resolve all mathematical conjectures which can be encoded in the form "does ⟨this Turing machine⟩ halt".[5] For example, there is a 27-state Turing machine that checks Goldbach's conjecture for each number and halts on a counterexample; if this machine did not halt after running for S(27) steps, then it must run forever, resolving the conjecture.[5][7] Many other problems, including the Riemann hypothesis (744 states) and the consistency of ZF set theory (745 states[8][9]), can be expressed in a similar form, where at most a countably infinite number of cases need to be checked.[5]this is the essence of the "32 bytes" claim in the beginning. 32*8 = 256 bits. a binary S-state Turing machine can be encoded in 2*S*log2(2*S+1) bits. all machines in BB(6) occupy a mere 45 bits, and this class of programs already contains a very hard problem (the Collatz conjecture). the 27-state Goldbach machine mentioned in the WP text would take 313 bits to encode, and it is likely not even the most difficult machine to reason about in that set
this isn't that important for cybernetics however. control theorists are concerned with practical problems