0
$\begingroup$

Most programming languages are Turing complete (finite memory blah blah blah), and when we design languages this is a goal.

But is it really necessary? What algorithms do we typically use that require Turing completeness? And do most industry software actually require it?

Like what can't pushdown automata do?

$\endgroup$
4
  • $\begingroup$ Related: cs.stackexchange.com/q/115229/755 $\endgroup$
    – D.W.
    Commented Jul 13, 2022 at 19:08
  • 5
    $\begingroup$ The "blah blah blah" is quite off-putting. $\endgroup$ Commented Jul 13, 2022 at 19:33
  • $\begingroup$ Turing completeness mandates a kind of loop construct. You would not go very far without loops. $\endgroup$
    – user16034
    Commented Jul 14, 2022 at 8:57
  • 4
    $\begingroup$ Worth reading is David Turner's paper on Total Functional Programming. It suggests a model that is more powerful than primitive recursion but still guarantees either termination or cotermination. (Cotermination is the dual notion of termination for non-terminating programs like operating systems.) sblp2004.ic.uff.br/papers/turner.pdf $\endgroup$
    – Pseudonym
    Commented Jul 14, 2022 at 10:32

3 Answers 3

1
$\begingroup$

Say that a programming language is general-purpose if all computable tasks can be programmed in it. It is worthwhile having such langauges, for the same reason that it is worthwhile having a universal computing machine.

Every general-purpose programming language is Turing complete, because by design it can express the Universal Turing machine.

There are special-purpose programming languages that are not Turing-complete. Some examples include database query languages, programming languages in proof assistants, languages that allow only limited resources to be used, etc.

$\endgroup$
0
$\begingroup$

You could refer to the following video, as it discusses the questions that David Hilbert asked and resolved by Gödel and Turing. https://www.youtube.com/watch?v=HeQX2HjkcNo

$\endgroup$
-3
$\begingroup$

Turing complete means no size limits.

For the C language, it’s easy to define an implementation with language-based limits that are way beyond physical limits. So you will never have an actual machine running into the limits. But the limits are there, so C is not Turing complete.

But if the limits are so high that building a machine that runs into the limits is physically impossible, at that point Turing complete or not makes no difference.

$\endgroup$
2
  • 3
    $\begingroup$ The real issue is not finiteness (no physical computer is infinite). The issue is the computing model. $\endgroup$
    – user16034
    Commented Jul 14, 2022 at 8:44
  • $\begingroup$ Yves, you are completely missing the point. The issue is not finiteness, the issue is that any of those machines has a limit of which finite tapes it can handle. And then read the actual question. It is answered. $\endgroup$
    – gnasher729
    Commented Aug 15, 2022 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.