3 ms·
> Thus he identified fundamental limits of algorithmic theorem proving, computing, and any type of computation-based AI Fundamental limits presuming one has ar
by skissane 5y ago
> Thus he identified fundamental limits of algorithmic theorem proving, computing, and any type of computation-based AI
Fundamental limits presuming one has arbitrarily high (but finite) quantities of time and space with which the computations can be performed. Given in real world computation we will never have either, the fundamental limits of real-world computation are a lot less (even infinitely less) than those given by Gödel's work.
Also, demonstrations of the theoretical limits of computation (Gödel, Turing, etc) often make the assumption that we only have finite (even if arbitrarily large) resources, and that true contradictions (dialetheias) are disallowed. If we give up either (or both) of those of two assumptions, we can compute beyond those limits. It may be objected that computations beyond those limits are not physically realisable; but, almost all computations within those limits are not physically realisable either, so how much significance does that objection actually have?
- Valmar 5y agoIt'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.
- amanaplanacanal 5y ago> 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.
- skissane 5y agoTrivially, 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.)
- onethought 5y ago> Even the most complex, complicated computer program follows an algorithm, which is ultimately deterministic. Gödel's work proved this statement false. To give an example, what if the algorithm is to generate the correct algorithm? What if the correct algorithm ends up being the original algorithm? That is not deterministic.
- deleted 5y ago[deleted]
- skissane 5y agoIf 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.
- Rioghasarig 5y ago>> To give an example, what if the algorithm is to generate the correct algorithm? That's not a description of an algorithm. You've stated a "problem". An algorithm, by definition, is an actual deterministic procedure.
- skissane 5y ago> That's not a description of an algorithm. You've stated a "problem". I wanted to say the same thing, but you managed to find the words I couldn't. > An algorithm, by definition, is an actual deterministic procedure That's not necessarily true. There are non-deterministic algorithms: https://en.wikipedia.org/wiki/Nondeterministic_algorithm https://en.wikipedia.org/wiki/Nondeterministic_algorithm
- Rioghasarig 5y agoI 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.
- skissane 5y agoI don't care about being downvoted, but I wish those doing so would reply to explain why.
- mlasson 5y ago> almost all computations within those limits are not physically realisable either, so how much significance does that objection actually have? If some thing is impossible with arbitrarily large finite resources, it is still impossible with "practically large" finite resources ! That's why Turing / Gödel results really tell something fundamental about computing/proving; it tells everyone that they do not need to spend time solving an unsolvable problem on computers "as we know them". But if you prove that something is possible in a your own magic computing framework, it remains practically useless until you implement it in the real world (an example of such a situation is the framework of "quantum computer" trying to solve prime factorization).
- skissane 5y ago> That's why Turing / Gödel results really tell something fundamental about computing/proving; it tells everyone that they do not need to spend time solving an unsolvable problem on computers "as we know them" Consider something like Turing's proof that the halting problem is undecidable – does that have practical relevance, even just in telling us that there is no point in trying to solve an unsolvable problem? That's the standard line but I doubt it. The thing is, the halting problem is practically irrelevant; what has practical relevance is the bounded halting problem. Practically, you don't care about the difference between a program that never halts, and a program that halts after a googolplex steps, but that distinction is essential to the halting problem as defined. And, the practically relevant, bounded halting problem, is in fact decidable. Now, it is still intractable, because it is EXPTIME-complete, and we also know (per the time hierarchy theorem) that EXPTIME-complete problems are not in P. So Turing's proof doesn't actually tell us anything much useful about whether the halting problem is solvable in practice, whereas the proof that the bounded halting problem is EXPTIME-complete does. Suppose (counterpossibly) that the bounded halting problem was in P instead of EXPTIME-complete; then the halting problem might actually be tractable in practice, even though Turing's proof of the unbounded halting problem's undecidability would still hold.
- oscardssmith 5y agoThe problem with this is that proving an algorithm is in P is also undecidable.