Turing machine/Talk

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Privacy policy

I was thinking of adding a link to the general theorem which says that practically no non-trivial question about the behavior of Turing machines can be decided, but I forgot the name of it. Anybody knows? --AxelBoldt

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