Re: clarification on recursively enumerable (R.E.)
From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 11/08/04
- Next message: Will Twentyman: "Re: clarification on recursively enumerable (R.E.)"
- Previous message: Will Twentyman: "Re: Resolving the paradoxes of set theory"
- In reply to: shane: "clarification on recursively enumerable (R.E.)"
- Next in thread: shane miller: "Re: clarification on recursively enumerable (R.E.)"
- Reply: shane miller: "Re: clarification on recursively enumerable (R.E.)"
- Reply: Acid Pooh: "Re: clarification on recursively enumerable (R.E.)"
- Messages sorted by: [ date ] [ thread ]
Date: 8 Nov 2004 15:04:49 -0800
shane says...
>So given the claim that the Godel number 'A' is a valid
>proof in the theory T, a decision method for proofs in
>T, will, on the basis of R.E.
>
>1. accept or reject 'A' in a finite amount of time
>2. never halt
>
>Regarding (2): given an infinite amount of time the
>decision method will ultimately accept or reject 'A'
>as a valid proof in the theory. But of course 'A' is
>not proved because it required an infinite number of
>steps whereas proofs are always finite.
>
>Now, is this a valid line of thinking regarding (2)
>
>(A) An infinite amount of time may be required to
> decision 'A' because there is enumerably infinite
> source of fomulas. And the number of permuations
> of those formulas --- even when restricted to
> sentences --- is infinite so finding the proof
> of 'A' could require an infinite amount of time.
That's not quite right. If A has a proof, then it has
a proof that can be discovered in a finite amount of time,
under the usual notion of what a proof is. The actual
situation for r.e. theories is this:
1. If A is provable, then that fact can be demonstrated in
a finite number of steps.
2. If A is *not* provable, then there may be no way to
demonstrate it in a finite number of steps.
In no circumstances can a proof of A require an infinite
number of steps, at least not in order first-order logic.
There is an extention of first-order logic, called "omega logic"
that introduces an infinitary proof rule:
A(0)
A(1)
.
.
.
--------------
forall x, A(x)
This means that if you can prove A(0), and A(1), and A(2), etc.
then you can conclude forall x, A(x). In omega logic, some proofs
do require an infinite number of steps. But this logic is not actually
used in reasoning by mortal human beings, since none of us can actually
carry out a proof that has an infinite number of steps.
-- Daryl McCullough Ithaca, NY
- Next message: Will Twentyman: "Re: clarification on recursively enumerable (R.E.)"
- Previous message: Will Twentyman: "Re: Resolving the paradoxes of set theory"
- In reply to: shane: "clarification on recursively enumerable (R.E.)"
- Next in thread: shane miller: "Re: clarification on recursively enumerable (R.E.)"
- Reply: shane miller: "Re: clarification on recursively enumerable (R.E.)"
- Reply: Acid Pooh: "Re: clarification on recursively enumerable (R.E.)"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
