# Estimating Algorithmic Information Using Quantum Computing for Genomics Applications
## 2 Background
### Restricted Parallel Universal Linear Bounded Automata  
While Turing machines can express arbitrary computations, their minimalist design makes them unsuitable for algorithm design in practice. Some modifications of the TM result in equivalent computation power, as captured by the Church-Turing thesis. Here, equivalence refers to being within polynomial translation overhead in time or memory resources. These models (such as lambda calculus, Post machine, cyclic-tag system) offer different perspectives in development of computer hardware and software by computing faster, using less memory, or having a smaller instruction set; however, they cannot compute more mathematical functions.  
It is physically not possible for an automata to possess an infinite tape. Thus, experimental realizations of computational models restrict the tape features in various ways, by limiting the size (linear bounded automata), restricting its input-output such as a stack (push-down automata) or not having a memory altogether (finite state automata). We will consider a linear-bounded automata (LBA) with a circular tape. More specifically, we will consider a parallel universal LBA (PULBA) which allows storing the program in the memory, and multiple programs to run in parallel (by dovetailed multi-threading or in quantum superposition).  
Figure 1: Computational model of a Turing machine.  
Figure 2: Computational model of a universal Turing machine.  
For implementing any automata, besides the memory, the runtime also needs to be restricted to a predetermined cycle count cutoff. This is because it is not generally possible to estimate the halting time of a Turing machine (or an LBA) in advance by inspecting a program's structure. Not all applications however allow a time restricted formulation. In our research, we are interested in these specific types of algorithms that can be aborted externally (with or without inspecting the current progress). The premature output yields an acceptable approximate solution with a bounded error based on the computation time. However, our assumptions on the space and time resources are motivated from the application perspectives of biological processes that we intend to model.  
There is no definitive metric to compare the power of tape-restricted TMs besides assigning them to the wide class in the Chomsky hierarchy. Most landmark research [4] on the universality of TMs has assumed infinite tape length, adding a few points on the pareto curve of universality for the number of symbols and states. For restricted TMs, instead of universality, more important metrics are expressibility and reachability. Expressibility is the set of solutions/states that an automaton can compute given a non-universal set of operations but not restricted by memory/space or steps/time resources. Reachability is the set of solutions/states that an automaton can compute by restricting space and/or time resources. For our computational model of a time-bound LBA, the reachability metric will be more suitable, semantically being the set of non-zero probability strings in the universal distribution we empirically obtain.  
In our model, we do not consider halting states (though it is not too difficult to include these too). Recent research [5] showed that a non-halting TM is statistically correlated in rank with LBA. Though the Chomsky hierarchy level of a non-halting LBA has not been explored, we conjecture that it will be correlated to type-1 rather than to type-2/3 in the hierarchy. The findings in [5], establish that more than 60% of algorithmic features, can be empirically tested by output distributions produced by sub-universal computation models, a key component for our research. As discussed later, restricting the TM based on the number of cycles is an unavoidable technicality as we need to collapse the quantum superposition. In the next section, we introduce the algorithmic features that we intend to estimate using our method.