Re:Where do type systems come from? (2017)
by rssoconnor on Sunday October 03, 2021 @12:39PM
(#28738439)
> I wouldn't fire the analyst in your example, by the way, because the fault would be mine: I should have just specified what complexity bound would be acceptable in a termination proof of the algorithm for it to be practical for my purposes.
I thought someone might say something like this. My counter is that if the analyst just used a normal proof system (i.e. one that doesn't assume false (in the standard model) axioms) then we could use Goedel's Dialectica [1] to mine the proof for some (probably crappy) complexity bound. That said, this is getting close to the edge of my knowledge on this subject.
[1] http://math.stanford.edu/~feferman/papers/dialectica.pdf
Re:Where do type systems come from? (2017)
by rssoconnor on Sunday October 03, 2021 @11:29AM
(#28737938)
I guess Tarski's definition of truth is relative to some interpretation, but the usual unqualified version of his definition is implicitly relative to the standard model of natural numbers. (Edit: or maybe it is me who is using the notion of Tarski's definition of truth incorrectly.)
I wouldn't fire the analyst in your example, by the way, because the fault would be mine: I should have just specified what complexity bound would be acceptable in a termination proof of the algorithm for it to be practical for my purposes.