Re: Quineless Turing-complete languages
- From: "r.e.s." <r_e_s_01@xxxxxxxxxxxx>
- Date: Wed, 14 Nov 2007 15:56:40 -0800
Oops, sorry to reply to my own post, but I (r.e.s.) wrote ...
Here's a question relating to the non-existence of "quines"
in certain Turing-complete programming languages. Thanks
in advance to anyone caring to consider this ...
Suppose T_1, T_2, T_3, ... is an enumeration of all Turing
machines, and suppose P_1, P_2, P_3, ... is an enumeration
of all programs in a given Turing-complete programming
language L. (By "Turing complete" I mean that for every n
in N, there is an m in N such that T_n and P_m compute the
same partial function from N to N.) For all n in N, let
f_n be the partial function from N to N computed by P_n.
Question:
Which (if either) of the following *must* hold? ...
(1) (Computability of the universal partial function)
The "universal" partial function
u: N^2 --> N: for all m,n in N, u(m,n) = f_{m}(n)
is partial recursive.
(2) (s-m-n theorem)
There exists a total recursive function s: N^2 --> N and
primitive recursive pairing function <.,.>: N^2 --> N,
such that for all m,n,x in N, f_{s(<m,n>)}(x) = f_{m}(n,x).
-
If I'm not mistaken, (1) and (2) together are sufficient to
prove Kleene's fixed point theorem, which is sufficient to
guarantee the existence of quines in L. (By quine, I mean
a program P_n such that f_n(.) = n.) So, in a language
that's Turing-complete yet having no quines, what can be
said about the status of (1) and (2) for that language?
.... and I spotted the cause of my confusion just after
hitting "send". By my definitions of "Turing complete" and
"quine", no Turing-complete language can be "quineless".
My mistake was to confuse a "quine"-as-I-defined-it, with
the kind of "literal" quine that most people mean by the
word (i.e., not defined as a P_n such that f_n(.) = n, but
rather as a program that literally ouputs its own source
code -- the latter can be absent from a Turing-complete
language, but not the former, if I'm not mistaken.
--r.e.s.
.
- References:
- Quineless Turing-complete languages
- From: r.e.s.
- Quineless Turing-complete languages
- Prev by Date: Quineless Turing-complete languages
- Next by Date: Re: recognition algorithm for series-parallel graph
- Previous by thread: Quineless Turing-complete languages
- Index(es):
Relevant Pages
|
