Register to reply

Turing Machines & Undecidability

by crazyautomata
Tags: machines, turing, undecidability
Share this thread:
crazyautomata
#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
New model helps explain how provisions promote or reduce wildlife disease
Stress can make hard-working mongooses less likely to help in the future
Grammatical habits in written English reveal linguistic features of non-native speakers' languages
Max.Planck
#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
#3
Mar13-12, 08:15 PM
P: 3
I mean partially decidable or recursively enumerable.

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