Please correct me if at any time my definitions are wrong. Suppose we have a programming language $L$ over some set $D$ with semantic (partial) n-ary functions $\varphi^n:D \to (D^n \to D)$. Assume $L \subseteq D$ (so programs are data as well).

  • We say that $L$ is turing complete if a function $f:D^n\to D$ is Turing Computable if and only if there exists a program $p \in L$ such that $f = \varphi^n(p)$.
  • We know there exists a universal Turing Machine: A Turing Computable function $U:D^2 \to D$ such that for every (encoding of) a Turing Computable function $T$, every $d \in D$: $U(T,d) = T(d)$.
  • Does this imply, via Turing Completeness, that there must be a universal program in $L$? Why or why not?
  • 1
    $\begingroup$ What are your thoughts? What have you tried so far? Have you tried looking for a counterexample? for a proof? (It's also hard to tell what you mean by the notation $\varphi$, $\varphi^n$, and $\varphi_T$: are they supposed to be related in some way? You should specify how.) $\endgroup$ – D.W. Apr 22 '16 at 15:50
  • $\begingroup$ @D.W. I would say yes, since $U$ is Turing Computable then it should be $L$-computable as well. I fixed the notation, it should be more clear now. The part about encodings and such confuses me, so I do not know really where to start looking for a proof/counter example. $\endgroup$ – Santiago Cerón Uribe Apr 22 '16 at 15:57

Your Answer

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

Browse other questions tagged or ask your own question.