formal languages – Do Turing machines have memory registers?

I am working on chapter one of the textbook Computational Complexity: a modern approach by Arora, S., & Barak, B. They begin by defining a turing machine (TM) and then prove equivalence between variations of TMs. They make the following claim.

Claim 1.6 Define a single-tape Turing machine to be a TM that has only one read-write
tape, that is used as input, work, and output tape. For every $f : {0, 1}^∗ → {0, 1}$ and time-constructible $T : mathbb{N} → mathbb{N}$, if $f$ is computable in time $T(n)$ by a TM $M$ using $k$ tapes, then it is computable in time $5kT(n)^2$ by a single-tape TM $M’$.

I understand how to “compress” the $k$ tapes $M$ has into $M’$ single-tape. However, when they describe how to simulate one step of $M$ on $M’$ I get confused. More specifically, they describe it as follows:

  1. First it sweeps the tape in the left-to-right direction and records to its register the $k$ symbols that are marked by “$ˆ$”.
  2. Then $M’$ uses $M$’s transition function to determine the new state,
    symbols, and head movements and sweeps the tape back in the right-to-left direction
    to update the encoding accordingly.

How can a TM have a register? I thought it was a finite automata with a tape and head only. They also mention TMs having a state register.

How much data can a register hold? In the proof, they imply the register can hold $k$ symbols. Are the registers typically stored on some separate tape or somewhere else?

turing machines – How is it possible that for infinite L in R exists subset L’ which is not in Re?

Subsets of recursive languages aren’t always recursive or recursively enumerable. The simplest example is the language of all strings: it is clearly recursive (even regular), and all languages are its subsets including those not in $RE$.

To solve this question, consider this: how many subsets does an infinite language $L$ have? What does that imply regarding their membership in $RE$?

set theory – How large are the stabilization times of Ordinal Turing Machines with an oracle for the transfinite initial ordinals?

Consider a model of Ordinal Turing Machines (called “$omega_{alpha}$-machines”) with a special oracle that provides a dynamic access to the transfinite initial ordinals.

Any $omega_{alpha}$-machine is an Ordinal Turing Machine equipped with two extra tapes, the oracle input tape and the oracle output tape. Additionally (for convenience), the alphabet is extended to four symbols in the set ${0,1,2,3}$, instead of the usual ${0,1}$.

Let $t(alpha)$ denote the symbol written on an $alpha$-th cell of the oracle input tape at the time when a machine goes into the ASK state.

The oracle operates as follows.

If there are no non-zero symbols written on the oracle input tape (that is, $t(alpha) = 0$ for all $alpha in text{Ord}$), the oracle puts a machine into the NO state and the computation continues. Otherwise, the oracle performs the following five steps in this exact order (obviously, the order of steps here is significant, although it is possible to consider steps 2 and 3 to be a single step):

  1. All non-zero symbols on the oracle output tape are replaced with 0;
  2. For any ordinal $alpha$ such that $t(alpha) = 1$ and $omega_{alpha} ne alpha$, a zero symbol on the $omega_{alpha}$-th cell of the oracle output tape is replaced with $1$;
  3. For any ordinal $alpha$ such that $t(alpha) = 1$ and $omega_{alpha} = alpha$, a zero symbol on the $omega_{alpha+1}$-th cell of the oracle output tape is replaced with $2$;
  4. Assuming that $T(alpha)$ denotes the symbol written on an $alpha$-th cell of the oracle output tape at the time when the result of step 3 is complete, let $beta = sup {alpha : T(alpha) in { 1,2 }}$. Then a zero symbol on the $beta$-th cell of the oracle output tape is replaced with $3$;
  5. The oracle puts a machine into the YES state and the computation continues.

The stabilization time of a machine is the least ordinal $gamma_0$ such that the value of a symbol written on the first cell of the output tape (not the oracle output tape) never changes at any time $gamma > gamma_0$. If a machine halts, then $gamma_0$ is equal to the halting time.

Let $F(i)$ denote the stabilization time of an $i$-th $omega_{alpha}$-machine, assuming that all computations start with no ordinal parameters (i.e. empty input). Here we assume that if a corresponding machine diverges (i.e. does not stabilize), then $F(i) = 0$.

Consider the following two ordinals: $$begin{array}{l}
{tau_0} = sup {F(i) : i in mathbb{N}, F(i) < {omega _1}} ,\
{tau_1} = sup {F(i) : i in mathbb{N}, F(i) ge {omega _1}}.

Is it possible to estimate how large are $tau_0$ and $tau_1$ (at least, give a “reasonably accurate” estimate for the lower/upper bounds)? In particular, is $tau_0$ larger than the least ordinal $delta$ such that $L_{delta} prec_{Sigma_3} L_{omega_1}$ (the latter is mentioned in this comment and this answer on Mathoverflow)?

complexity theory – Resolvable languages on Turing machines

