Re: Alan Turing's Halting Problem is incorrectly formed

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 06/10/04 

Date: 10 Jun 2004 04:04:54 -0700

|-|erc says...

>Regarding
>
> Your definition of F is
>
> Forall x, x<->proof(x)
>
> which involves quantification over sentences (or propositions).
> That is not possible in first-order logic
>
>
>Are you saying this is not possible also then?
>> ~ExProof(x,y,y)

No, in Proof(x,y,y), x and y are *numbers*, not sentences.
(They are numbers that *code* for sentences, but they are
still numbers.)

Proof(x,y,y) is a formula involving x and y. This is in contrast to the
expression

   For all x, x <-> Proof(x)

In that expression, if you meant for x to be a *number*
then the left-side of the <-> is incorrect --- only formulas
can appear on the left side of <->. If you meant for x
to be a sentence, then the quantifier Forall x makes no
sense, because you can only quantify over numbers. 

--
Daryl McCullough
Ithaca, NY

Relevant Pages

  • Re: The Law of the Excluded Middle again (long)
    ... Inside the scope of quantification, ... and you seem to be saying exactly the same ... The distinction between truth and provability, ... ridiculous howling error, but it is not the particular tremendously ...
    (sci.math)
  • Re: [9fans] parallel systems
    ... The issue here is that all the things you are saying can be (and have ... There are variations in just ... This type of discussion, absent some sort of quantification, belongs ... akin to arguing about power without knowing what terms like volts and ...
    (comp.os.plan9)
  • Re: Uncertainty and Continuity?
    ... > |> By saying that we can never completely quantify Reality, is to admit ... > limitation and attributes and c is as a stepping stone in our quantification ...
    (sci.physics.relativity)
  • Re: Godels comments about the "true reason" for incompleteness
    ... why not formally admit propositions ... arbitrary Q. Obviously there is an implied quantification over Q, ... letters of the object language). ... refutable in PA and as confirmed by the supposed undecidability of S. ...
    (sci.logic)
  • Re: RM formalism supporting partial information
    ... nonsense, and I stopped reading. ... be nonsensical because universal quantification is only meaningful ... The important concepts are tuples, propositions, predicates etc. ...
    (comp.databases.theory)
Loading