13

What are the critera or the basic features required to tell that X or Y is (or is not) a programming language?

I've done some reading (Is HTML considered a programming language?, Turing complete, and others), and came to the conclusion that a language or a syntax has to be Turing complete to be considered a programming language. Is this correct? Is it enough?

And how do I determine if something is Turing complete? Are there any specific criteria?

Is having control-of-flow structures (conditional statements and loops) enough to be considered Turing complete?

Community
  • 1
  • 1
Jérôme
  • 26,567
  • 29
  • 98
  • 120

4 Answers4

7

There exist programming languages which are not Turing complete. For some examples of non-Turing complete languages, take a look at: Practical non-Turing-complete languages?

An advantage of having a language that is non-Turing complete could for instance be that it might be sufficient to perform the tasks you need, while being simple enough to allow you to prove properties about your programs, which you could not otherwise prove. This could, for instance, be useful in cases where it's vital to know that the program will run without error.

What exactly constitutes a programming language is a bit vague, but one could say that it's a language in which you can express computations. If we look at HTML, you cannot create a document that computes anything; it merely tells the browser how the page is supposed to look. The important part to note is, it doesn't compute anything new.

It is, as Marcelo says, quite fuzzy.

As for determining if a language is Turing complete, I will refer you to this question: What are practical guidelines for evaluating a language's "Turing Completeness"?

Community
  • 1
  • 1
Sebastian Paaske Tørholm
  • 49,493
  • 11
  • 100
  • 118
  • 1
    A functional program doesn't compute anything; it tells what the result should be. The same goes for logic programming languages like Prolog. From a language theory perspective, the only requirement for a programming language is that there exists an unambiguous grammar for it, so there's a single syntactic structure for any valid sequence. The meaning of said structure is up to the interpreter or translator; a pretty printer, a metrics analyzer, and a compiler, give different meanings to the same _program_ (a pretty printer doesn't care about mismatched types and operations, f.i.). – Apalala Feb 01 '11 at 15:03
  • The TCP protocol is a programming language. – Apalala Feb 01 '11 at 15:06
3

What are the critera or the basic features required to tell that X or Y is (or is not) a programming language ?

As Marcelo Cantos already told it is somewhat fuzzy, especially since there are Domain specific languages (DSLs; http://en.wikipedia.org/wiki/Domain-specific_language) that are not Turing complete, but also often considered programming languages.

And how do I determine if something is Turing complete ? Are there any specific criteria ?

One way determine whether a programming language is Turing complete is to write a Turing machine in it (or an implementation of the Lambda calculus).

Another way is to prove that all mu-recursive functions http://en.wikipedia.org/wiki/%CE%9C-recursive_function can be computed by the programming language.

Since it can be proved that an imperative programming language is Turing complete, if there is a variable assignment, a way to represent number 0, a successor function, a predecessor function and a possibility to represent while-loops this is another way.

A sometimes-used way (that for obvious reasons does not always work) to prove that a programming language is not Turing-complete is to check whether all programs terminate; if yes, it can't be.

Nubok
  • 3,502
  • 7
  • 27
  • 47
1

So let's think about the consequences of these concrete definitions:

A Turing-complete language is a programming language: CSS becomes a programming language.

A programming language must be turing-complete: maybe, but programs can be written otherwise.

Now a far better definition: A programming language is one that can be used to write programs.

Community
  • 1
  • 1
Camilo Martin
  • 37,236
  • 20
  • 111
  • 154
0

The term "programming language" is somewhat fuzzy. Do regular expressions constitute a programming language? Most programmers would say yes, even though regexes are not turing complete.

As for Turing-completeness, I'm no expert, but I think it is sufficient to have a conditional branch and an infinite stack (therefore real machine only approximate turing-completeness).

EDIT: After a bit of research, I've found that this is isn't sufficient. You need at least two stacks and some minimal number of states (and a state transition table).

Perhaps a more down-to-earth yardstick is that if can remember arbitrary amounts of state and do loops, it's probably turing complete.

Marcelo Cantos
  • 181,030
  • 38
  • 327
  • 365