CODEWITHSUNDEEP
automationfinite-automatacomputation-theoryturing-machines
Gaurav Joshi
Gaurav Joshi

Reputation: 97

Can a more powerful computing machine (Turing Machine) not decide a problem which can be well decide by less powerful machine in Chomsky hierarchy

For a set of input alphabets (a,b) , say Language L is defined as "Set of all 2016 length strings".

so,

First Scenario : A finite Automata can clearly decide whether any input given over input alphabets (a,b), is in L or not, by accepting or rejecting it OR in other words it can decide that the input string is of length 2016 or not ?

Second Scenario : Let's say I wanna see how turing machine works, so even after getting the answer from a less powerful machine, we run that arbitary string on Turing Machine.

But unfortunately, Years passed but the turing machine does not halt, that is - "it has fallen into infinte loop for that arbitary input".

I am very much confused by this fact that why even being more powerful than a finite Automata, a turing machine cannot decide what a Finite Automata decided

Edited:

Example : L = ({M} | M is a turing machine that accepts a string of length 2015)

we know that if we see the above example through the prism of regular language then language of length 2015 are finite and hence they are regular.

But the language L for Turing machine M is Undecidable and Recursively enumerable.

that's more or less my confusion

Upvotes: 1

Views: 202

Answers (1)

Patrick87
Patrick87

Reputation: 28312

Turing machines can decide membership in any regular language. I think your confusion is that a TM can loop forever, and certainly many TMs do that and many others that don't also don't decide any particular regular language. However, there's guaranteed to be a TM that decides any regular language L:

  • take a DFA for L;
  • write the input on the tape;
  • transition through the DFA based on symbols read from the tape left to right;
  • halt-accept if ending in an accepting state;
  • halt-reject otherwise

Upvotes: 2

Related Questions