Sure, it's Rice's Theorem. --AV |
Sure, it's Rice's Theorem. --AV Two things are missing from the article but I don't have time right now: * The functions that Turing machines define are only partial because TM's need not halt. * Link to recursive functions, recursive and recursively enumerable languages. --AxelBoldt |