Complexity Analysis

A very common reason for teaching Turing machines is to give an introduction to complexity analysis. Varphi provides a mechanism for determining both the time and space complexity of a Turing machine.

To analyze the complexity of a Turing machine, pass the -c, or --complexity, option to the Varphi Interpreter. For example, below we show a session where the complexity of a machine that multiplies a number by two is computed on various input tapes:

$ <PATH TO vpi> -c multiplicationByTwo.vp
Input Tape: 1
Output Tape: 1100
Number of Steps: 11
Number of Tape Cells Accessed: 4

$ <PATH TO vpi> -c multiplicationByTwo.vp
Input Tape: 11
Output Tape: 111100
Number of Steps: 21
Number of Tape Cells Accessed: 6

$ <PATH TO vpi> -c multiplicationByTwo.vp
Input Tape: 111
Output Tape: 11111100
Number of Steps: 35
Number of Tape Cells Accessed: 8

$ <PATH TO vpi> -c multiplicationByTwo.vp
Input Tape: 1111
Output Tape: 1111111100
Number of Steps: 53
Number of Tape Cells Accessed: 10

$ <PATH TO vpi> -c multiplicationByTwo.vp
Input Tape: 11111
Output Tape: 111111111100
Number of Steps: 75
Number of Tape Cells Accessed: 12

$ <PATH TO vpi> -c multiplicationByTwo.vp
Input Tape: 111111
Output Tape: 11111111111100
Number of Steps: 101
Number of Tape Cells Accessed: 14

Notice that if the -c or --complexity option is specified, prompts asking for the input tape will automatically appear.

If you do the math, you will see that the time-complexity of this machine is quadratic in nature, and follows the following quadratic equation (where $n$ is the length of the input tape):

$$f(n)=2n ^2 +4n+5$$

Therefore, we can conclude that the runtime complexity (both best- and worst-case) is $\Theta(n^2)$ for this Turing machine.

On the other hand, the space-complexity of this machine is linear in nature, and follows the following linear equation (where $n$ is the length of the input tape):

$$f(n)=2n+2$$

Therefore, we can conclude that the space complexity (both best- and worst-case) is $\Theta(n)$ for this Turing machine.