Prev: sci.lang is not meant for advertisement
Next: The Electron’s puzzles.
From: Aatu Koskensilta on 9 Jun 2010 02:59
apoorv <sudhir_sh(a)hotmail.com> writes:

> That is, there is no way of identifying the code of the godel formula
> in finite time. Is that a correct inference?

No. You are thoroughly confused.

--
Aatu Koskensilta (aatu.koskensilta(a)uta.fi)

"Wovon man nicht sprechan kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: apoorv on 9 Jun 2010 03:46
On Jun 9, 11:59 am, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote:
> apoorv <sudhir...(a)hotmail.com> writes:
> > That is, there is no way of identifying the code of the godel formula
> > in finite time. Is that a correct inference?
>
> No.You are thoroughly confused.

I agree with the second part. But would you give some reason for your
'cryptic' no or it is reasoning by authority?
-apoorv
From: Daryl McCullough on 9 Jun 2010 06:49
apoorv says...

>If PA is sound, then PA does not halt on p nor can it be detected to
>be in a loop at any finite instant of time.

I think you mean that

If PA is sound, then P does not halt on p nor can it be detected to
be in a loop at any finite instant of time.

where P is constructed so that P halts on p <-> PA proves
that P does not halt on p.

>( Because if we could so detect it to be in a loop, the sequence of
>configurations would constitute a proof in PA that P loops on p),.
>So, is it that P just goes on forever on input p without halting
>or looping?

Yes. The particular P works by going through every proof in PA,
one by one, and checking whether that proof happens to prove a
statement of the form "P does not halt on input p". There are
infinitely many different proofs to check, so P never halts,
but never loops.

>So, is it that 'loops' and 'does not halt' are not equivalent?

No, they are not equivalent. For a program to "loop" means that
it keeps doing the same thing over and over, without any possibility
of doing anything different. If a program loops, you can detect
it, by keeping track of the sequence of program states. But a
program can run forever without ever doing the same thing twice.
The program in question is running through all possible proofs in PA,
so it's not in a loop; it's not checking the *same* proof over and
over.

>Suppose, again assuming PA to be sound, we want to test some number q
>for whether it is the code of the (self referential) machine P. We
>decode q to get Q and run Q on q.

You can't check whether two programs are equal by running them.
Either you look at the source code and check syntactically that
they are the same, or else you try to prove that they compute
the same function.

>If Q halts or loops in a finite time on q, we conclude that q is
>not the required code. We would know that q is the required code
>only after 'Q has run forever without halting or looping'.

That doesn't prove that q is the code for program P. The fact that
Q fails to halt on input q, and P fails to halt on input p does
not mean that P and Q are the same program.

>That is, there is no way of identifying the code of the godel formula
>in finite time. Is that a correct inference?

No, it's not. Whether an input is a code for a Godel formula is
decided by looking at the formula, and seeing if it has the form
of a Godel sentence.

--
Daryl McCullough
Ithaca, NY

From: Frederick Williams on 9 Jun 2010 08:19
apoorv wrote:
>
> On Jun 9, 11:59 am, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote:
> > apoorv <sudhir...(a)hotmail.com> writes:
> > > That is, there is no way of identifying the code of the godel formula
> > > in finite time. Is that a correct inference?
> >
> > No.You are thoroughly confused.
>
> I agree with the second part. But would you give some reason for your
> 'cryptic' no or it is reasoning by authority?
> -apoorv

There is a systematic way of identifying the G\"odel code of every
formula in the formal language. There has to be. Recursive functions
are numerical functions so if a manipulation of symbols is to be deemed
recursive then it must be via a systematic numbering.

So it seems to me anyway. Of course one could define recursive
functions of symbols and strings of symbols but if *that* notion of
recursion was to be proved equivalent to the numerical notion then some
way of translating between symbols and numbers must be given, i.e.
G\"odel numbering, and that translation must be effective.

--
I can't go on, I'll go on.
From: apoorv on 11 Jun 2010 06:49
On Jun 9, 3:49 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote:
> apoorv says...
>
> >If PA is sound, then PA does not halt on p nor can it be detected to
> >be in a loop at any finite instant of time.
>
> I think you mean that
>
> If PA is sound, then P does not halt on p nor can it be detected to
> be in a loop at any finite instant of time.
>
> where P is constructed so that P halts on p <-> PA proves
> that P does not halt on p.
>
> >( Because if we could so detect it to be in a loop, the sequence of
> >configurations would constitute a proof in PA that P loops on p),.
> >So, is it that P just goes on forever on input p without halting
> >or looping?
>
> Yes. The particular P works by going through every proof in PA,
> one by one, and checking whether that proof happens to prove a
> statement of the form "P does not halt on input p". There are
> infinitely many different proofs to check, so P never halts,
> but never loops.
>
> >So, is it that 'loops' and 'does not halt' are not equivalent?
>
> No, they are not equivalent. For a program to "loop" means that
> it keeps doing the same thing over and over, without any possibility
> of doing anything different. If a program loops, you can detect
> it, by keeping track of the sequence of program states. But a
> program can run forever without ever doing the same thing twice.
> The program in question is running through all possible proofs in PA,
> so it's not in a loop; it's not checking the *same* proof over and
> over.
>
> >Suppose, again assuming PA to be sound, we want to test some number q
> >for whether it is the code of the (self referential) machine P. We
> >decode q to get Q and run Q on q.
>
> You can't check whether two programs are equal by running them.
> Either you look at the source code and check syntactically that
> they are the same, or else you try to prove that they compute
> the same function.
>
> >If Q halts or loops in a finite time on q, we conclude that q is
> >not the required code. We would know that q is the required code
> >only after 'Q has run forever without halting or looping'.
>
> That doesn't prove that q is the code for program P. The fact that
> Q fails to halt on input q, and P fails to halt on input p does
> not mean that P and Q are the same program.
>
> >That is, there is no way of identifying the code of the godel formula
> >in finite time. Is that a correct inference?
>
> No, it's not. Whether an input is a code for a Godel formula is
> decided by looking at the formula, and seeing if it has the form
> of a Godel sentence.
I want to go back to the formula
sub(x,x,y) <-> y is the code of the formula resulting by substituting
x for the free variable in the formula whose code is x.
Let its code be p.Then
sub(p,p,y) <-> y is the code of the formula resulting by substituting
p for the free variable in the formula whose code is p.
or,
sub(p,p,y) <-> y =code of sub(p,p,y)
if we use the ascii coding used by you, then for any y, say 1234, the
ascii code for
sub(p,p,y) is a number that contains 1234 as a substring.So,
code of sub(p,p,1234) is greater than 1234. So, is it that In
general ,code of sub(p,p,y) is greater than y and equality never
holds?

Also, in the second approach, we do not have an explicit description
(states, transition function) of the machine P with code p such that,
P does not halt on p iff PA does not prove P does not halt on p.

So,if we are to find this machine, it could be done only by testing
all machines
in some order to see whether it meets the above definition.Now if X
halts or loops in a finite time on its code x, then we reject X. Only
those machines are possible candidates for P which 'run forever'
without looping . Such candidates could be known only 'after
forever'.So,is it that :
if a number n is not the code of P,then we can prove that it is not
the code of P;
but, if a number m is indeed the code of P, then we cannot prove that
it is indeed the code of P?

First  |  Prev  | 
Pages: 1 2 3 4 5 6 7
Prev: sci.lang is not meant for advertisement
Next: The Electron’s puzzles.