Unit6 - Subjective Questions

Definition:
A Turing Machine (TM) is a mathematical model of computation that defines an abstract machine capable of simulating any computer algorithm. It consists of an infinite tape divided into cells, a read/write head, and a finite control mechanism.

7-Tuple Representation:
A TM is formally defined as , where:

• : A finite set of states.
• : A finite set of input symbols (excluding the blank symbol).
• : A finite set of tape symbols, where .
• : The transition function mapping . It determines the next state, the symbol to write, and the direction to move the head (Left or Right).
• : The initial state ().
• : The blank symbol (, but $B
  otin \Sigma$).
• : The set of final or accepting states ().

Turing Machines can be represented in three primary ways:

1. Transition Table: A tabular representation where rows correspond to states, columns to tape symbols, and entries represent the transition .
2. Transition Diagram: A directed graph where nodes are states and edges represent transitions. An edge from state to state labeled with means if the machine reads in state , it writes , moves in direction , and transitions to state .
3. Instantaneous Description (ID):
   An ID provides a snapshot of the Turing Machine's current configuration. It is written as , where:
   • is the current state.
   • is the string of non-blank symbols on the tape.
   • The read/write head is currently scanning the first symbol of .
   • For example, an ID means the machine is in state , the tape contains , and the head is reading . Transitions between IDs are denoted by .

Logic and Design:
The Turing machine will replace 'a' with 'X', 'b' with 'Y', and 'c' with 'Z' in each pass.

Step-by-step algorithm:

1. Start in state . Read 'a', replace it with 'X', move Right, and transition to .
2. In , skip all 'a's and 'Y's by moving Right until 'b' is found. Replace 'b' with 'Y', move Right, transition to .
3. In , skip all 'b's and 'Z's moving Right until 'c' is found. Replace 'c' with 'Z', move Left, transition to .
4. In , move Left skipping 'Z', 'b', 'Y', 'a' until 'X' is found. Move Right, transition back to .
5. In , if 'Y' is read instead of 'a', it means all 'a's are processed. Move Right transitioning to to verify only 'Y's and 'Z's remain.
6. Skip all 'Y's and 'Z's in . If a Blank () is encountered, transition to the final state and accept.

Formal Transitions:

• ,
• ,
• , , ,
• ,
• (Accept)

Linear Bounded Automaton (LBA):
An LBA is a restricted model of a Turing Machine where the tape is not strictly infinite. Instead, the computation is restricted to the portion of the tape containing the input string.

Structural Model:
The tape of an LBA has two special end-marker symbols:

• Left End-marker ( or ): Prevents the read/write head from moving beyond the left end of the input.
• Right End-marker ( or ): Prevents the read/write head from moving beyond the right end of the input.

Differences from Standard TM:

1. Tape length: A standard TM has an infinitely long tape. An LBA has a tape whose usable length is bounded by a linear function of the input length, typically exactly cells (where is the input length).
2. Memory: Standard TM has infinite memory, while LBA has finite, input-dependent memory.
3. Power: Standard TM accepts Recursively Enumerable languages, while LBA strictly accepts Context-Sensitive Languages (CSLs).

Power of LBA:
The computational power of a Linear Bounded Automaton lies strictly between a Pushdown Automaton (PDA) and a standard Turing Machine (TM).

Relation to Chomsky Hierarchy:

• Type 0 (Unrestricted Grammars): Accepted by Turing Machines.
• Type 1 (Context-Sensitive Grammars): Accepted by Linear Bounded Automata.
• Type 2 (Context-Free Grammars): Accepted by Pushdown Automata.

Because an LBA has memory bounded to , it can solve problems that require proportional memory, such as , which a PDA cannot. However, it cannot solve problems requiring an unbounded amount of memory, which a full TM can handle. LBA computations represent the class of Context-Sensitive Languages (CSL).

Variations of Turing Machine:

