Skip to main content
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
Source Link

I know that $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable$L$ not being decidable ). But is $L$ recognizable?

What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $\langle M\rangle$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $\langle M\rangle$ (in lexicological order), thus using $H$ I am able to decide $L$ which I know is not possible.

Is my method correct ? In either case is there a better method for example is there a general way for proving that a language is not recognizable like for undecidability we try to reduce an undecidable problem to the current problem ?

I know that $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable?

What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $\langle M\rangle$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $\langle M\rangle$ (in lexicological order), thus using $H$ I am able to decide $L$ which I know is not possible.

Is my method correct ? In either case is there a better method for example is there a general way for proving that a language is not recognizable like for undecidability we try to reduce an undecidable problem to the current problem ?

I know that $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable?

What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $\langle M\rangle$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $\langle M\rangle$ (in lexicological order), thus using $H$ I am able to decide $L$ which I know is not possible.

Is my method correct ? In either case is there a better method for example is there a general way for proving that a language is not recognizable like for undecidability we try to reduce an undecidable problem to the current problem ?

added 27 characters in body; edited tags; edited title
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Is the language $L=\{<M>|\; |L(M)| \; is \;TMs that accept finite \; \}$languages Turing recognizable-recognizable?

I know that $L=\{<M>|\; |L(M)| \; is \; finite \; \}$$L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable ( by Riceby Rice's theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable  ?
What

What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $<M>$$\langle M\rangle$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $<M>$$\langle M\rangle$ ( inin lexicological order  ), thus using $H$ I am able to decide $L$ which I know is not possible.
Is

Is my method correct ? In either case is there a better method for example is there a general way for proving that a language is not recognizable like for undecidability we try to reduce an undecidable problem to the current problem ?

Is the language $L=\{<M>|\; |L(M)| \; is \; finite \; \}$ Turing recognizable?

I know that $L=\{<M>|\; |L(M)| \; is \; finite \; \}$ is not decidable ( by Rice theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable  ?
What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $<M>$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $<M>$ ( in lexicological order  ), thus using $H$ I am able to decide $L$ which I know is not possible.
Is my method correct ? In either case is there a better method for example is there a general way for proving that a language is not recognizable like for undecidability we try to reduce an undecidable problem to the current problem ?

Is the language TMs that accept finite languages Turing-recognizable?

I know that $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable?

What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $\langle M\rangle$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $\langle M\rangle$ (in lexicological order), thus using $H$ I am able to decide $L$ which I know is not possible.

Is my method correct ? In either case is there a better method for example is there a general way for proving that a language is not recognizable like for undecidability we try to reduce an undecidable problem to the current problem ?

deleted 3 characters in body; edited title
Source Link
advocateofnone
  • 3k
  • 1
  • 26
  • 44

Is the language $L=\{<M>|\; L|L(M) \;has\; finite\; strings| \; is \; finite \; \}$ Turing recognizable?

I know that $L=\{<M>|\; L(M) \;has \;finite \;strings \}$$L=\{<M>|\; |L(M)| \; is \; finite \; \}$ is not decidable ( by Rice theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable ?
What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $<M>$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $<M>$ ( in lexicological order ), thus using $H$ I am able to decide $L$ which I know is not possible.
Is my method correct ? In either case is there a better method for example is there a general way for proving that a language is not recognizable like for undecidability we try to reduce an undecidable problem to the current problem ?

Is the language $L=\{<M>|\; L(M) \;has\; finite\; strings \}$ Turing recognizable?

I know that $L=\{<M>|\; L(M) \;has \;finite \;strings \}$ is not decidable ( by Rice theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable ?
What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $<M>$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $<M>$ ( in lexicological order ), thus using $H$ I am able to decide $L$ which I know is not possible.
Is my method correct ? In either case is there a better method for example is there a general way for proving that a language is not recognizable like for undecidability we try to reduce an undecidable problem to the current problem ?

Is the language $L=\{<M>|\; |L(M)| \; is \; finite \; \}$ Turing recognizable?

I know that $L=\{<M>|\; |L(M)| \; is \; finite \; \}$ is not decidable ( by Rice theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable ?
What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $<M>$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $<M>$ ( in lexicological order ), thus using $H$ I am able to decide $L$ which I know is not possible.
Is my method correct ? In either case is there a better method for example is there a general way for proving that a language is not recognizable like for undecidability we try to reduce an undecidable problem to the current problem ?

Source Link
advocateofnone
  • 3k
  • 1
  • 26
  • 44
Loading