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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Related: cs.stackexchange.com/q/115229/755 $\endgroup$
    – D.W. ♦
    Jul 13, 2022 at 19:08
  • 5
    $\begingroup$ The "blah blah blah" is quite off-putting. $\endgroup$
    – Andrej Bauer
    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
    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 ♦
    Jul 14, 2022 at 10:32

3 Answers 3

Reset to default
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.

Improve this answer
$\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

Improve this answer
$\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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ The real issue is not finiteness (no physical computer is infinite). The issue is the computing model. $\endgroup$
    – user16034
    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
    Aug 15, 2022 at 8:09

Your Answer

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

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