Takayuki Miyadera, Masanori Ohya
Abstract
Open-access reader
We prove that there is no algorithm to tell whether an arbitrarily constructed Quantum Turing Machine has same time steps for different branches of computation. We, hence, cannot avoid the notion of halting to be probabilistic in Quantum Turing Machine.
OpenAlex reports 28 citations for this work. Citation counts describe recorded attention and do not establish research quality.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
We prove that there is no algorithm to tell whether an arbitrarily constructed Quantum Turing Machine has same time steps for different branches of computation. We, hence, cannot avoid the notion of halting to be probabilistic in Quantum Turing Machine.
Key concepts: Turing machine, Description number, Turing machine examples, Probabilistic Turing machine, Quantum Turing machine, Universal Turing machine, Super-recursive algorithm, Non-deterministic Turing machine