Let some language be resolvable on a Turing machine in memory $f(n)$. Prove that there is another Turing machine that resolves the same language and works on memory that is at most $n + εf (n)$.

Prove a similar statement for computations with time constraints rather than memory constraints. In this problem we use multi-tape machines with arbitrary finite alphabets. Where in the proof is the addition of $n$ to $εf(n)$ required?

algorithms – One-tape Turing machine for doubling words (strings)

I am going to design a Turing machine for doubling any words. My algorithm is such that for word X as input, the output will be in the form X@X which @ is a character. How can design an one-tape Turing machine that give exactly XX as its output? For example, X=abba, XX=abbaabba. Thank you in advance for consideration.

single-tape Turing machine

I am reading an introductory text on Turing machines( and I have some questions. The first one is the following:
Prove that there is a single-tape Turing machine that doubles words of the form $1^n$ (result 1 to the 2n power), and works $O(nlog n)$ clock cycles.
Could you please help me to solve this problem?

turing completeness – Had Conway’s Game of Life been demonstrated to generate non-repeating pattern?

As we know, Conway’s Game of Life is Turin-complete. And Turin-complete systems can be used to calculate irrational numbers such as $sqrt{2}$, $pi$, $e$, etc. which have non-repeating digits.

So it might be natural to reach the conclusion that Conway’s Game of Life can be used to generate non-repeating digit.

To limit the scope of this question and not make it open-ended and opinion-based, I’ll be asking: had there been research on cellular automata generating infinite non-repeating patterns?

turing machines – How to prove that the problem $text{“If $L$ is a context-free language, then, is $overline{L}$ also context-free?”}$ is undecidable?

Lately I came across a problem:

$text{“If $L$ is a context-free language, then, is $overline{L}$ also context-free?”}$

And I need to comment on its decidability. Now I know that context free language is not closed under complementation. Had it been so, then this decision problem would have been trivially decidable. (In the sense that we could design a Turing Machine for this problem and allow it to always answer “YES”.)

Few of peers make a wrong logic behind the problem as follows. They say that the problem below is undecidable since CFLs are not closed under complementation. This logic/reasoning seems utter non-sense to me.

Yet few other peers try commenting about the decidability of the problem using Rice Theorem. They argue as follows:

Let $L$ be set of all CFLs. For this language whether any member’s complement is CFL or not is non trivial property. As CFL are not closed under complement. So According to Rice theorem it is undecidable.

But this above argument also does not convince me. I mean is it correct in the first place? I know the Rice Theorem and it states that :

Any non trivial property of Recursively Enumerable Languages is undecidable.

And my peer probably justifies this argument about Rice Theorem saying that all CFLs are also RE languages. But as far as I know, the “property” talked about in Rice Theorem is a predicate where the universe of discourse is the set of RE languages. Now if I reduce/chop this universe of discourse to contain only CFLs, then would things remain the same? I do not think so, (I might be wrong however.) in the sense that now we are dealing with just a smaller fraction of the entire set. (Like, for instance, the set $mathbb{N}$ is closed under addition, but the set ${1,2,..,10}$ is not.)

To apply Rice Theorem, I would defined the language of the property as:

$$L_p={langle M rangle | text{ L(M) is a context free language and $ overline{L(M)}$ is context free}}$$

Here the language $L_p$ is undecidable, because the property that “a RE language is context free and its complement is context free”, is non-trivial. But this non triviality arises primarily due to the check of RE language being context free. Is the actual decision problem correctly addressed by the $L_p$ above?

Moreover for decidability question I usually try to design a TM machine, but in this decision problem I am having no clue as to how to proceed? If I am given a CFL (using a finite description of course), then how do I design the TM to find the complement of this finite description? Once this complementation is done, we can check whether the language produced is a CFL. (But how?) This is a thought process which I have in my mind, but I cannot proceed.

Or is this decision problem problem much more notorious than it seems to be and do we next level thinking beyond the possible approaches which came to my mind? Please help.

turing machines – Can a non deterministic finite automaton go into infinite loop?

Here is the exact same question but on deterministic finite automaton. The case for deterministic finite automaton is simple. For each state only one transition is possible for each input symbol and quite intuitively one can verify that a DFA shall halt when the input string is exhausted.

Lately I came across a question as :

State true/false:

“Whether a finite state automaton halts on all inputs” is a decidable problem.

I came to the conclusion that the above statement is True, with the following thought process. Be it an $epsilon$-NFA or DFA, every finite automata has an equivalent simplified DFA and hence it is this DFA which is bound to halt on all (finite) input.

Just as I mentioned above about $epsilon$-NFA, I was wondering, that we can have an infinite loop in this finite automaton. Possibly using $epsilon$ transitions as follows:


But the possible loop in the red path in the diagram is harmless (unlike a loop in Turing Machine TM), as it is just a parallel path, which me might not even consider while the parallel processing of the contemporary instances of NFA is going on.

I cannot possibly think of a situation of finite automata where it goes into a situation like TM. Is such a situation at all possible ?