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


More information about the FOM mailing list