1.
The Basic Model for Turing Machines (TM)
What Is a Turing Machine?
A Turing machine is a mathematical model of computation that defines an abstract,
idealized computer. It's the most powerful of the basic automata, capable of performing
any computation that can be described algorithmically. [1][2]
Key Components of a Turing Machine
A Turing machine consists of:
An infinite tape: Imagine a long strip of paper divided into cells. Each cell holds a
symbol from a finite alphabet (like 0, 1, or blank). The tape acts as the memory.
A tape head: This moves left or right one cell at a time, reads the current tape
symbol, and can overwrite it.
A state register: Keeps track of the machine's current state.
A finite set of rules (transition function): These determine what the machine
does, based only on its current state and what the tape head sees.
Formal 7-Tuple Definition
A Turing machine is defined formally as a 7-tuple:
M =(Q , Γ ,b , Σ , δ , q 0 , F)
where:
Q : Set of states
Γ : Tape alphabet (includes special blank symbol b )
Σ : Input alphabet (subset of Γ , not including blank)
b : The blank symbol
δ : The transition function
q 0: The initial (start) state
F : Set of accepting (final) states[1]
How Does a TM Operate?
At each step:
1. The machine is in some state q .
2. It reads the symbol s under the head.
3. It looks up (q , s) in its transition table.
4. Based on the rule, it:
o Writes a symbol (may overwrite s),
o Changes to a new state q ' ,
o Moves the head left (L) or right (R).
5. If no rule applies, the machine halts (stops running).
Diagramming the Process
It's helpful to visualize the TM as a tape with a read/write head that can move left or
right, changing its internal state as instructed.
2. Turing-Recognizable and Turing-Decidable Languages
These two classes of languages are central to computability:
A. Turing-Recognizable (Recursively Enumerable, RE) Languages
A language is Turing-recognizable (or recursively enumerable, RE) if there
exists a TM that will accept and halt on every string in the language. For strings not
in the language, the machine may either reject or loop forever.
Think: If a string belongs, the TM will eventually accept it; otherwise, it might run
forever with no answer.[3][4]
Intuitive Example:
Suppose a TM is checking for palindromes. If you feed it a valid palindrome, it will
eventually recognize it and accept. But for non-palindromes, it might keep searching
indefinitely, never confirming non-membership conclusively.
Key Points:
Not every RE language has a TM that halts on all inputs.
Every recursive (decidable) language is also RE, but not all RE languages are
recursive.
B. Turing-Decidable (Recursive) Languages
A language is Turing-decidable (or recursive) if there is a TM that always halts—
accepting if the string is in the language and rejecting if not.
This means: For every string, the machine gives a YES or NO answer in finite
time.
Example:
Consider the language of all strings with an equal number of a's and b's. It's possible to
design a TM that always halts and correctly decides whether a specific string meets this
property.
Relationship:
Every recursive language is RE, but there are RE languages that are not recursive
(because the TM might loop forever on some inputs). [4][3]
3. Differences Between RE and Recursive Languages
Property Turing-Recognizable Turing-Decidable
(RE) (Recursive)
Alternate Names Recursively Enumerable Recursive
(RE)
Machine Outcome (in TM halts and accepts TM halts and accepts
L)
Machine Outcome TM may loop forever TM halts and rejects
(not L)
Always Halts? No Yes
Always Decides? No Yes
4. Closure Properties
Closure properties tell us about the behavior of these languages under operations like
union, intersection, complementation, concatenation, and star (Kleene closure).
A. Closure Properties of Recursive (Decidable) Languages
Recursive languages are closed under most operations. That means, applying the
operation to recursive languages gives another recursive language.
Union: If L1 and L2 are recursive, so is L1 ∪ L2.
Intersection: If both are recursive, so is L1 ∩ L2 .
Complement: If L is recursive, so is its complement.
Concatenation: L1 L2={xy ∣ x ∈ L1 , y ∈ L2 } is recursive.
¿
Kleene Star: L (all finite concatenations of strings from L) is recursive.
Reason: Since the machine always halts and decides, we can build combined machines
that always halt.[5][3]
B. Closure Properties of Recursively Enumerable (RE) Languages
RE languages are closed under some but not all basic operations.
Union: Closed. L1 ∪ L2 is RE if both L1 , L2 are RE.
Intersection: Closed. L1 ∩ L2 is RE.
Concatenation: Closed.
Kleene Star: Closed.
Complement: Not closed. The complement of an RE language may not be RE.
Why Not Complement?
There are RE languages whose complements are not RE. This happens because, for
strings not in the language, a TM might loop forever and never reject, so you can't always
"recognize" non-membership effectively.[4][5]
Examples
Let L be RE and its complement L not RE. Then, L is not recursive.
If both L and L are RE, then L is recursive. So, recursive languages are exactly
those where both a language and its complement are RE.
C. Closure Properties Table
Operation Recursive RE (Recursively
(Decidable) Enumerable)
Union Yes Yes
Intersection Yes Yes
Complemen Yes No
t
Concatenati Yes Yes
on
Kleene Star Yes Yes
5. Summary Table and Mnemonics
Language Class Machine Type Acceptance Always Closure Under
Condition Halts? Complement?
RE (T- TM may loop on Accept if in No No
recognizable) nonmembers language
Recursive (T- TM always halts Accept if in, Yes Yes
decidable) reject if out
Mnemonic:
Remember that Recursively Enumerable = Recognizable = Machine accepts members,
but may never finish on nonmembers. Recursive = Decidable = Machine always finishes
(accepts or rejects).
Quick Review Questions
1. What is a Turing machine?
2. How are recursive and RE languages different?
3. What operations are recursive languages closed under?
4. Is the complement of every RE language also RE?
Try answering these for active recall!
6. Illustrative Examples
Example 1: Palindromes (RE but not Recursive)
A Turing machine can check for palindromes by brute force (guess the midpoint,
compare). If it's a palindrome, it halts and accepts. If not, the machine might loop
(especially if it can never find a valid midpoint). This language is RE, but unless an
efficient halting procedure exists, it may not be recursive.
Example 2: Equal Numbers of a, b, and c (Recursive)
The language L={an bn c n ∣n ≥1 } is recursive. It's possible to design a TM that will always
halt with accept or reject, so it's both RE and recursive.
7. Common Misconceptions Clarified
Not all Turing machines decide a language. Some only recognize.
"Recognizable" is not the same as "decidable". Recognizable means the TM
can say "yes" but not always "no"; decidable means it always says either "yes" or
"no," halting in both cases.
Closure properties are not the same for all language classes. For exams,
memorize that recursive languages are closed under complement, but RE languages
are not.
8. Visual Diagram (Conceptual)
Imagine this as a Venn diagram:
The set of all RE languages is the big circle.
The recursive languages are a smaller circle inside RE, where the machine always
halts.
There are RE languages outside this inner circle—they're recognizable but not
decidable.
The complement of an RE language may not be RE, forming a contrasting shape
outside.
9. How to Remember the Key Points
Recursive = TM always halts (decides every string)
RE = TM may halt only to accept (recognizes members)
Recursive languages = closed under union, intersection, complement,
concatenation, star
RE languages = closed under union, intersection, concatenation, star—not
complement
If both L and its complement are RE ⇒ L is recursive
Next Steps
Practice constructing simple Turing machines for various languages, and check whether
your design always halts (recursive) or might run forever (RE only). Review closure
properties by making example languages and testing the effect of union, intersection,
and complement.
If you’re ready, let’s try a few practice definitions or proofs, or test yourself with some
questions on these key points!