Wikipedia: Turing machine/Talk

Difference (from prior major revision) (no other diffs)

Changed: 4c4,8

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

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