News for hackers. Stuff that matters.
Re:Where do type systems come from? (2017) by auggierose on Sunday October 03, 2021 @10:29AM (#28737444)
Very helpful answer, thank you! I suspected that it has something to do with "Tarski's definition of truth", but there seem to be different ideas around about what this means. While Wikipedia agrees with yours, I can point to at least one popular book ("An Introduction to Mathematical Logic" by Richard E. Hodel) that equates Tarski truth just with model theoretic truth.

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.

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.)