Turing machines

Question 1

What is the most powerful computational model introduced in this course?

Answer 1

The Turing Machine.

Question 2

What are the two components of a Turing Machine?

Answer 2

A head (control unit) and a tape (infinite memory).

Question 3

What can a Turing machine do at each step?

Answer 3

Read a symbol, write a symbol, and move left or right on the tape.

Question 4

What type of memory does a Turing machine use?

Answer 4

An infinite tape of cells storing symbols.

Question 5

What language can a finite automaton not recognize?

Answer 5

L = { aⁿbⁿ | n ≥ 0 }

Question 6

What language can a pushdown automaton not recognize?

Answer 6

L = { aⁿbⁿcⁿ | n ≥ 0 }

Question 7

What language is undecidable by any machine?

Answer 7

The halting problem.

Question 8

What is the formal definition of a Turing machine?

Answer 8

A 6-tuple (Q, Σ, Σ₀, s, δ, H) with states, tape alphabet, input alphabet, start state, transition function, and halting states.

Question 9

What symbols must be included in the tape alphabet of a Turing machine?

Answer 9

▷ (start-of-tape marker) and ⊔ (blank symbol).

Question 10

What are halting states in a Turing machine?

Answer 10

States in which the machine stops executing.

Question 11

Can a Turing machine move left off the tape?

Answer 11

No — it cannot move left from the start-of-tape marker ▷.

Question 12

What is a configuration of a Turing machine?

Answer 12

A 4-part description (q, u, a, v) — current state, left content, current symbol, right content.

Question 13

How is a computation defined in a Turing machine?

Answer 13

A sequence of configurations from the initial to a halting configuration.

Question 14

What does it mean for a Turing machine to accept a word?

Answer 14

It halts on the input in an accepting state.

Question 15

What is a semidecidable language?

Answer 15

A language where the TM halts for all strings in the language but may run forever on others.

Question 16

What is a decidable language?

Answer 16

A language for which a TM halts on all inputs, accepting or rejecting correctly.

Question 17

What is another name for a decidable language?

Answer 17

A recursive or Turing-decidable language.

Question 18

What condition must hold for a language to be decidable?

Answer 18

Both the language and its complement must be semidecidable.

Question 19

What is the Church-Turing Thesis (informally)?

Answer 19

Everything computable by an algorithm can be computed by a Turing machine.

Question 20

What does the Turing machine model provide in theoretical computer science?

Answer 20

A precise definition of computation and computability.

Question 21

What is an algorithm (informally)?

Answer 21

A set of step-by-step rules or instructions for solving a problem.

Question 22

What kind of function does an algorithm define?

Answer 22

A function f : X → Y mapping inputs to outputs.

Question 23

What does it mean for a function to be effectively calculable?

Answer 23

It can be computed by an algorithm.

Question 24

What is a partial function?

Answer 24

A function f : D ⊆ X → Y that is only defined for some inputs in D.

Question 25

How do Turing machines represent partiality?

Answer 25

They halt for defined inputs, and run forever for undefined inputs.

Question 26

When is a function computable?

Answer 26

If it can be implemented by a Turing machine that halts on all inputs in its domain.

Question 27

What is the formal model used to define computable functions?

Answer 27

Turing machines.

Question 28

What is the informal notion of computation?

Answer 28

Effectively calculable using a mechanical algorithm.

Question 29

What is the Church–Turing Thesis?

Answer 29

A function is effectively calculable if and only if it is computable by a Turing machine.

Question 30

Can the Church–Turing Thesis be proven?

Answer 30

No — it's a thesis, not a theorem.

Question 31

What supports the Church–Turing Thesis?

Answer 31

All reasonable models of computation (lambda calculus, μ-recursive functions, etc.) agree with it.

Question 32

What does it mean to describe a Turing machine at a formal level?

Answer 32

You specify all its states, symbols, and transition rules explicitly.

Question 33

What is an implementation-level description of a Turing machine?

Answer 33

A step-by-step description of what the machine does, written in natural language.

Question 34

What is a high-level description of a Turing machine?

Answer 34

A summary of the algorithm or problem-solving approach without tape-level details.

Question 35

Is L = { a^2ⁿ | n ≥ 0 } decidable?

Answer 35

Yes — a TM can systematically mark every other a and verify the count.

Question 36

How can a TM semidecide whether ax = b has a solution?

Answer 36

Try x = 0, 1, -1, 2, -2... until a solution is found; if one is found, halt.

Question 37

How can a TM decide whether ax = b has a solution?

Answer 37

Check if b mod a = 0 using division; if yes, accept; else, reject.

Question 38

What do all effectively calculable functions discovered so far have in common?

Answer 38

They can be implemented on a Turing machine.

Question 39

Why do we consider TMs the standard model of computation?

Answer 39

They are simple yet powerful, and match all intuitive notions of algorithms.

Question 40

What is the significance of alternative models agreeing with Turing machines?

Answer 40

It supports the validity of the Church–Turing Thesis.

Question 41

What is the language L_DFA?

Answer 41

L_DFA = {⟨A, w⟩ | A is a DFA and A accepts w} — it is decidable.

Question 42

What is the language L_NFA?

Answer 42

L_NFA = {⟨A, w⟩ | A is an NFA and A accepts w} — it is decidable.

Question 43

How do we decide if a regular expression accepts a word?

Answer 43

Convert the regex to an NFA, then simulate the NFA.

Question 44

What is L_TM?

Answer 44

L_TM = {⟨M, w⟩ | TM M halts on input w} — the halting problem.

Question 45

Is L_TM decidable?

Answer 45

No — the halting problem is undecidable.

Question 46

Is L_TM semi-decidable?

Answer 46

Yes — if M halts on w, we can simulate it and confirm; otherwise, it may loop forever.

Question 47

What does it mean for a language to be semi-decidable?

Answer 47

A Turing machine halts for positive cases, but may loop forever on negatives.

Question 48

What does it mean for a language to be decidable?

Answer 48

The Turing machine always halts with either accept or reject — you fully understand the problem.

Question 49

What is the distinction between semi-decidable and decidable?

Answer 49

Semi-decidable = computable; Decidable = computable with total understanding (guaranteed termination).

Question 50

What is a universal Turing machine?

Answer 50

A TM that can simulate any other TM on any input ⟨M, w⟩.

Question 51

What is the significance of the universal TM?

Answer 51

It is the theoretical model behind modern general-purpose computers.

Question 52

What is the core question of the halting problem?

Answer 52

Does a given TM halt on a given input?

Question 53

What is the result of the halting problem?

Answer 53

It is undecidable — no TM can always decide halting for all other TMs.

Question 54

What is the idea behind the halting problem proof?

Answer 54

Construct a machine that behaves paradoxically when asked if it halts on itself — leading to contradiction.

Question 55

What kind of paradox does the halting proof resemble?

Answer 55

Russell’s Paradox — self-reference leads to logical contradiction.

Question 56

Why can't we build a tool that always detects infinite loops in programs?

Answer 56

Because that would solve the halting problem, which is impossible.

Question 57

What is Hilbert’s 10th problem?

Answer 57

Determine if a Diophantine equation has an integer solution — proven undecidable.

Question 58

Who proved Hilbert’s 10th problem undecidable?

Answer 58

Davis, Putnam, Robinson, and Matiyasevich in 1970.

Question 59

What real-world implication does the halting problem have?

Answer 59

We cannot build a perfect tool that detects all non-terminating code.