3 ms·
That is the entire basically the entire concept of complexity theory. The reals are compressed into the computable reals. The real numbers are un-computable 'a
by nyrikki 3y ago
That is the entire basically the entire concept of complexity theory.
The reals are compressed into the computable reals. The real numbers are un-computable 'almost everywhere'
Semi-decidabity is just recursively enumerable that gets you to finite time with unlimited resources.
NP-hard is brute forcible in exponential time, with most likely no approximate polynomial reductions.
P has exact polynomial time reductions...
Most code is made of IF and FOR loops, because that produces primitive recursive functions, which are most of the intuitive computable functions that always halt.
The problem becomes with complex systems where you need to balance coupling with cohesion along with free variables, WHILE and GOTO.
Note that the above compression was lossy.
If you consider that information loss as setting constraints through heuristics, (educated guesses) those constraints may or may not work for a particular use case.
The problem with how we often try to set coding style is that we want simple universal rules.
Unless you have a system that fits in with those ideals all the time that is problematic.
Gödel demonstrated that isn't possible for complex systems. Either our rules will be inconsistent or incomplete.
This is why I think selling conventions as ideals, that need to yield to less preferred cohesion models when appropriate is the real solution.
Unfortunately that requires a lot more thought and vigilance.
Functional cohesion with loose coupling is what we shoot for when it is appropriate, but not as a hard fast rule.