[FOM] Is current computability theory intuitionistic?
Timothy Y. Chow
tchow at alum.mit.edu
Thu Jun 20 21:54:57 EDT 2013
Even in computational complexity theory, which you might guess would be
more "constructive" than recursion theory, the distinction is visible.
For example it is standardly asserted that if F is any minor-closed family
of graphs, then there exists a polynomial time algorithm for testing for
membership in F, even though there is no general method for constructing
said algorithm.
Tim
More information about the FOM
mailing list