- Does a given Turing machine M halt on all inputs?
- Does Turing machine M halt for
*any*input? (That is, is L(M)=?) - Does Turing machine M halt when given a blank input tape?
- Do two Turing machines M
_{1}and M_{2}accept the same language? - Is the language L(M) finite?
- Does L(M) contain any two strings of the same length?
- Does L(M) contain a string of length k, for some given k?

Copyright © 1996 by David Matuszek

Last modified Apr 14, 1996