4 ms·
Yes, you can have fanciful "models of computation" with oracles of various kinds. Few people really think of that as computation. But I agree that there are r
by btilly 3y ago
Yes, you can have fanciful "models of computation" with oracles of various kinds.
Few people really think of that as computation.
But I agree that there are real examples of physically possible computation which are not deterministic. The most widely used being true random number generators. And so theoretical computability is not necessarily the right model for the real world.
- tsimionescu 3y agoNote that analyzing the complexity of problems in relation to various oracles is probably half of computer science. Algorithms like those in NP are not exotic concepts, they are the bread and butter of many computer science courses and careers. Hyper-computation is much more exotic, though, I'll give you that.
- mjburgess 3y agoRandom number generation, if physically non-deterministic, isnt computation. https://en.wikipedia.org/wiki/Computable_function https://en.wikipedia.org/wiki/Computable_function