On 30 Jul 2012, at 15:34, Alberto G. Corona wrote:
"Computations are not proof. There are similarities, and there are a
lot of interesting relationships between the two concepts, but we
cannot use proof theory for computation theory"
What goes to Another intriging duality : The Curry-Howard
isomorphism between computer programs and mathematical proofs. It
seems that both have the same structure after all.
http://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence
And, as the Stephen mentioned paper makes use of Category theory and
Topos Theory (That is a variation of CT) to discover the duality ,
The curry howard isomorphism can be reshaped in terms of category
theory.
What all these dualities say is that math structures can be
expressed as particular cases of a few, more encompassing
categories. And 2) since the human mind arrange his knowledge in
categories, according with the Phillips paper I mention a few posts
ago, this bring light about the nature of reality . No only the
phisical world is mathematical, but this mathematical world has a
few patterns after all. That economy may say something about the
reality, that for me is related with the process of discovery both
conscious and mechanical discovery: the natural evolution has
discovered the mathematical essence of reality and organized the
brain in categories. And scientist create hypotheses by applying
their categorical intuitions to new fields of knowledge, for example
to discover new mathematical structures or new relations between
existing structures. At the same time, if the mathematical reality
is not so simple, it would have been not discoverable in the first
place, and it would not exist.
Actually I wrote, and did not send a reply on some of your remark on
category theory. I agree that category is very interesting. But
category are nice and smooth only around the first person notion. In
fact in the math part of AUDA, categories and non boolean toposes can
be used to model the arithmetical first person (the one we can
canonically associate to self-referential machine). They are solipsist
by nature, not by doctrine, and this correspond to the simple fact
that we build our own private mental space, so the first person is
intuitionist. category unfortunately don't handle well the second
recursion theorem, and the whole intensional part of non constructive
math, which makes them hard to use for the non "first person"
hypostases.
Also, category theory is abstract and difficult. It is already hard to
find people with some maturity simultaneously in quantum physics,
mathematical logic and "philosophy-of-mind-computer-science", so
adding the category notion tends to make the intersecting set empty.
Category are useful for the functional part of comp, and awkward for
the intensional part of computer science.
The Curry-Howard isomorphism is *very* interesting, and was the main
reason I made a little teaching on the combinators (and lambda terms)
some year ago on this list, but of course that kind of things tend to
be quickly technical, so I have come back with the numbers instead.
For those who remember the combinators S and K, the typing of SKK
gives the "well known" proof of "A -> A" from the axioms A->(B->A),
and A->(B->C) ->. (A->B)->(A->C) which gives the "types" of K and S
respectively.
Note that the Curry-Howard isomorphism highlights the fact that proof
and computations are different concept, as the proof are related to
the programs and not the execution, and this does not fit well with
the measure problem on the computations, where we can use instead the
correspondence between some proofs of sigma_1 proposition and the
computations, but we can still relate all this in some categories
indeed. All this is a bit too much technical, and there are many
technical open problems.
Note also that the Curry-Howard isomorphism was also at the start only
linking constructive proof with programs, but people like Jean Louis
Krivine (and some others) have extended it on non constructive proofs,
and this might be useful in the future of the "AUDA" program. No doubt
on this, even if I am not sure of Jean-Louis Krivine choice of the way
to extend it.
Bruno
PS I am re-connected!
2012/7/30 Bruno Marchal <marc...@ulb.ac.be>
Le 29-juil.-12, à 07:34, Stephen P. King a écrit :
Dear Bruno,
From http://www.andrew.cmu.edu/user/awodey/preprints/fold.pdf
First-Order Logical Duality
we read:
"In the propositional case, one passes from a propositional theory
to a Boolean algebra by
constructing the Lindenbaum-Tarski algebra of the theory, a
construction
which identifies provably equivalent formulas (and orders them by
provable
implication). Thus any two complete theories, for instance, are
‘algebraically
equivalent’ in the sense of having isomorphic Lindenbaum-Tarski
algebras.
The situation is precisely analogous to a presentation of an algebra
by generators and relations: a logical theory corresponds to such a
presentation,
and two theories are equivalent if they present ‘the same’ –
i.e. isomorphic –
algebras."
The construction of the Lindenbaum-Tarski algebra is
implemented by
1) identification of provably equivalent formulas
and
2) ordering them by provable implication
1) might be equivalent to your sheaf of infinities of
computations
Computations are not proof. There are similarities, and there are a
lot of interesting relationships between the two concepts, but we
cannot use proof theory for computation theory.
(but requires a bisimilarity measure) and 2) seems contrary to the
Universal Dovetailer ordering idea as it implies tight sequential
strings (but tightness might be recovered by Godel Numbering but not
uniquely for infinitely long strings). But there is a question
regarding the constructability of the Lindenbaum-Tarski algebra
itself!
This is needed for special application of the Lindenbaum-Tarski
algebra.
Does it require Boolean Satisfiability for an arbitrary
propositional theory to allow the construction?
Not in general. Boolean satisfiability concerns only classical
logic, but none of the hypostases, except the "arithmetical truth",
do correspond (internally) to a classical logic.
Bruno
It surely seems to! But is there a unique sieve or filter for the
ordering of implication? How do we define invariance of meaning
under transformations of language? Two propositional theories in
different languages would have differing implication diagrams , so
how is bisimulation between them defined????? There has to be a
transformation that generates a diffeomorphism between them.
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com
.
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
.
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com
.
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
.
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en.
