Talk:Proof

The subtype Natural is pre-defined for all Ada implementations. Arithmetic upon that subtype is also pre-defined. This does not appear to be a very interesting problem in Ada. Any suggestions? --Waldorf 14:42, 21 December 2007 (MST)

This seems like less of a computing problem, and more of a discrete math problem. I'm not sure if it's a good task. --Mwn3d 14:45, 21 December 2007 (MST)

The task was intended to demonstrate dependent types. I've got some C++ code I'm working that demonstrates how it can be accomplished there. --Short Circuit 20:50, 21 December 2007 (MST)

Huh?

The data type for "natural numbers" is what would be called an "unsigned integer" in other languages, right? Or did you want us to create a data type that can deal with arbitrary-size integers?

If we're merely talking about unsigned ints, then the data type for "even numbers" is of course the exact same thing (since the two sets are isomorphic). So the programming task boils down to writing functions for I/O that take an unsigned int and interpret it as "one half of the number we're talking about". Is that what is intended here? If not, then what exactly are we supposed to do here? You see me somewhat puzzled... Sgeier 17:45, 11 March 2008 (MDT)

If you ignore the numbers given, the proposal still makes sense. I think the task was intended as an exercise of type dependency with proof systems. This possibility is supported by the project pages for Coq, Agda2 and Twelf. (How is it that all the links on this page are uncreated, I wonder...) It doesn't look like an imperative problem. It could be done in C++ with classes and operator overloading, for example. The proof is whether or not the proper code compiles. It looks like I'd intended to do that, but I recall life getting in the way that week. --Short Circuit 19:40, 11 March 2008 (MDT)

Proofs

Does this task apply to languages which are not built as theorem-proving systems? If so, what constitutes an acceptable implementation of "prove that the addition of any two even numbers is even"? --Kevin Reid 00:07, 17 February 2009 (UTC)

I'm thinking about implementing theorem proving system as an application in the language. This could be done with at least any Turing-equivalent language. Still unsure how that would be for this particular task.Avmich 00:03, 12 November 2009 (UTC)

I did this in Haskell, but I dunno how easy it would be in other languages, especially dynamically-typed ones. —Underscore (Talk) 18:11, 18 February 2010 (UTC)

Clarification needed

The first line of the description reads: "Define a type for a sub-set of natural numbers (0, 1, 2, 3, ...) representable by a computer, and addition on them." Can somebody please clarify that last phrase, "addition on them"? I think I know what it's supposed to mean (and I'm fairly sure I understand the task as a whole) but just in case... -- Eriksiers 22:24, 5 November 2009 (UTC)

In mathematics, when we speak of "a binary operation on S", we mean a function whose domain is S × S and whose codomain is S. So "addition on the natural numbers" means an addition function that takes two naturals and returns a natural. —Underscore 00:42, 6 November 2009 (UTC)

Hmmm... I slept through most of my calculus classes, due to having THE MOST BORING TEACHER IN THE UNIVERSE (really) and as a result, most math above simple algebra I just don't get. I think I'll give this task a pass. -- Eriksiers 15:05, 6 November 2009 (UTC)

But this is not much more than elemental type theory. Hardly as complex as the infinitesimal calculus... –Donal Fellows 16:38, 6 November 2009 (UTC)

I passed Calc 2, and it still took me a couple years and lurking in discussions of C++0x before I really started understanding what was being talked about in this task. Type theory and calculus seem to me to be orthogonal subjects. --Michael Mol 19:19, 6 November 2009 (UTC)

Rightly or wrongly, elementary calculus is in most colleges a prerequisite for courses on basic proof-writing. I'm a math major and I ended up taking vector calculus before "foundations of mathematics". —Underscore 20:34, 6 November 2009 (UTC)