Re: Yet another Attempt at Disproving the Halting Problem

From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 08/10/04 

Date: Tue, 10 Aug 2004 10:45:37 +0200

Jerry Coffin wrote:
> "Peter Olcott" <olcott@worldnet.att.net> wrote in message news:<dLWPc.381367$Gx4.219217@bgtnsc04-news.ops.worldnet.att.net>...
>
>>Within deduction it is never valid.
>>Only deduction can guarantee that it always provides correct results. It is
>>considered to be valid inductive inference, yet inductive inference can not
>>guarantee correct results. Deduction can not err, induction can err.
>
> You should really quit while you're ahead -- or in this case, before
> you get further behind.
>
> An inductive proof can be just as much of a proof as a deductive
> proof.
>
> What you're (apparently) thinking of is not induction. Just to give an
> example, I could look at a bunch of odd primes, and conclude from it
> that all odd numbers are primes.
>
> That's not induction though. In a real inductive proof, the first part
> is usually fairly trivial: prove the result for the most trivial case
> you can -- in the example above, I'd prove that 3 is prime. Then comes
> the part that's usually harder: I have to prove that if it's true for
> N, then it's also true for whatever's needed to generate the rest of
> the applicable values. In the case above, I'd have to prove that for
> any odd N, if N is prime then N+2 is also prime. Since I can't do
> that, the inductive proof doesn't err.

It seems you are referring to "mathematical" induction,
which contrary to its name, is just another -deductive-
(logical) rule of inference.

Another kind of inference, called inductive, is distinct
from deduction. Sometimes it is called natural or scientific
or rhetorical induction. It is not -formally- sound (always
necessarily correct) but it works well in practice. It's
the kind of reasoning used in natural sciences for
determining laws of physics, etc. or in a court room for
determining guilt. 

-- 
Mitch Harris
(remove q to reply)

Relevant Pages

  • Re: Yet another Attempt at Disproving the Halting Problem
    ... >> Only deduction can guarantee that it always provides correct results. ... Deduction can not err, induction can err. ... > An inductive proof can be just as much of a proof as a deductive ... > that all odd numbers are primes. ...
    (comp.theory)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... >> Only deduction can guarantee that it always provides correct results. ... Deduction can not err, induction can err. ... > An inductive proof can be just as much of a proof as a deductive ... > that all odd numbers are primes. ...
    (comp.lang.cpp)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... >> Only deduction can guarantee that it always provides correct results. ... Deduction can not err, induction can err. ... > An inductive proof can be just as much of a proof as a deductive ... > that all odd numbers are primes. ...
    (sci.logic)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... >>Only deduction can guarantee that it always provides correct results. ... >>considered to be valid inductive inference, ... Deduction can not err, induction can err. ... > An inductive proof can be just as much of a proof as a deductive ...
    (sci.logic)
  • Re: Paganos Truthlikeness
    ... classic difficulty with deduction is that it runs downhill. ... Induction climbs up hill; it starts from the muck of our ... are a good many tests of reliability. ... "Evidence confirming an observation is ...
    (talk.origins)