Turing Machine Time Complexity

1. From Steps to Running Time

At its heart, a Turing Machine is a step-by-step model of computation. To measure how long a TM takes, we need to count these steps.

A "step" corresponds to one application of the TM's transition function, $\delta (q,a)=(q^{\prime },b,D)$, which involves:

1. Reading the symbol on the current tape cell.
2. Changing to a new state.
3. Writing a new symbol on the current tape cell.
4. Moving the tape head left or right.

The total number of these steps a TM takes before it halts (in either an accept or reject state) is its running time.

2. Formalizing Time Complexity

While the idea of counting steps is simple, a formal definition requires care. The number of steps usually depends on the specific input string. A TM might be very fast for some inputs and slower for others, even if they have the same length.

To handle this, we will build our definition in a few stages.

Let's summarize the key definitions from the reading:

1. Running time on an input w: Denoted as $r{t}_M(w)$, this is the total number of steps the TM $M$ performs before halting on the specific input string $w$.

2. Input size n: We want to measure complexity as the input gets larger. By convention, we use the length of the input string, $n=|w|$, as the measure of input size.

3. Worst-Case Analysis: For a given size $n$, there could be many input strings. We are typically interested in the "pessimistic" view: what is the maximum number of steps the machine might take for any input of that size? This is known as worst-case analysis.

This leads us to the central definition:

Definition: Time Complexity of a Turing Machine

Let $M$ be a deterministic Turing Machine that halts on all inputs. The time complexity (or running time) of $M$ is the function $t_M:\mathbb{N}\to \mathbb{N}$, where $t_M(n)$ is the maximum number of steps that $M$ performs on any input word of length $n$.

Formally:
$t_M(n)=\max \{r{t}_M(w)\mid w\in {\Sigma }^{\ast }\text{ and }|w|=n\}$

If a TM has a time complexity of $t_M(n)$, we say it is a $t_M(n)$-time Turing Machine.

3. Asymptotic Analysis and Big-O Notation

Precisely calculating $t_M(n)$ for complex TMs can be tedious, and the exact number might depend on low-level implementation details of the TM model. In computer science, we are usually more interested in how the running time grows as the input size $n$ increases.

Your experience with algorithm analysis in software development is directly applicable here. We use Big-O notation to capture this asymptotic behavior, ignoring constant factors and lower-order terms.

So, instead of saying a TM runs in $3n^2+5n+2$ time, we simplify this and say it runs in $O(n^2)$ time. This tells us the running time grows quadratically with the input size, which is the most important piece of information for large inputs.

When we say a TM $M$ has a running time of $O(f(n))$, it means there exists some function $g(n)\in O(f(n))$ such that the time complexity of $M$, $t_M(n)$, is at most $g(n)$ for all sufficiently large $n$.

4. Example: Analyzing a Palindrome-deciding TM

Let's apply these concepts to a concrete example. Consider a TM that decides the language $L=\{w\mid w\text{ is a palindrome}\}$.

A high-level algorithm for this TM could be:

1. Read the first symbol of the string, cross it out (e.g., write a blank).
2. Scan to the right end of the string.
3. Check if the last symbol matches the one from step 1. If not, reject.
4. If it matches, cross it out.
5. Scan back to the left end of the remaining string.
6. Repeat this process until the string is empty or a mismatch is found.

Let's analyze the time complexity of this algorithm for an input of length $n$.

• One Pass: A single pass involves scanning from left to right ($\approx n$ steps) and then back from right to left ($\approx n$ steps). So, one pass takes $O(n)$ time.
• Number of Passes: In each pass, we eliminate two characters from the string. We need to do this approximately $n/2$ times.

Combining these:
$\text{Total Time}\approx (\text{Number of passes})\times (\text{Time per pass})$
$\text{Total Time}\approx \left(\frac{n}{2}\right)\times O(n)=O(n^2)$

A more detailed analysis would show the first pass takes $\approx 2n$ steps, the second takes $\approx 2(n-2)$, and so on, leading to a sum that is also $O(n^2)$.

Therefore, we say the time complexity of this TM is $O(n^2)$.

Conclusion

Today we laid the essential groundwork for analyzing the efficiency of algorithms within the framework of Turing Machines. This shift from "can it be computed?" to "how long does it take?" is the central theme of complexity theory.

Key Takeaways:

• The time complexity of a TM measures the number of discrete computational steps it takes to halt.
• We standardize this measure by using a worst-case analysis, defining the time complexity for an input size $n$ as the maximum time taken over all possible inputs of that length.
• The formal definition is $t_M(n)={\max }_{|w|=n}\{r{t}_M(w)\}$.
• We use Big-O notation to describe the asymptotic growth of $t_M(n)$, allowing us to compare the efficiency of algorithms in a way that is independent of machine-specific details and constant factors.

Preview of the Next Lesson:
Now that we have a formal tool to measure the time taken by a TM, we can begin to group problems into "complexity classes" based on their resource requirements. In our next lesson, we will define the first and perhaps most important of these classes: P, the class of all decision problems that can be solved by a deterministic Turing Machine in polynomial time. This will be our first step in mapping the landscape of "efficiently solvable" problems.