Lew Gordeew, WSI f. Informatik, Tuebingen University

Talk on Wednesday (10/01/2007)

This is a joint paper with A. Weiermann.


We investigate phase transitions for well-quasi-ordering (wqo) results with respect to nested finite sequences and nested finite trees under the homeomorphic embedding with symmetrical gap condition. With every wqo W in question we correlate a natural "strong" PA-extension T that proves the corresponding 2-order sentence WQO(W) stating that W is a wqo. Furthermore, we consider a parametrized 1-order "slow" wqo sentence SWQO(W,...,x) with x ranging over computable reals, and actually compute a real number r such that the following hold:

  1. If x < r, then SWQO(W,...,x) is provable in PA.

  2. If x > r, then SWQO(W,...,x) is not provable in T.

Such (uniquely determined) real r is called phase transition for T and SWQO(W,...,x). These results strengthen Kruskal-Friedman-Gordeew-Kriz wqo theorems and Weiermann's phase transitions concerning Kruskal-Friedman-Schuette-Simpson cases.

Talk on Thursday (11/01/2007)


We present a simple, purely logical interpretation of "Computing the future" by N.C.A da Costa and F.A, Doria concerning (un)provability of P vs. NP.

TecMF: TalksLew2007 (last edited 2010-08-11 15:16:53 by localhost)