patternModerate
Language to define perfectly a programming problem
Viewed 0 times
perfectlyproblemprogramminglanguagedefine
Problem
Is there any language, which can be used to define all programming problems perfectly?
By perfectly, I mean with these two properties:
$$
\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?
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?
Solution
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.
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.
(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.
Context
StackExchange Computer Science Q#116704, answer score: 19
Revisions (0)
No revisions yet.