3 ms·

> Section 2.3 Turing Completeness and expressiveness: The primary requirement for a TC language is the capacity to describe unbounded computations over unbounde

by c3poa 6y ago

> Section 2.3 Turing Completeness and expressiveness: The primary requirement for a TC language is the capacity to describe unbounded computations over unbounded values. This encompasses a very wide spectrum of programming languages, if seemingly novel aspects are regarded as state changes, for example HTML manipulating WWW pages, and SQL manipulating databases. >Contrariwise, a non-TC language can only describe bounded computations, for example regular expressions, or manipulate bounded values, for example FORTRAN IV which, without files, has bounded numbers and arrays. Arbitrary instances of an arbitrary non-TC language will be translatable into an arbitrary TC language but not vice versa. Can someone elaborate? How do we have unbounded computations and unbounded values?

qsort 6y ago
In math and computer science, unbounded doesn't mean infinite. Unbounded simply means that there is no a-priori fixed limitation to the amount of space and time that a valid, non-diverging program could take. Unbounded space and time is (as the article correctly points out) a hard requirement for a computational model to be Turing-complete, in the sense that there exist computable functions that take arbitrarily high time and space to be computed; (see the time- and space-hierarchy theorems for details) any computational model with a space or time limitation would therefore be unable to compute such functions making it, by definition, not Turing-complete. For this reason, ordinary Turing-complete programming languages allow (at least in principle, i.e. assuming infinite RAM) valid, provably terminating programs with arbitrarily high, unbounded complexity, unlike other formalisms such as regular expressions, which do not allow the same level of generality.
- c3poa 6y ago
  First, thanks for the answer, really appreciate it! So in a more practical sense, for example in application programming, unbounded computations/values could be compared to users continually adding/retrieving data against application database - as long as the server is up, the process never stops?
  - qsort 6y ago
    The angle is slightly different. Let's put it this way. Imagine a function written in any Turing-complete programming language, Java, for example. Let's say that you can see the API but not the implementation. Can you bound the space or time that the function call will take? The answer is no, because there exist correctly written and terminating Java functions with arbitrarily high running time. You can write functions with running time O(n^100), O(2^n), O(n!), O(((n!)!)!)... there is no limit. The crucial observation is that this property is necessary for a language to be as powerful as Java, because there exist problems that require such a high running time and that couldn't be solved if the Java compiler enforced a hard limit on the running time or memory. (System resources such as physical RAM are obviously limited, we are thinking of an hypotetical computer with infinite RAM). The same isn't true for computational models that aren't Turing complete. For example, regular expression searches are guaranteed to terminate in a certain amount of time and using a certain amount of space (what exactly is this limit depends on the algorithm you're using to implement regexes, but there definitely is one). The 'tradeoff' at play here is that by using a less powerful tool, i.e. regexes instead of a Java program, you are gaining guarantees about the maximum running time and memory usage, but you are losing the ability to solve certain types of problems. A common example that can be solved by a Java program but not by any regular expression is determining whether a string of parentheses is correctly matched. The idea, of course, is not that either tool is 'better' or 'worse', but simply that Turing-complete programming languages can solve problems that non-Turing-complete languages can't, at the expense of being 'more dangerous', because you can't a-priori guarantee how much time they'll take to terminate (if at all!) or how much memory they'll require.
    - c3poa 6y ago
      Now I understand, thank you for clarification!

by c3poa 6y ago

qsort 6y ago

In math and computer science, unbounded doesn't mean infinite. Unbounded simply means that there is no a-priori fixed limitation to the amount of space and time that a valid, non-diverging program could take. Unbounded space and time is (as the article correctly points out) a hard requirement for a computational model to be Turing-complete, in the sense that there exist computable functions that take arbitrarily high time and space to be computed; (see the time- and space-hierarchy theorems for details) any computational model with a space or time limitation would therefore be unable to compute such functions making it, by definition, not Turing-complete. For this reason, ordinary Turing-complete programming languages allow (at least in principle, i.e. assuming infinite RAM) valid, provably terminating programs with arbitrarily high, unbounded complexity, unlike other formalisms such as regular expressions, which do not allow the same level of generality.

c3poa 6y ago
First, thanks for the answer, really appreciate it! So in a more practical sense, for example in application programming, unbounded computations/values could be compared to users continually adding/retrieving data against application database - as long as the server is up, the process never stops?
- qsort 6y ago
  The angle is slightly different. Let's put it this way. Imagine a function written in any Turing-complete programming language, Java, for example. Let's say that you can see the API but not the implementation. Can you bound the space or time that the function call will take? The answer is no, because there exist correctly written and terminating Java functions with arbitrarily high running time. You can write functions with running time O(n^100), O(2^n), O(n!), O(((n!)!)!)... there is no limit. The crucial observation is that this property is necessary for a language to be as powerful as Java, because there exist problems that require such a high running time and that couldn't be solved if the Java compiler enforced a hard limit on the running time or memory. (System resources such as physical RAM are obviously limited, we are thinking of an hypotetical computer with infinite RAM). The same isn't true for computational models that aren't Turing complete. For example, regular expression searches are guaranteed to terminate in a certain amount of time and using a certain amount of space (what exactly is this limit depends on the algorithm you're using to implement regexes, but there definitely is one). The 'tradeoff' at play here is that by using a less powerful tool, i.e. regexes instead of a Java program, you are gaining guarantees about the maximum running time and memory usage, but you are losing the ability to solve certain types of problems. A common example that can be solved by a Java program but not by any regular expression is determining whether a string of parentheses is correctly matched. The idea, of course, is not that either tool is 'better' or 'worse', but simply that Turing-complete programming languages can solve problems that non-Turing-complete languages can't, at the expense of being 'more dangerous', because you can't a-priori guarantee how much time they'll take to terminate (if at all!) or how much memory they'll require.
  - c3poa 6y ago
    Now I understand, thank you for clarification!