Skip to main content
Tweeted twitter.com/#!/StackCompSci/status/296073989837713409

Re: Turing Machines. What is the difference between a TM accepting and deciding a language?

Frankly I'm very uncomfortable with the material right now. There are some things I can understand, but many I still do not.

My first assignment is asking me in one question (which I do know how to do) to give a full description of a TM that accepts a language L={x in {0,1}* | x is divisible by 4}$L = \{ x \in \{0,1\}^* \mid x \text{ is divisible by } 4 \}$. I I know that any binary string ending with 00$00$ is divisible by 4, so {00,100,1100,1000,11100,11000,10100,10000,...} are all in$\{00,100,1100,1000,11100,11000,10100,10000,\dots\}$ is the language that this TM accepts.

But on the topic of (Unun)decidability... I: I know that a language is decidable if there exists a TM that accepts all strings in, and only strings from that language - and that same TM rejects all strings and only strings not in that language.

So with that said,Which leads to the question: What is there athe difference between a Turing machine accepting and deciding a language?

Re: Turing Machines. What is the difference between a TM accepting and deciding a language?

Frankly I'm very uncomfortable with the material right now. There are some things I can understand, but many I still do not.

My first assignment is asking me in one question (which I do know how to do) to give a full description of a TM that accepts a language L={x in {0,1}* | x is divisible by 4}. I know that any binary string ending with 00 is divisible by 4, so {00,100,1100,1000,11100,11000,10100,10000,...} are all in the language that this TM accepts.

But on the topic of (Un)decidability... I know that a language is decidable if there exists a TM that accepts all strings in, and only strings from that language - and that same TM rejects all strings and only strings not in that language.

So with that said, is there a difference between

What is the difference between a TM accepting and deciding a language?

Frankly I'm very uncomfortable with the material right now. There are some things I can understand, but many I still do not.

My first assignment is asking me in one question (which I do know how to do) to give a full description of a TM that accepts a language $L = \{ x \in \{0,1\}^* \mid x \text{ is divisible by } 4 \}$. I know that any binary string ending with $00$ is divisible by 4, so $\{00,100,1100,1000,11100,11000,10100,10000,\dots\}$ is the language that this TM accepts.

But on the topic of (un)decidability: I know that a language is decidable if there exists a TM that accepts all strings in, and only strings from that language and that same TM rejects all strings and only strings not in that language.

Which leads to the question: What is the difference between a Turing machine accepting and deciding a language?

Source Link
Mirrana
  • 4.4k
  • 5
  • 21
  • 22

Re: Turing Machines. What is the difference between a TM accepting and deciding a language?

Frankly I'm very uncomfortable with the material right now. There are some things I can understand, but many I still do not.

My first assignment is asking me in one question (which I do know how to do) to give a full description of a TM that accepts a language L={x in {0,1}* | x is divisible by 4}. I know that any binary string ending with 00 is divisible by 4, so {00,100,1100,1000,11100,11000,10100,10000,...} are all in the language that this TM accepts.

But on the topic of (Un)decidability... I know that a language is decidable if there exists a TM that accepts all strings in, and only strings from that language - and that same TM rejects all strings and only strings not in that language.

So with that said, is there a difference between