Skip to main content
added 137 characters in body
Source Link
Rick Decker
  • 14.9k
  • 5
  • 42
  • 54

The problem with your proposed algorithm is where you say

... choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings.

How are you going to do this? If you could, then you would have answered your original question, i.e., you've fallen into the trap of assuming what you want to prove.

In fact, your language $L$ isn't recursively enumerable.


There are at least two ways to show that $L$ isn't r.e.. I'll give one, but it requires that you be able to show that $L$ isn't recursive. Rice's theorem is an immediate way, but you don't know it yet, so you'll have to reduce it from a known non-recursive language like the Halting language. That's not hard, but I won't give it now. Just accept for the moment that $L$ is not recursive.

Suppose that we wrongly guessed that $L$ was recursive and we wanted to build a recognizer for it. One way is to simply dovetail all strings and test whether $M$ accepted any odd-length strings (so we'd know then if $M$ wasn't in $L$). This gives us a proposed recognizer for $L$:

RL(<M>) =
  for n = 0, 1, ...
     for s = s0, ..., sn  \\in the standard order on all strings
       run M on s for one move
         if M(s) = accept AND |s| is odd
           reject

If $M$ accepts any odd-length string, sooner or later this program will find it and so will be able to recognize that $M$ is not in $L$. Of course this isn't what we wanted: we need to make a program that recognized if a given $M$ is in $L$. However, all is not lost---simply by changing the "reject" to "accept" we would have made a recognizer for the complement, $\overline{L}$, so we've stumbled across the interesting fact that $\overline{L}$ is recognizable.

So what, you might ask? Remember, if a language $A$ and its complement, $\overline{A}$ are both r.e., then $A$ must be recursive. We just showed that $\overline{L}$ is r.e., so if $L$ was also r.e., then we could conclude that $L$ was recursive. However, you've accepted that $L$ is not recursive, so we must conclude that $L$ must not be r.e..

The problem with your proposed algorithm is where you say

... choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings.

How are you going to do this? If you could, then you would have answered your original question, i.e., you've fallen into the trap of assuming what you want to prove.

In fact, your language $L$ isn't recursively enumerable.

The problem with your proposed algorithm is where you say

... choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings.

How are you going to do this? If you could, then you would have answered your original question, i.e., you've fallen into the trap of assuming what you want to prove.

In fact, your language $L$ isn't recursively enumerable.


There are at least two ways to show that $L$ isn't r.e.. I'll give one, but it requires that you be able to show that $L$ isn't recursive. Rice's theorem is an immediate way, but you don't know it yet, so you'll have to reduce it from a known non-recursive language like the Halting language. That's not hard, but I won't give it now. Just accept for the moment that $L$ is not recursive.

Suppose that we wrongly guessed that $L$ was recursive and we wanted to build a recognizer for it. One way is to simply dovetail all strings and test whether $M$ accepted any odd-length strings (so we'd know then if $M$ wasn't in $L$). This gives us a proposed recognizer for $L$:

RL(<M>) =
  for n = 0, 1, ...
     for s = s0, ..., sn  \\in the standard order on all strings
       run M on s for one move
         if M(s) = accept AND |s| is odd
           reject

If $M$ accepts any odd-length string, sooner or later this program will find it and so will be able to recognize that $M$ is not in $L$. Of course this isn't what we wanted: we need to make a program that recognized if a given $M$ is in $L$. However, all is not lost---simply by changing the "reject" to "accept" we would have made a recognizer for the complement, $\overline{L}$, so we've stumbled across the interesting fact that $\overline{L}$ is recognizable.

So what, you might ask? Remember, if a language $A$ and its complement, $\overline{A}$ are both r.e., then $A$ must be recursive. We just showed that $\overline{L}$ is r.e., so if $L$ was also r.e., then we could conclude that $L$ was recursive. However, you've accepted that $L$ is not recursive, so we must conclude that $L$ must not be r.e..

added 137 characters in body
Source Link
Rick Decker
  • 14.9k
  • 5
  • 42
  • 54

The problem with your proposed algorithm is where you say

... choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings.

How are you going to do this? If you could, then you would have answered your original question, i.e., you've fallen into the trap of assuming what you want to prove.

In fact, your language $L$ isn't recursively enumerable.

The problem with your proposed algorithm is where you say

... choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings.

How are you going to do this?

In fact, your language $L$ isn't recursively enumerable.

The problem with your proposed algorithm is where you say

... choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings.

How are you going to do this? If you could, then you would have answered your original question, i.e., you've fallen into the trap of assuming what you want to prove.

In fact, your language $L$ isn't recursively enumerable.

Source Link
Rick Decker
  • 14.9k
  • 5
  • 42
  • 54

The problem with your proposed algorithm is where you say

... choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings.

How are you going to do this?

In fact, your language $L$ isn't recursively enumerable.