Turing Machines & Undecidability


by crazyautomata
Tags: machines, turing, undecidability
crazyautomata
crazyautomata is offline
#1
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 Phys.org
Simplicity is key to co-operative robots
Chemical vapor deposition used to grow atomic layer materials on top of each other
Earliest ancestor of land herbivores discovered
Max.Planck
Max.Planck is offline
#2
Mar13-12, 05:00 PM
P: 127
What do you mean by undecible language, the chomsky hiearchy for languages is given as follows: http://en.wikipedia.org/wiki/Chomsky_hierarchy.
crazyautomata
crazyautomata is offline
#3
Mar13-12, 08:15 PM
P: 3
I mean partially decidable or recursively enumerable.

Max.Planck
Max.Planck is offline
#4
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