Timeline for Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 30, 2019 at 19:33 | comment | added | Yuval Filmus | No. You're confusing Turing machines and languages. | |
| Jun 30, 2019 at 19:32 | vote | accept | WeCanBeFriends | ||
| Jun 30, 2019 at 20:37 | |||||
| Jun 30, 2019 at 19:32 | comment | added | WeCanBeFriends | Got it, that's what I was referring to. There is no algorithm that can decide whether a TM is total, however if the language is finite, then we know that that specific TM program is total, because all finite languages are decidable | |
| Jun 30, 2019 at 19:29 | comment | added | Yuval Filmus | I'm not sure what you mean by "how do I know". There is no algorithm that can determine whether an input Turing machine is total. But some Turing machines are total nevertheless. | |
| Jun 30, 2019 at 19:28 | comment | added | Yuval Filmus | A Turing machine accepts a string if it halts in an accepting state. That's the definition. | |
| Jun 30, 2019 at 19:28 | comment | added | WeCanBeFriends | Got it, but was wondering due to the halting problem, how do I know if it halts on all inputs? if the language is infinite | |
| Jun 30, 2019 at 19:27 | comment | added | WeCanBeFriends | Is it correct to say that a TM accepts a string? If so, does that mean it halts+accepts or does it mean it does not reject, ie it can loop? | |
| Jun 30, 2019 at 19:27 | comment | added | Yuval Filmus | A Turing machine is total if it halts on all inputs. This is the definition. | |
| Jun 30, 2019 at 19:26 | comment | added | WeCanBeFriends | How do I know a Turing machine is total? Maybe if the language defined by the Turing machine is finite? | |
| Jun 30, 2019 at 19:12 | history | answered | Yuval Filmus | CC BY-SA 4.0 |