Is it theoretically possible to specify a programming language for which no implementation could exist? A programming language is a way of defining functions. An implementation means a method to execute a given program in that language on a given input to the output of the function corresponding to the program on that input.

What is are the minimal requirements of such a language?

  • 3
    $\begingroup$ What is an "implementation" of a language? $\endgroup$ – Raphael Jun 12 '12 at 22:00
  • $\begingroup$ @Raphael: It is you who changed “programming lang” to “language.” Before your edit, it was clear what an implementation of a language meant. $\endgroup$ – Tsuyoshi Ito Jun 13 '12 at 12:21
  • $\begingroup$ @TsuyoshiIto: Not quite; I only adapted the title to match the question, which was changed on cstheory.SE. I changed it back, but it is still not clear what that means. A compiler? An interpreter? Anyways, migrating a question here that is almost a year old and by a user who apparently never revisited the question there was ill-advised at best. $\endgroup$ – Raphael Jun 13 '12 at 20:04
  • $\begingroup$ @Raphael: Asking “what is an implementation of a language?” after removing all the clues was simply beyond my understanding. But I agree that the question was unclear from the beginning. $\endgroup$ – Tsuyoshi Ito Jun 13 '12 at 23:23
  • $\begingroup$ I think your putative definition of "programming language" is ill-conceived. It should at least be amended by replacing "functions" by "computable functions". Otherwise, it is not clear why you would choose to call the language a "Programming language". Once you amend it, the question becomes meaningless, because there are no such "programming languages for which no implementation could exist". $\endgroup$ – Uday Reddy Jun 19 '12 at 19:04

Usually, implementing a programming language is at least giving a interpreter in a language (or a compiler to a language) that is no more than Turing-complete.

Using this "definition" we can specify a programming language like this:

  • there only one possible program that is HALT;

  • specification of HALT: it is a function that solve the halting problem.

Implementing this programming language requires solving the halting problem with the implementation. (Which is impossible since our implementation should not be more powerful than a Turing machine).

Specification handles logic and thus can ask for a lot more. Another specification that will be impossible to implement is "false". (Or any contradictory sentence in the specification) But this does not feels like a specification, which is why I used the halting problem example.

| cite | improve this answer | |
  • 1
    $\begingroup$ Generalized: Any language which specifies a function which solves an undecidable problem cannot be implemented. $\endgroup$ – edA-qa mort-ora-y Jun 14 '12 at 3:52
  • $\begingroup$ @edA-qamort-ora-y Technically it could be implemented. You can't decide the Halting Problem, but a TM can simulate another machine and accept if that machine halts; the language accepted by such a TM is exactly the language of (encodings of) machines that halt. But for practical purposes we normally like the primitive operations of programming languages to be guaranteed to terminate! (at least on "sensible" input) $\endgroup$ – Ben Jun 14 '12 at 5:12
  • 1
    $\begingroup$ Yes, functions of a language should have a time complexity less than $O(∞)$ :) $\endgroup$ – edA-qa mort-ora-y Jun 14 '12 at 5:54
  • $\begingroup$ @edA-qamort-ora-y this is not always true. For example, in Haskell's denotational semantics 1/0 $\equiv$ let loop = loop in loop and thus is $\Omega(\infty)$ in the obvious cost model. In practice, all Haskell implementations differentiate between exception and divergence, and GHC has a specified operation semantics that explains how exceptions are supposed to work. But, it would be possible to have a conforming implementation that looped forever on divide by zero! $\endgroup$ – Philip JF Feb 5 '13 at 23:47

Just a curious side note: the C++ template engine is Turing-complete

Theorem 1: In the absence of instantiation bounds, C++ templates are Turing-complete.

Corollary 1: In the absence of instantiation limits, whether a C++ compiler will halt when compiling a given program is undecidable.

... so the C++ itself can be considered a programming language for which no "implementation" could exist ... :-D

| cite | improve this answer | |
  • $\begingroup$ So could a C "compiler" be used as an interpreter if one didn't care about the code that was generated but simply the diagnostics produced? $\endgroup$ – supercat Jan 30 '14 at 4:40
  • $\begingroup$ Yes, as shown in the paper, the compiler halts with a list of errors that match the computation history of the Turing machine (and its final tape configuration). Obviously the input cannot be interactive (it must be encoded in the source code before running the compiler). $\endgroup$ – Vor Jan 30 '14 at 7:42

It is unclear what you mean by a "programming language" and "an implementation of a language". You need to provide rigorous definitions of these two to get an answer.

A "programming" language for computing a (partial) functions over strings can be considered a mapping from $\Sigma^*$ to $2^{\Sigma^*}$. As long as one of the uncomputable functions is in the range the language cannot be implemented.

For example, one can take first-order arithmetic. Then it is easy to define functions that are not computable, e.g. the function that given a TM $M$, decide if $M$ returns $0$ on all inputs. This can be easily expressed by a first order formula in the language of arithmetic. On the other hand it is an easy result in computability theory that it is not a computable function, so there can be no implementation of the function.

But this is not the kind of specification language that people mean when they use the phrase "programming language". A programming language is typically meant to be a language to express computable functions (processes,...) and to communicate the instructions to a machine and therefore there is a TM that can simulate those its programs and output their results. So in a sense having a programming language which cannot be implemented is not meaningful.

(My guess is that you are probably confusing programming languages either with specification languages or with formal languages. In any case, we can define languages that are not computable.)

| cite | improve this answer | |
  • $\begingroup$ I'm pretty sure "programming language" means a programming language the way we would normally talk about it, and "an implementation of a language" means an environment for executing programs in that language on real computers. The question is not formalised, but surely it's not unclear? I can easily write a spec for a new programming language without bothering to implement it; the question is simply asking whether it's possible to do so in such a way that the language cannot be implemented. $\endgroup$ – Ben Jun 15 '12 at 0:05
  • $\begingroup$ @Ben, if you look at the original question on cstheory you will see there is no word programming in the question only in the title. The question as posted by OP is definitely clear. ps: I would be interested in a rigorous (doesn't need to be formal) definition of what is a programming language. We cannot prove negative results about programming languages solely based on intuition and examples. If you have reference for a definition you please post it as an edit or comment to the question. $\endgroup$ – Kaveh Jun 15 '12 at 0:41
  • $\begingroup$ Fair enough, although SE claims you answered it 9 hours ago, long after it was migrated and edited. I still would make the same interpretation based on the original question anyway. As far as a definition of a programming language, I'd say an obvious-ish one is a formal grammar plus either a reduction to some other well understood computational model (lambda calculus, turing machine, etc), or a rigorous operational semantics. The reduction model would make the answer to this question a trivial "no", obviously. $\endgroup$ – Ben Jun 15 '12 at 1:40

There have been plenty of languages specified without an implementation, e.g. Algol 60 was supposed to be a language for writing up algorithms, not to be implemented. Some of the many "just for fun" languages were specified long before an implementation came along, Intercal comes to mind.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy