Results 1 to 2 of 2

Math Help - Formal proof

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    1

    Formal proof

    Hi guys

    I am a beginner at FOL, trying to prove sentence1 implies sentence 2. I have followed some steps, but I am not able to formally write a proof. Please see and correct.

    sentence 1
    \forall CPlusPlus program C \exists Turning Machine Mc \forall Instance I Mc(I)=C(I)

    sentence 2
    \forall Problem P [
    \exists CPlusPlus program Cp \forall Instance I Cp(I)=P(I)
    \implies
    \exists Turning Machine Mp \forall Instance I Mp(I)=P(I) ]


    So first I assume sentence 1 is right. My first question is what should I note after this assumption? How to state the facts?


    Now I say
    for arbitrary problem P, it is true that
    \exists CPlusPlus program Cp \forall Instance I Cp(I)=P(I)

    and prove
    \exists Turning Machine Mp \forall Instance I Mp(I)=P(I)


    So I say something like
    Let Mp1 be a Turning machine for arbitrary instance I. then we have assumed Cp(I)=P(I) from sentence 2 part 1, and from sentence 1 I know Cp(I)=Mp1(I) therefore we have Mp1(I)=P(I)


    Could you help me write this formally?

    Thank you so mcuh.
    Jungar








    Thanks
    Jungar
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Formal proof

    First, Cp is a function in the expression Cp(I) since it is applied to an argument. First-order logic does not allow quantifying over functions. You can replace Cp(I) by R(Cp, I) where R (for "result") is a predicate symbol, and similarly for Turing machines (TMs) and problems.

    Second, since you mention TMs and C++ programs, you should appreciate the fact that they are syntactic objects constructed using specific rules. A TM is not a C++ program, which is not a Java program, even if all three solve the same problem. So, if you need a formal proof, please specify the proof calculus, which is also a requirement is this sticky thread. Without it, you can only write an informal proof, which is similar to a description of an algorithm in English.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Formal Proof
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 30th 2011, 01:12 PM
  2. formal proof of set
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 6th 2010, 10:36 PM
  3. Formal proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 14th 2009, 10:19 PM
  4. formal proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 2nd 2009, 09:17 AM
  5. Formal Proof
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 12th 2008, 02:43 PM

Search Tags


/mathhelpforum @mathhelpforum