Turing machines — formal definition, computation, configurations: Question bank

Before we start, three symbols this page leans on, restated in plain words so nothing is assumed:

$⊔$ is the blank — the "nothing here" symbol that fills the infinite tape beyond your finite input.
$δ$ is the transition function — the rulebook that, given (current state, symbol under head), tells you (new state, symbol to write, direction to step).
$L (M)$ is the ==language of $M$ == — the set of all inputs the machine eventually accepts.

True or false — justify

A TM must read its entire input before deciding.

False. Unlike a DFA, a TM halts the instant it enters

q_{accept}

q_{reject}

— it can accept after seeing one symbol and never look at the rest.

Every TM halts on every input.

False. Only deciders always halt; a general recognizer may loop forever on non-members, which is exactly the gap that makes the Halting Problem undecidable.

L (M)

is Turing-recognizable then it is decidable.

False. Recognizable only promises "yes eventually" for members; decidable also promises "no" for non-members. Deciders are a strict subclass.

Σ = Γ

for a well-formed TM.

False. We require

Σ \subseteq Γ

but almost always

Σ ⊊ Γ

, because

⊔ \in Γ ∖ Σ

and the machine usually needs extra marker symbols too.

The blank symbol

⊔

may appear in an input string.

False. By definition

⊔ \in / Σ

, so no input contains it — that is precisely how the machine tells "real input" from "empty tape".

A TM can have

q_{accept} = q_{reject}

to save states.

False. The definition demands

q_{accept} \neq = q_{reject}

; otherwise "halt" would carry no yes/no information at all.

One application of

δ

can write to the tape without moving the head.

False in this model. Every

δ

output includes a direction in

{L, R}

, so each step both overwrites and moves exactly one cell — there is no "stay" option.

Moving left at cell 0 crashes the machine.

False. By convention the head simply stays at cell 0 and the computation continues; there is no out-of-bounds error like in an array.

If a TM never enters

q_{reject}

, then it accepts every input.

False. It may still loop forever on some inputs, which is neither accepting nor rejecting — looping is a third outcome.

The class of languages a nondeterministic TM recognizes is larger than what a deterministic TM recognizes.

False. They recognize exactly the same class; nondeterminism only affects convenience and time, not raw computational power (by simulation).

A multitape TM can compute something a single-tape TM cannot.

False. Multitape machines are equivalent in power; the extra tapes give speed, not new decidability — consistent with the Church-Turing Thesis.

Every TM's language

L (M)

is decidable.

False.

L (M)

is always recognizable (that is its definition), but it is decidable only when some machine recognizes it and halts on all inputs.

Spot the error

"The start configuration on input

w

q_{0} ⊔ w

, since the tape starts blank."

Error: the start configuration is

q_{0} w

with the head on the first symbol of $w$ , not on a leading blank. Blanks only fill the tape beyond the finite input.

δ (q, a) = (r, b, R)

turns

u a q b v

into

u a q c v

Error: the state should change to

r

and the new symbol

c

joins the left part after moving right, giving

u a c r v

. The old

b

is overwritten, not kept.

"After a left move

u a q b v ⊢ u r a c v

: the head now reads

c

Error: after stepping left the head lands on

a

, so

a

is the new head symbol;

c

(what we wrote over

b

) sits to its right. The head reads

a

, not

c

"A configuration

u q v

records the whole infinite tape, so

v

must list every trailing blank."

Error:

v

is finite; everything beyond

v

is understood to be blanks by convention, so we never write them out.

"If

v

is empty in

u q

, the machine is stuck because there's no symbol to read."

Error: an empty right part means the head is over a blank, so we treat it as

q ⊔

and apply

δ (q, ⊔)

normally.

{0^{2^{n}}}

is recognized by crossing off the first 0 each pass."

Error: the algorithm crosses off every other 0 so each pass halves the count; crossing off just one would only subtract one and never test the power-of-two property.

"Since

q_{accept}

and

q_{reject}

are halting states,

δ

must be defined on them too."

Error: halting states have no outgoing transitions — reaching them stops the machine, so

δ

need not (and conceptually cannot) act on them.

Why questions

Why split

Σ

from

Γ

instead of using one alphabet?

Because the machine needs private working symbols (markers like

X

#

, and the blank

⊔

) that must never be mistaken for legitimate input characters.

Why do we need the blank symbol at all?

The tape is infinite but input is finite;

⊔

marks where real data ends so the head can detect the right boundary of the input.

Why bundle state, tape, and head position into a single "configuration"?

Because those three items completely determine the machine's entire future, so one configuration is a full snapshot — computation becomes a clean sequence

C_{0} ⊢ C_{1} ⊢ \dots

Why does "recognize" only promise an answer for members, not non-members?

Because a recognizer may loop forever on a non-member; it can eventually say "yes" but has no obligation ever to say "no".

Why is the accept/reject split more powerful than a DFA's accepting states?

The two halting states let a TM stop and commit the moment it decides, mid-input if it likes, whereas a DFA must consume the whole string before its final-state check.

Why does giving a TM two tapes not increase what it can compute?

A single tape can simulate multiple tapes by interleaving their contents and tracking head positions with markers, so the set of decidable/recognizable languages is unchanged — only running time differs.

Edge cases

What is the language of a TM that immediately enters

q_{reject}

on the start state for all inputs?

The empty language

\emptyset

: it accepts nothing, yet it is a perfectly valid decider (it always halts).

What happens on the empty input string

ε

The start configuration is just

q_{0}

(empty left and right parts), so the head reads a blank and the machine applies

δ (q_{0}, ⊔)

Is a TM that loops on every input a decider?

No. A decider must halt on all inputs; a machine that never halts recognizes

\emptyset

but is not a decider.

Can a TM whose

δ

is undefined on some (state, symbol) pair still be valid?

In the strict total-

δ

convention it should route missing cases to

q_{reject}

; an undefined transition is treated as an implicit rejection so the machine still halts cleanly.

What does the trace

q_{0} 00 ⊢ 0 q_{0} 0 ⊢ 00 q_{0} ⊢ 00 q_{accept}

show at the last step?

The right part became empty, so the head read a blank;

δ (q_{0}, ⊔)

sent it to the accept state — the machine halts having walked off the end of the input.

If a TM sits at cell 0 and

δ

says move

L

, what is the next head position?

Still cell 0. The left-edge convention keeps the head in place while state and written symbol update normally.

Recall Quick self-test

The single sharpest line to remember ::: Recognizable = "yes eventually"; decidable = "yes or no, always" — the whole theory of the Halting Problem lives in that difference.