0
$\begingroup$

I've learned this a few years ago that this is impossible unless one simply 'executes' (in a modern computing sense) the input with the language rules, but I have some problems in just using this statement.

  • The fundamental doubt is that the statement itself is well-stated. If I'm using the term 'execution' to describe the act of matching the rules one input element by one, is this statement valid?

  • Is this statement (deciding whether an input sequence is in a language is impossible without an execution) not exactly limited to RE? In other words, I wonder this statement also holds even for the languages in other classes.

  • I'm not even sure how I can search for this statement and confirm from the external source.

(By RE, here I indicate the recursively enumerable languages, not the regular expression)

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm not sure your vocabulary is understandable. Could you give a precise definition of what you mean by "executing" an input? Also, there seems to be some conceptual misunderstanding here since inputs do not "satisfy" a language. Languages are sets; an input is either in it or not. $\endgroup$
    – dkaeae
    Commented Aug 9, 2019 at 7:26
  • $\begingroup$ @dkaeae There could be multiple issues as I'm not a native speaker nor majoring in automata theory. By execution, I mean investigating the input elements one by one dictated by the rules, like 'executing' an instruction in a program. And when it comes to the latter one, I think describing my question as 'whether an input is in the language' is more appropriate. $\endgroup$
    – Gwangmu Lee
    Commented Aug 9, 2019 at 7:40

1 Answer 1

Reset to default
1
$\begingroup$

A language is recursively enumerable if there exists a Turing machine that:

  • halts and says "yes" whenever its input is in the language;
  • either halts and says "no" or just doesn't halt whenever its input is not in the language.

The undecidability of the halting problem means that there is no algorithm which, when given an RE language (or, rather, when given the code of a Turing machine which accepts some language) and a string, can determine whether the string is in the language or not. In general, all you can do is run the Turing machine and see if it accepts its input. However, if it seems to be taking a long time to run then, in general, there's no way of figuring out if it's in an infinite loop, so even this doesn't actually work.

However, that doesn't mean that you can never tell whether a particular machine will have certain behaviour. For example, it's easy to tell that the machine

IF the first character of the input is 0 THEN accept
ELSE [do something complicated]

will accept any string that begins with $0$. More sophisticated analytic techniques will allow you to prove that more complicated machines do or do not accept certain inputs. However, what the lack of a general algorithm means is that, whatever analytic techniques you develop, there will be some machines and some inputs (in fact, infinitely many of them) where your techniques fail. In those cases, your only options are to develop even more advanced techniques (which still won't work in all cases) or to give up and just run the machine.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This was exactly the answer that I wanted. Actually I've learned this years ago but forgot many bits of the theory. Thanks! $\endgroup$
    – Gwangmu Lee
    Commented Aug 9, 2019 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.