Re: Question: Mathematics and Computer Science

On Apr 2, 7:28 pm, Aaron Hsu <aaron....@xxxxxxxxxxxxxxxxx> wrote:
Hello all,

This is not exactly a scheme question, but I assume many of you will
have some good insight and advice to help me understand this topic.

My mathematics professor, who is by no means a computer scientist, made
a oomment regarding the relationship between computer science and
mathematics. He personally guessed that any conceivable computer
program ought to be theoretically provable. That is, even if it might
not be reasonably feasible to actually develop and verify the proof, it
is conceivable that any computer program should be provable
mathematically (I assume this is just a way of saying that it is
rigorously provably correct, but correct me, please if I am wrong here).

Your professor is wrong. There exist programs that are correct but
cannot logically have a proof of correctness. This is a direct
consequence
of Godel's Incompleteness Theorem.

However, as I began to think about this I wondered if this was indeed
the case. Assuming a turing complete computer language, is it possible
to create a program which does not have a conceivable proof of
correctness that would fall within the realm of mathematical rigour or
domain? My inclination is to say, yes, there is such a program;
however, my professor guesses that there is not; neither of us really
knows one way or the other. The second question along these lines is
whether it is possible to create a program which is provably unprovable.

Yes.


.

Relevant Pages

  • Re: Category Theory books
    ... > 2)Conceptual Mathematics: ... It is difficult to give advice here without knowing your ... The book is the standard introduction for those students ... It will provide you with most of the technical tools ...
    (sci.math)
  • Re: Pls help with sister becoming crackpot
    ... A lot of mathematics is done the way she's doing it. ... important results are discovered through flashes of insight. ... of useless random thoughts. ... And this year's wheat from last decade's wheat as well. ...
    (sci.math)
  • Re: Pls help with sister becoming crackpot
    ... The hard problem is finding nontrivial factors of composites. ... A lot of mathematics is done the way she's doing it. ... A lot of it is about writing numbers on a sheet of paper and looking for patterns, and a lot of important results are discovered through flashes of insight. ... Crucial insights often come to mathematicians during a walk in the park, or early in the morning when they're not quite awake, but so do a lot of useless random thoughts. ...
    (sci.math)
  • Re: Humanistic mathematics: response to David Petry
    ... The problem is precisely that the anti-Cantorians offer *no* ... insight into mathematics, as far as I can see. ... grumbling, whining, whimpering and insults but no mathematics. ... intolerant Cantorians and indulges in his own combination ...
    (sci.logic)
  • Re: Raatikainens critique of Chaitin
    ... >> there is randomness in arithmetic, that there are certain facts in ... >> This in fact is a great insight into ... >> the nature of mathematics, as it destroys the Greek idea of ... > What does it mean to say that Chaitin's insight destroys the Greek ...
    (sci.math)
Loading