1. Multi-Tape TM: Has multiple tapes and independent read/write heads. Useful for simplifying complex operations (e.g., copying strings).
2. Multi-Track TM: A single tape is divided into multiple tracks, allowing the head to read/write a tuple of symbols at once.
3. Two-Way Infinite Tape TM: The tape extends infinitely in both left and right directions, unlike the standard semi-infinite tape.
4. Multi-Dimensional TM: The tape is a multi-dimensional grid (e.g., 2D array) instead of a 1D line.
5. Non-Deterministic TM (NDTM): Can have multiple valid next steps for a given state and tape symbol.

Impact on Computational Power:
None of these variations increase the computational power over a standard, single-tape Deterministic Turing Machine. Every variation can be simulated by a standard TM. They only provide convenience in programming and sometimes an improvement in computational efficiency (time/space complexity).

Non-Deterministic Turing Machine (NDTM):
An NDTM is a variation of the TM where the transition function allows for multiple possible moves from a specific state and tape symbol.
Mathematically, returns a set of possible next configurations: . An NDTM accepts an input if at least one sequence of choices leads to an accepting state.

Equivalence with DTM:
Every NDTM can be simulated by a DTM, meaning they possess the exact same computational power.
Simulation Approach:
The execution of an NDTM can be visualized as a tree of configurations. A DTM can simulate the NDTM by exploring this tree using Breadth-First Search (BFS). Using a multi-tape DTM (which is equivalent to a standard DTM):

1. Tape 1 holds the original input.
2. Tape 2 generates and holds sequences of non-deterministic choices (like an address track).
3. Tape 3 acts as the working tape to simulate the NDTM along the specific path generated on Tape 2.
   Since BFS is systematic, if the NDTM has an accepting path, the simulating DTM will eventually find it and accept.

Statement:
The Halting Problem asks whether there exists a general algorithm (Turing Machine) that can determine, for every given TM and input string , whether will eventually halt (accept or reject) on or loop forever.

Proof of Undecidability (By Contradiction):

1. Assume such a machine exists. outputs "Halt" if halts on , and "Loop" if loops on .
2. Construct a new TM, , which uses as a subroutine. takes a TM description as input.
3. asks what does on its own description .
   • If says halts on , deliberately goes into an infinite loop.
   • If says loops on , halts.
4. Now, feed its own description: what happens when evaluating ?
   • If halts, reports "Halt", which causes to loop. (Contradiction)
   • If loops, reports "Loop", which causes to halt. (Contradiction)
5. Conclusion: Since a logical contradiction occurs in all cases, our initial assumption must be false. Therefore, the machine cannot exist. The Halting Problem is undecidable.

Definition:
The Post Correspondence Problem (PCP) is an undecidable decision problem. Given two lists of non-empty strings, and over an alphabet , the problem asks if there exists a sequence of indices (where and ) such that the concatenation of strings from A equals the concatenation of corresponding strings from B:

Example:
Let List A = [, , ] and List B = [, , ].
Let and .
Try the sequence of indices: 3, 2, 1.

• Concatenation from A ():
• Concatenation from B ():
  Since both concatenations yield the same string aabab, this PCP instance has a solution.

Basic Concepts of Computability:
Computability theory studies which problems can be solved by an algorithm or a mechanical process. A function is considered "computable" if there exists an algorithm that can produce the correct output for any valid input in a finite amount of time.

The Church-Turing Thesis:
The Church-Turing Thesis is a foundational hypothesis in computer science. It states that:
"Any mathematically definable function that can be evaluated by human calculation (an intuitive algorithm) can be computed by a Turing Machine."

Significance:

1. It bridges the intuitive notion of "algorithms" with the formal mathematical model of Turing Machines.
2. It implies that if a problem cannot be solved by a Turing Machine, it cannot be solved by any standard digital computer, no matter how powerful.
3. It cannot be mathematically proven (since "intuitive algorithm" is not formally defined), but it is universally accepted because all known formal models of computation (Lambda calculus, Post systems, TM) have been shown to be equivalent.

