It's a harsh, but true reality that with only have finite quantities of time and space, especially in real world computation. The assumption of finite resources is also a harsh, but true reality.
There are many things that fundamentally defy any form of computation. Things which cannot create mathematical formulae to represent, nor create algorithms for.
For a major example, we cannot translate the mental activities of conscious, aware living beings into any sort of computable form, as these activities are not algorithmic in nature. They aren't random, nor deterministic ~ rather, they are indeterministic, following no rigid patterns.
Even the most complex, complicated computer program follows an algorithm, which is ultimately deterministic. Even if you throw in some random inputs at some parts, the algorithm still acts deterministically. Perhaps the only really indeterministic part in an algorithm's behaviour might be hardware level bugs and errata which interfere with the otherwise very predictable algorithm.
> For a major example, we cannot translate the mental activities of conscious, aware living beings into any sort of computable form, as these activities are not algorithmic in nature. They aren't random, nor deterministic ~ rather, they are indeterministic, following no rigid patterns.
How could you possibly know that? Following no known patterns, maybe.
Trivially, for any finite string (in a finite alphabet), there is a finite program (Turing machine, whatever) which outputs that string given empty input. Hence, "the mental activities of conscious, aware living beings" are trivially computable if there exists a finite string which describes them with perfect accuracy.
Furthermore, there obviously are some computable patterns in those activities, so the shortest possible computable program to generate that description will actually be shorter than the length of the description itself.
One could respond that a string describing those mental activities, no matter how accurately, is a different thing from the mental activities themselves. I think that is indeed the correct response, but it has nothing to do with any questions of computability.
(Another response would be to claim that those mental activities cannot be finitely described because they are actually infinite. Few however will want to claim that human minds are infinite.)
I guess you're right. But I was trying to defend Valmar's statement which I still think is basically right in this context. Computers can't really implement non-deterministic algorithms.
Well they can. Quantum computers are inherently non-deterministic.
Even for a classical computer, access to a true randomness source (such as a sufficiently good hardware RNG) is enough to make a classical computer non-deterministic, and hence programs that rely on that true randomness source are classified as non-deterministic.
In practice, we sometimes classify a program as nondeterministic even if it only has access to pseudorandomness, provided that pseudorandomness is "random enough". If a program uses a high quality PRNG seeded with the current time, that might be practically considered non-deterministic, even though strictly speaking the program's behaviour is a deterministic function of the current time (and other inputs).
Artificial neural networks can be either deterministic or non-deterministic.
Biological neural networks are non-deterministic.
(You can debate philosophically whether apparent non-determinism is actually fundamentally non-deterministic or ultimately reduces to some hidden determinism. It depends on one's choice of interpretation of quantum theory – many worlds and hidden variables both claim that reality is fundamentally deterministic, other interpretations do not. But, whether or not non-determinism ultimately exists, it certainly apparently exists, both in biological and technological systems.)
Yes I was asserting that algorithms are by definition deterministic. But I guess you can technically consider non-deterministic algorithms but those aren't really relevant here. Computers don't behave non-deterministically. Every program in your computer describes a deterministic process.
If a machine is deterministic, all programs for the machine must be deterministic. Gödel’s theorems don’t contradict that. If you think they do, you’ve misunderstood them.
There are many things that fundamentally defy any form of computation. Things which cannot create mathematical formulae to represent, nor create algorithms for.
For a major example, we cannot translate the mental activities of conscious, aware living beings into any sort of computable form, as these activities are not algorithmic in nature. They aren't random, nor deterministic ~ rather, they are indeterministic, following no rigid patterns.
Even the most complex, complicated computer program follows an algorithm, which is ultimately deterministic. Even if you throw in some random inputs at some parts, the algorithm still acts deterministically. Perhaps the only really indeterministic part in an algorithm's behaviour might be hardware level bugs and errata which interfere with the otherwise very predictable algorithm.