Register to reply

Turing Machines & Undecidability

by crazyautomata
Tags: machines, turing, undecidability
Share this thread:
Mar12-12, 08:07 AM
P: 3
1. The problem statement, all variables and given/known data

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?

2. Relevant equations

3. The attempt at a solution

I think L1 is undeciable and L2 is decidable. Since we can have a many-to-1 reduction from halting to L1 and for L2, we can count the number of states in some encoding. And I guess L1 intersect L2 is still undecidable but I can't find a reduction to any undecidable problems.

Any help will be appreciated!
Phys.Org News Partner Science news on
'Office life' of bacteria may be their weak spot
Lunar explorers will walk at higher speeds than thought
Philips introduces BlueTouch, PulseRelief control for pain relief
Mar13-12, 05:00 PM
P: 127
What do you mean by undecible language, the chomsky hiearchy for languages is given as follows:
Mar13-12, 08:15 PM
P: 3
I mean partially decidable or recursively enumerable.

Mar14-12, 04:45 AM
P: 127
Turing Machines & Undecidability

Aren't they both regular?

Register to reply

Related Discussions
Turing Machines Calculus & Beyond Homework 4
Conciousness and Turing undecidability General Discussion 1
Uncountably Many Turing Machines Set Theory, Logic, Probability, Statistics 4
Turing machines Calculus 5