Decidable Languages (Recursive Languages):
A language is decidable if there exists a Turing Machine that halts on every input string.

• If , halts in an accept state.
• If $w
  otin L$, $M$ halts in a reject state.
• Examples: The language of even numbers, Context-Free Languages, regular languages, .

Undecidable Languages:
A language is undecidable if there is no Turing Machine that can halt and give a correct accept/reject answer for all input strings. The TM might loop infinitely for some inputs.

• Examples:
  1. The Halting Problem (): Determining if a TM halts on a given input.
  2. The Post Correspondence Problem (PCP).
  3. Determining if a Context-Free Grammar generates all possible strings ().

Recursively Enumerable (RE) Language:
A language is Recursively Enumerable (also called Turing-recognizable) if there exists a Turing Machine that:

• Halts and accepts if .
• Either halts and rejects, OR loops infinitely if $w
  otin L$.
  (The machine can enumerate all valid strings of the language, hence "enumerable").

Recursive Language (Decidable Language):
A language is Recursive if there exists a TM that halts on ALL inputs (it never loops infinitely). It halts and accepts if , and halts and rejects if $w
otin L$.

Differences:

1. Halting Guarantee: Recursive languages guarantee halting. RE languages only guarantee halting for strings inside the language.
2. Complement: The complement of a Recursive language is always Recursive. The complement of an RE language is not necessarily RE.
3. Hierarchy: Every Recursive language is also an RE language, but not all RE languages are Recursive (e.g., the Halting Problem is RE but not Recursive).

Computational Complexity measures the amount of resources required by an algorithm to solve a problem based on the input size .

1. Measuring Time Complexity, :
In a Turing Machine, time complexity is defined as the maximum number of state transitions (or steps/moves of the read/write head) the TM makes before halting on an input of length .

• If is a DTM that halts on all inputs, its time complexity is .
• It is usually expressed using Big-O notation, e.g., .

2. Measuring Space Complexity, :
Space complexity is defined as the maximum number of distinct tape cells scanned (visited) by the read/write head of the TM during its computation on an input of length .

• Like time complexity, it considers the worst-case scenario and is expressed in Big-O notation.
• Note that because the head can scan at most one new cell per step.

Complexity Classes:

1. P (Polynomial Time):
   The class of decision problems that can be solved by a Deterministic Turing Machine (DTM) in polynomial time, . These are considered "tractable" or practically solvable. Example: Sorting, Shortest Path.

2. NP (Non-Deterministic Polynomial Time):
   The class of decision problems solvable by a Non-Deterministic Turing Machine (NDTM) in polynomial time. Alternatively, if the answer is "yes", there exists a certificate that a DTM can verify in polynomial time. Example: Traveling Salesperson Problem (decision version).

3. NP-Hard:
   A problem is NP-Hard if every problem in NP can be reduced to in polynomial time. These are at least as hard as the hardest problems in NP. NP-Hard problems do not have to be in NP (they may be undecidable, like the Halting Problem).

4. NP-Complete (NPC):
   A problem is NP-Complete if it is both in NP AND NP-Hard. These are the hardest problems within NP. If a polynomial-time algorithm is found for any NPC problem, then P = NP. Example: Boolean Satisfiability Problem (SAT).

Cellular Automaton (CA):
A Cellular Automaton is a discrete model of computation studied in automata theory. It consists of a regular grid of "cells", each of which can be in one of a finite number of states (e.g., On/Off, 0/1).

Basic Structure & Rules:

