What Assumptions are Needed to Prove there is a self-outputting program (s-m-n?)
Charlie-Boo
What assumptions (axioms, informal theorems) are needed concerning
Computability to prove that there is a program (regardless of the
programming language) that outputs only a copy of itself?
I ask because in my own formalism all I need is s-m-n and if published
proofs or conclusions say that you start with only s-m-n, it would be
a good example of a published informal proof (not just the theorem)
being very precisely formalized.
(There are other principles used that are true of much larger
supersets of Computability such as the ability to substitute for an
input to a function in general, which I could codify.)
C-B
Mary Beth
> What assumptions (axioms, informal theorems) are needed concerning
> Computability to prove that there is a program (regardless of the
> programming language) that outputs only a copy of itself?
>
> I ask because in my own formalism all I need is s-m-n and if published
> proofs or conclusions say that you start with only s-m-n, it would be
> a good example of a published informal proof (not just the theorem)
> being very precisely formalized.
What is s minus m minus n?
Marshall
Jesse F. Hughes
It's pronounce "ess-em-en" as in the "s-m-n theorem".
http://en.wikipedia.org/wiki/S-m-n_theorem
(Maybe you were just funnin' but maybe not.)
--
"That's all the legacy I ever wanted, to have people remember me like
a shooting star streaking across their Life sky, illuminating, for
just one moment, unparalleled beauty unique to itself."
-- Weblogs are a particularly humble medium, unique to themselves.
Marshall
> Mary Beth <mbg...@gmail.com> writes:
> > On Nov 8, 4:14 am, Charlie-Boo <shymath...@gmail.com> wrote:
> >> What assumptions (axioms, informal theorems) are needed concerning
> >> Computability to prove that there is a program (regardless of the
> >> programming language) that outputs only a copy of itself?
>
> >> I ask because in my own formalism all I need is s-m-n and if published
> >> proofs or conclusions say that you start with only s-m-n, it would be
> >> a good example of a published informal proof (not just the theorem)
> >> being very precisely formalized.
>
> > What is s minus m minus n?
>
> It's pronounce "ess-em-en" as in the "s-m-n theorem".
>
> http://en.wikipedia.org/wiki/S-m-n_theorem
>
> (Maybe you were just funnin' but maybe not.)
I was just funnin', but I was also unaware that the
term wasn't one Charlie had just made up.
So ... I read that wiki page 3 or 4 times. Is it just
saying that we can bind free variables without
binding all of them? I'm unclear why we would
need a theorem for that.
Marshall
Jesse F. Hughes
It's not quite about binding variables, but rather about Currying
them. Of course, we know that for each function f:N x N -> N, there
is a function g:N -> (N -> N), defined by
g(x)(y) = f(x,y)
but the s-m-n theorem tells us something more. Namely, the function
s(f, x) = g(x): N -> N
is primitive recursive.
Well, I'm being sloppy here, since primitive recursive functions have
domain N^k and codomain N, and I wrote down a function with
s:(N^2 -> N) x N -> (N -> N).
So, we simply use the Goedel number #(f) of f in the definition of the
function s. Similarly, the output will be a Goedel number of a
function doing the right thing. So,
s: N x N -> N
where s(#(f),x) is the Goedel number of a function N -> N such that
phi_s(#(f),x)(y) = f(x,y).
The whole point is that there is a *primitive recursive* function s
satisfying this condition.
--
Jesse F. Hughes
"And I will dream that I live underground and people will say, 'How
did you get there?'
"'I just live there,' I will tell them." -- Quincy P. Hughes, Age 4
Charlie-Boo
And from that can you prove that there is a program that outputs
itself e.g. a Turing Machine that accepts only a representation of
itself?
What in general do you need to prove it? How would you prove it?
C-B
Jesse F. Hughes
It's been a very long time since I did any recursion theory, so I
don't recall the details easily. Have you tried looking at a
textbook? Surely you could find the answer there.
--
"Reality is that I've worked all over the United States in so many
different jobs that I jokingly call myself The Pretender. I've been a
bartender, worked at Equifax, sold new cars for Honda, and that's from
about six months of my life." -- James S. Harris: a great Pretender.