8
$\begingroup$

Is there any language, which can be used to define all programming problems perfectly?

By perfectly, I mean with these two properties:

  • p is the problem.
  • d is the definition in the language.
  • P(d, p): "d is the definition of the problem p"

$$ \forall p\exists d(P(d, p)) $$ $$ \forall p\exists d1,d2((P(d1, p) \land P(d2, p)) \rightarrow (d1 \Leftrightarrow d2)) $$

Example: The simple problem to output the first N numbers, can be defined in many ways, for example in the english language. I want a language which restricts the number of definitions to 1 for every problem. In other words, no 2 distinct definitions can define the same problem, and every problem has a definition.


1. This language exists?

2. If such language does not exists, is it possible to create one?

$\endgroup$
  • 1
    $\begingroup$ Unlikely. Intuitively, some form of the s-m-n property should carry over from descriptions of the programs to descriptions of the problems; we'd have infinitely many descriptions just like we have infinitely many programs for each (computable) problem. In fact, each programming language is such a description, so the proof probably carries over directly. $\endgroup$ – Raphael Nov 5 '19 at 20:17
  • 4
    $\begingroup$ FWIW, I don't think those formulae add a lot of value here. $\endgroup$ – Raphael Nov 5 '19 at 20:18
  • 3
    $\begingroup$ Question 2 seems to be self-contradictory. $\endgroup$ – Raphael Nov 5 '19 at 20:18
  • $\begingroup$ I agree that programming languages and/or assembly are basically this very description you speak of. The thing to understand here is that there are effectively an infinite number of ways to solve a problem, let alone to even attempt to solve it. Some of those ways are just better than others. So no you can't have 1 definition for every problem, because you can't even have N definitions. $\endgroup$ – Andrew Nov 6 '19 at 16:56
16
$\begingroup$

This question is somewhat unclear to me; however, under one interpretation there is a result which indicates that the answer is unsatisfyingly yes: namely, the existence of Friedberg numberings. Roughly speaking, a Friedberg numbering is a programming language which is Turing complete but in which no two programs perform the same task.

(More formally: a Friedberg numbering is a computable function $\varphi$ of two variables such that for each computable function $\psi$ of one variable there is exactly one $e_\psi^\varphi$ such that $\lambda x.\varphi(e_\psi^\varphi,x)\cong\lambda x.\psi(x)$.)

A simple proof of the existence of such numberings was given by Kummer.

That said, it's easy to show that we can never "translate into" a Friedberg numbering, which renders the positive result above somewhat misleading at best: if $(\theta_i)_{i\in\mathbb{N}}$ is the usual numbering of computable functions of one variable and $\varphi$ is a Friedberg numbering, the map $$(*)_\varphi:\theta_i\mapsto e_{\theta_i}^\varphi$$ is not computable. Essentially, what this means is that programming in the usual sense is impossible in the context of a Friedberg numbering: while every computable function has a corresponding program, there's no way to find it.

  • To prove this, simply note that from the map $(*)_\varphi$ we can compute the set of indices for the never-defined function: let $c$ be the unique number such that $\lambda x.\varphi(c,x)$ is never defined, and to tell whether $\theta_i$ is never defined just check whether $(*)_\varphi(i)=c$. (Note that this can be improved: if we replace the never-defined function with the identity function, or more generally any partial computable function with infinite domain, the resulting set of indices is strictly more complicated than the halting problem - it has Turing degree $\bf 0''$. So in fact "translating into a Friedberg numbering" is really very impossible indeed.)

This "impossibility of translation" is what breaks the "obvious" proof that Friedberg numberings are impossible. It also points the way to the general study of numberings, which is a fruitful area of study within computability theory. The numberings which are Turing complete in a "non-stupid" way are the acceptable numberings, which are also those which are maximal in a certain natural pre-ordering on numberings.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

No, such a language cannot exist.

Programming can solve many different kinds of problems.

One particular kind of problem it can solve is computing a function from input values to output values. The program will read an input value and produce the output value defined for that input value by that function. For this type of problem, the problem definition is given by some sort of specification of the input-output function.

I think you will agree that we don't want to restrict ourselves to problems that only accept finitely many different input values. For instance, we want to be able to define the problem that takes an arbitrary integer and outputs its value squared. We can only do that if we allow any integer to be an input value.

Furthermore, we don't want to restrict ourselves in the kind of input-output function we can define.

A pretty fundamental result in computability theory says that for any language capable of describing all such functions, it is undecidable whether two descriptions of functions in that language describe the same function. Which directly answers your question.

What is more, it is undecidable even for heavily restricted classes of input-output functions. Consider, for instance, the set of functions with the following properties:

  • All input values are strings from some given alphabet of at least two characters; for instance, strings built out of the characters a and b.
  • All output values are either yes or no.
  • The set of input values for which the output value is yes is always a context-free language.

No matter which language you design for describing these functions, deciding whether two descriptions describe the same function is undecidable, as equivalence of context-free languages is undecidable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "A pretty fundamental result in computability theory says that for any language capable of describing all such functions, it is undecidable whether two descriptions of functions in that language describe the same function. Which directly answers your question." That's false, per my answer; it only applies to "acceptable" situations. Now also per my answer, all counterexamples are deeply weird, but they do exist. $\endgroup$ – Noah Schweber Nov 5 '19 at 14:26
  • 2
    $\begingroup$ I think a description that can't effectively be used isn't a description at all. $\endgroup$ – reinierpost Nov 5 '19 at 14:32
  • $\begingroup$ Well, it can be effectively used, it just can't be translated into. That is, each description in a "Friedberg language" can in fact be carried out (the whole shebang is computable) but there's no way to identify which description in the language performs a given task in general. It's a weird one-way-ness which does in fact exist, and this is a situation where a "morally true" statement is technically false. $\endgroup$ – Noah Schweber Nov 5 '19 at 14:36
  • 1
    $\begingroup$ Yes, but you don't know how to describe anything you want to describe (e.g. squaring a number), so Friedberg numbers don't actually describe anything, they just point at something. (In logical terms: they are purely extensional, not intensional.) That said, I've upvoted your answer, as it's certainly a valid perspective and I didn't know Friedberg numberings existed. $\endgroup$ – reinierpost Nov 6 '19 at 9:20
  • $\begingroup$ "I think a description that can't effectively be used isn't a description at all." Yeah tell that to anyone whose ever defined things according to a standard though... $\endgroup$ – Andrew Nov 6 '19 at 16:51

Your Answer

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

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