Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Programming Paradigms, Turing Completeness and Computational Thinking (2020)

programming-journal.org

Post reply on HN
Print view View original

21–26 of 26 posts

Re: Programming Paradigms, Turing Completeness and Computational Thinking (2020)

#21

Post by qsort »

c3poa wrote: post #20

> 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 boun…

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.

Re: Programming Paradigms, Turing Completeness and Computational Thinking (2020)

#22

Post by c3poa »

qsort wrote: post #21
c3poa wrote: post #20

> 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 boun…

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 hig…

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?

Re: Programming Paradigms, Turing Completeness and Computational Thinking (2020)

#23

Post by qsort »

c3poa wrote: post #22
qsort wrote: post #21

Earlier quoted context omitted.

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 hig…

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?

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.

Re: Programming Paradigms, Turing Completeness and Computational Thinking (2020)

#24

Post by c3poa »

qsort wrote: post #23
c3poa wrote: post #22

Earlier quoted context omitted.

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?

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 functio…

Now I understand, thank you for clarification!

Re: Programming Paradigms, Turing Completeness and Computational Thinking (2020)

#25

Post by igorkraw »

carapace wrote: post #18
igorkraw wrote: post #16

Earlier quoted context omitted.

I hope this doesn't offend you, but I am more confused by your answer than I was before. Could you point me to some papers/books available online (maybe on certain hubs of science) you'd consider "seminal"?

I'm really sorry about that. No offense taken. In re: Cybernetics in general I always recommend "Introduction to Cybernetics" by W. Ross Ashby. It's a whole book but I find it to be the most direct and concrete exposition of Cybernetics. http://pespmc1.vub.ac.be/ASHBBOOK.html http://pespmc1.vub.ac.be/books/IntroCyb.pdf In re: paradigm shift, I don't really know of a single good source for that, but the works of Grego…

Thank you, I'll take a look:-)

Re: Programming Paradigms, Turing Completeness and Computational Thinking (2020)

#26

Post by carapace »

igorkraw wrote: post #25
carapace wrote: post #18

Earlier quoted context omitted.

I'm really sorry about that. No offense taken. In re: Cybernetics in general I always recommend "Introduction to Cybernetics" by W. Ross Ashby. It's a whole book but I find it to be the most direct and concrete exposition of Cybernetics. http://pespmc1.vub.ac.be/ASHBBOOK.html http://pespmc1.vub.ac.be/books/IntroCyb.pdf In re: paradigm shift, I don't really know of a single good source for that, but the works of Grego…

Thank you, I'll take a look:-)

Cheers, well met. :-)
Post reply on HN