1. Grid: Can be 1D, 2D (like Conway's Game of Life), or higher dimensions.
2. Neighborhood: The cells adjacent to a target cell (e.g., left and right neighbors in 1D).
3. Transitions (Rules): Time progresses in discrete steps. The new state of a cell at time is determined by a fixed rule based on its own state and the states of its neighborhood at time .

Relationship with Turing Machines:
Despite their simplicity, certain Cellular Automata are computationally universal, meaning they are Turing Complete. They can simulate any Turing Machine. For example, Stephen Wolfram's Rule 110 (a 1D cellular automaton) and Conway's Game of Life (2D) have been proven to have the same computational power as a Universal Turing Machine.

Logic for Unary Addition:
The input is zeroes, followed by a '1' (separator), followed by zeroes. To get zeroes, we simply need to replace the '1' with a '0', and then remove one '0' from the end of the string.

Step-by-step Design:

1. State : Start at the leftmost '0'. Move Right until you find the '1'.
   • (Replace '1' with '0')
2. State : Continue moving Right to the end of the string.
   • (Found the blank after the last '0', move Left to the last '0')
3. State : Replace the last '0' with a Blank () to account for the extra '0' created by replacing '1'.
   • (Replace '0' with , transition to final state)

The TM halts in with exactly on the tape.

Universal Turing Machine (UTM):
A standard Turing Machine is "hard-wired" to compute a single specific task (e.g., addition or accepting a specific language). A Universal Turing Machine (UTM), denoted as , is a specialized TM that can simulate the behavior of any other Turing Machine .

How it works:
The UTM takes two inputs on its tape:

1. The description of a TM (): Encoded as a binary string , which details 's states, alphabet, and transition rules.
2. The input string (): The data that is supposed to process.

The UTM reads and , and executes 's logic on . accepts, rejects, or loops exactly as would.

General-Purpose Computer Analogy:
The UTM is the theoretical foundation of modern stored-program computers (Von Neumann architecture). Just as a PC can run different software applications (encoded TMs) on various files (input data) without needing hardware changes, the UTM reads an algorithm and input from memory and executes it.

Concept of Reduction:
In computability, reduction is a way of converting one problem into another. A problem is reducible to problem (denoted ) if there exists a computable function such that for every input , if and only if .
This implies that if we have a Turing Machine to solve , we can use it to solve by first transforming the input using .

Proving Undecidability:
Reduction is the primary technique used to prove new problems are undecidable. The logic relies on contradiction:

1. Suppose we know problem (like the Halting Problem) is strictly undecidable.
2. We want to prove problem is undecidable.
3. We show how to reduce to ().
4. If were decidable, we could solve by converting 's input to 's format and using 's decider.
5. Since we know is undecidable, a decider for cannot exist. Therefore, must also be undecidable.

Space Complexity Classes:

• PSPACE: The class of decision problems that can be solved by a Deterministic Turing Machine using a polynomial amount of memory space, , regardless of how much time it takes.
• NPSPACE: The class of decision problems that can be solved by a Non-Deterministic Turing Machine (NDTM) using a polynomial amount of memory space.

Savitch's Theorem:
Savitch's Theorem states that for any function , if a problem can be solved by an NDTM in space, it can also be solved by a DTM in space.
Mathematically: .

Significance:
By applying this theorem to polynomial space functions, if is a polynomial, then is also a polynomial. Therefore, PSPACE = NPSPACE. This is a profound result because, unlike time complexity where it is heavily suspected that P $
eq$ NP, non-determinism does not increase the class of problems solvable within polynomial space.

Modified Post Correspondence Problem (MPCP):
MPCP is a variation of the standard Post Correspondence Problem. Given two lists of strings and , MPCP asks if there exists a sequence of indices such that:

Difference from Standard PCP:
The crucial difference is that in MPCP, the solution sequence must start with the first pair of strings from the lists. The standard PCP allows the sequence to start with any index pair.

Role in Computability Theory:
The MPCP serves as an intermediate stepping stone in proofs of undecidability. Because of the forced starting condition, it is easier to reduce the Turing Machine Halting Problem directly to MPCP. Once MPCP is proven undecidable, it is then relatively straightforward to reduce MPCP to the standard PCP, thereby proving that the standard PCP is also undecidable.