3 ms·
> The result becomes less weird when you realize that that almost all functions from string -> boolean are not expressible as a program. I think this is one of
by pdpi 1y ago
> The result becomes less weird when you realize that that almost all functions from string -> boolean are not expressible as a program.
I think this is one of those cases where a maths background makes computer science much easier. It only takes enough calculus to get you to entry level differential equations before you’re confronted with the fact that most functions ℝ → ℝ aren’t elementary functions (or admit any closed-form expression at all). In a certain sense, “program” is really just a weird word for “closed-form expression”.
- tliltocatl 1y agoIMHO what just referring to uncountability misses is that not only most functions are unexpressable, many __useful ones__ are not. Most ℝ→ℝ functions (and even most real numbers) are so unremarkable there is no way to uniquely name them. The fact that some useful functions are undecidable is quite a bit less trivial than "there are more functions than there are programs to evaluate them".
- SkyBelow 1y agoIsn't this related to why the busy beaver is the fastest growing program, given that at some N states it would be able to emulate any closed form function and then at some greater number N + M states be able to use that function in more complex functions (as a lower bounds, the actual busy beaver of N + M states given size would likely be an even larger output than the same sized Turing machine emulating whichever fast growing function is used for comparison)?