0
$\begingroup$

Given a Turing machine, how can I identify the language it accepts and write a set notation for L(M)?

$\endgroup$

closed as too broad by David Richerby, D.W., Ran G., Nicholas Mancuso, Juho May 13 '15 at 7:36

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ You identify the langauge in the same way that you identify what any computer program does: study it and figure it out. How to write something using set notation is an exceptionally broad question. Bear in mind that descriptions of languages aren't unique: there's more than one way to describe a set and any reasonably concise, unambiguous description will do. $\endgroup$ – David Richerby May 12 '15 at 8:25
2
$\begingroup$

A Turing machine implements an algorithm. The algorithm can be implicit by an explicit definition of the language such as:
$M$ is a TM such that $L(M)=\left \{ x\in \Sigma^* \ | \ |x|\in \mathbb{N}_{even}\right \}$. Which is usually the case.
In other cases, you might have to understand a turing machine based on a state diagram, this will be a simple reverse engineering problem where based on some inputs you understand the algorithm (and then you can prove your assumption).
Generally, there is no fixed approach towards understanding the language a machine accepts.

$\endgroup$
0
$\begingroup$

The problem of identifying the language that is accepted by a Turing machine (using or not some form of set construction notation) does not have a general solution. This means that - with the exception of a minority of trivial cases - you will have to take them one at a time, as separate problems, by logical necessity.

The fact that this question constantly reappears (in different guises) just shows how its answer is counterintuitive. It may be worth noting that Turing proposed the model of computation that carries his name precisely to explore the limits of computation, so this negative result should not be treated as something unexpected, or surprising.

$\endgroup$

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