1. ## Turing Machines

I have a question regarding undecidable languages.
Let L1 = { M | M is an encoding of a Turing machine that accepts any input} and L2 = { M | M is an Turing machine with at most 100 states}. Is L1 intersect L2 decidable?
I think L1 is undeciable and L2 is decidable. And I guess L1 intersect L2 is undecidable but I can't find a reduction to any undecidable problems. Any help will be appreciated!

2. ## Re: Turing Machines

I agree that L1 is undecidable, because there is an easy reduction from it to the Halting Problem, which I assume you've already figured out. L2 is also clearly decidable; you just design a machine which takes the encoding of M as an input and counts the number of states. I think there is another easy reduction to show L1 intersect L2 is undecidable - essentially the same reduction as for L1 from the Halting problem, except that you also add 100 redundant states in order to satisfy L2. What do you think?

Edit: I misread less than 100 states for more than 100 states. In this case, we still use the reduction for L1 combined with a simulation to ensure using less than 100 states. Sorry, if I've confused you.

3. ## Re: Turing Machines

Thank you very much for your reply! I feel like my mind is trapped somewhere since I just don't see the reduction. I read the language as {M | M is a machine with less than 101 states and accepts any input}. For L1, I got a reduction:

We know the halting problem "given a machine M and input x, does M halt on x". Now construct a new machine M': if the input = x, then run M on x, if it halts, accept. If input != x, accept the input. We can see M' accepts any input iff M halts on x. And M' doesn't accept everything iff M does not halt on x. So we got the reduction. L1 is undecidable. Now I got this gap since the number of states in M is unbounded. If we put limit on the number of states in M', then essentially we are reducing from 100-State-HALT instead of the original HALT. For example, M is with 1000 states and M' will be rejected regardless whether M halts on x or not.

Like I said, I hope I'm just mistaking something so there is an easy reduction. Would you please elaborate your idea:
Originally Posted by StaryNight
we still use the reduction for L1 combined with a simulation to ensure using less than 100 states.
Any comment will be appreciated! Thank you StaryNight

4. ## Re: Turing Machines

Originally Posted by crazyautomata101
Thank you very much for your reply! I feel like my mind is trapped somewhere since I just don't see the reduction. I read the language as {M | M is a machine with less than 101 states and accepts any input}. For L1, I got a reduction:

We know the halting problem "given a machine M and input x, does M halt on x". Now construct a new machine M': if the input = x, then run M on x, if it halts, accept. If input != x, accept the input. We can see M' accepts any input iff M halts on x. And M' doesn't accept everything iff M does not halt on x. So we got the reduction. L1 is undecidable. Now I got this gap since the number of states in M is unbounded. If we put limit on the number of states in M', then essentially we are reducing from 100-State-HALT instead of the original HALT. For example, M is with 1000 states and M' will be rejected regardless whether M halts on x or not.

Like I said, I hope I'm just mistaking something so there is an easy reduction. Would you please elaborate your idea:

Any comment will be appreciated! Thank you StaryNight
I don't follow your reduction from the Halting Problem to L1, so let me try and write my own formalisation:
Assume L1 is decidable. Then there exists a machine M, that accepts the encoding of all machines that accepts any input.
Construct H to decide the halting problem as follows:
Take input (c,x), where c is the encoding of a Turing Machine and x is an input.
Construct c' as the code of the machine that clears the input tape, writes x and runs program c.
Run M on c'. It is not hard to see that H accepts (c,x) iff machine c halts on input x.

As I suggested, there is a very similar reduction for L1 intersect L2. Are you familiar with the Universal Turing Machine?
It is possible to construct a Turing Machine, which given the code of another Machine, is capable of simulating it.
Importantly for this problem, this machine requires much less than 100 states, which effectively means that any Turing Machine
that uses >100 states can be rewritten to use <100 states. If you combine this with the reduction above, you can show L1 intersect L2 to be undecidable.

5. ## Re: Turing Machines

Thank you very much! You're good! I didn't know that UTM can have so small no. of states. Problem solved!