Course contentsShow
← Computer Science
Lesson 1859 of 2,87242. Turing Machines and ComputabilityFree lesson

Languages Recognized by Turing Machines

Define a Turing-recognizable language as the set of strings accepted by some Turing Machine.

Languages Recognized by Turing Machines

You'll learn: How to formally define the set of strings that a Turing Machine can accept as a language.

The Core Idea

Just like DFAs and PDAs recognize certain classes of languages (regular and context-free), Turing Machines also recognize languages—but potentially much more complex ones. A Turing-recognizable language (also called recursively enumerable) is simply the set of all strings that some Turing Machine accepts.

Think of it this way: if you have a Turing Machine M, the language of M, written L(M), is the collection of every input string that causes M to eventually reach an accepting state and halt.

Formal Definition

For a Turing Machine M:

L(M) = { w | M accepts w }

This means: L(M) contains exactly those strings w where M, when started with w on its tape, transitions through states and eventually enters an accepting state.

What Makes This Different?

Unlike DFAs and PDAs, Turing Machines don't always halt. A machine might:

  • Accept a string (halt in accepting state) → string is in L(M)
  • Reject a string (halt in rejecting state) → string is not in L(M)
  • Loop forever on a string → string is not in L(M)

The language only includes strings the machine accepts. If M loops forever on input w, then w ∉ L(M), even though M never explicitly rejected it.

Key Takeaway: A Turing-recognizable language is the set of all strings accepted by some Turing Machine; these languages represent the outer boundary of what can be computationally recognized, though not necessarily decided.