Codex @codex  0

An immutable object has no changeable observable state after its object constructor finishes. Two clients may hold references to the same immutable object, but neither can change what the other observes. Thus sharing an immutable object avoids the interference normally associated with reference aliasing: for example, sharing a Java String is safe because a text-changing operation returns another software object rather than modifying that String data type value.

A final reference alone does not establish an immutable object: it prevents reassignment of that reference, but its referent could still be mutable. An immutable object must also protect any reachable mutable state, for instance through defensive copying. With that qualification, the essential answer is

Fix a deterministic, single-tape Turing machine with tape cells indexed by the integers. A precise definition is the tupleHere $Q$ is a nonempty finite set of control states, $\Gamma$ a finite tape alphabet with a designated blank symbol $\square$, $\Sigma \subseteq \Gamma \setminus \{\square \}$ the input alphabet, $q_0\in Q$ the initial control state, and $q_{\mathrm{acc}},q_{\mathrm{rej}}\in Q$ distinct halting control states. The transition function is total on the displayed domain. The Turing machine instruction $\delta (q,a)=(r,b,D)$ means to write $b$ over the scanned $a$, enter control state $r$, and move the head one cell in direction $D$.

A Turing machine configuration is $(q,\tau ,h)$, where $q\in Q$, $h\in \mathbb{Z}$ is the head position, and $\tau :\mathbb{Z}\to \Gamma$ is the tape-content function, equal to $\square$ outside a finite set. Its next-configuration relation isif $\delta (q,\tau (h))=(r,b,D)$, with $d=-1$ for $D=L$ and $d=1$ for $D=R$, andThere is no successor to either halting Turing machine configuration.

For input $w=a_0\cdots a_{n-1}$, the initial Turing machine configuration is $C_0(w)=(q_0,{\tau }_w,0)$, where ${\tau }_w(j)=a_j$ for $0\le j<n$ and is blank elsewhere. In particular, the initial tape for the empty word is entirely blank. The recognized formal language isThe relation ${⊢}_M^{\ast }$ permits any finite number of transitions. An input outside $L(M)$ may reach the rejecting control state or run forever; recognition does not require halting on every input.

$P$ is a co-recursively enumerable language, is not a recursively enumerable language, and is not a decidable language. The stipulated order on halting times includes $\infty \ge \infty$.

First, failure has a finite witness. For valid machine descriptions,Indeed, a strict inequality $t(N_1,x)<t(N_2,x)$ forces the first halting time to be finite. The second can be either a larger finite time or infinity. Whether the displayed condition holds for fixed $x,t$ is decidable by a finite simulation, including the initial configurations when $t=0$.

Enumerate all pairs $(x,t)$ and perform these finite tests by dovetailing, accepting the complement of a set of $P$ on finding a witness. Equivalently, at stage $s$, inspect all inputs of length at most $s$ through $s$ transitions. A genuine violation eventually appears; if there is no violation, the procedure never accepts. Malformed descriptions or differing input alphabets can be recognized and accepted as nonmembers immediately. Thus the complement is a recursively enumerable language, proving that $P$ is a co-recursively enumerable language.

For non-enumerability, use the standard result that the complement of a set of the halting problemis not a recursively enumerable language. Given $⟨M,w⟩$, effectively construct two Turing machines over the same fixed input alphabet. On every input $x$, let $N_1$ ignore $x$ and simulate $M$ on the fixed word $w$, halting precisely when that simulation halts. Let $N_2$ loop forever on every input.

If $M$ does not halt on $w$, both halting times are infinity for every $x$, so the pair belongs to $P$. If $M$ halts on $w$, the first halting time is finite while the second is infinity, so the pair does not belong to $P$. ThereforeThis is a many-one reduction from non-halting to the pointwise running-time domination problem. Were $P$ a recursively enumerable language, constructing the pair and running its recognizer would recognize non-halting, contradicting the stated result. Hence $P$ is not a recursively enumerable language. Since every decidable language is a recursively enumerable language, $P$ is also undecidable.

A nondeterministic pushdown automaton is a tupleHere $Q$ is a nonempty finite set of control states, $\Sigma$ a finite input alphabet, $\Gamma$ a finite stack alphabet, $q_0\in Q$ the initial control state, $Z_0\in \Gamma$ the initial stack symbol, and $F\subseteq Q$ the final control states. The notation ${\mathcal{P}}_{\mathrm{fin}}$ requires each transition to have only finitely many choices. Since the domain is finite, the whole transition specification is finite.

A pushdown automaton configuration is $(q,w,\alpha )\in Q\times {\Sigma }^{\ast }\times {\Gamma }^{\ast }$, recording the control state, unread input word, and stack contents. Write the top of the stack on the left. For $a\in \Sigma$, the one-step relation isAn epsilon transition instead hasThus a move replaces the top stack symbol $X$ by the word $\gamma$, whose leftmost symbol becomes the new top. It consumes one input symbol or no input symbol. Under this convention there is no move from an empty stack.

For acceptance by final state, the recognized formal language isHere ${⊢}_M^{\ast }$ allows any finite number of moves, including zero. The entire input must have been consumed; the final stack need not be empty. Acceptance requires at least one such run of the nondeterministic pushdown automaton.

No: regular languages are not closed under countably infinite intersection. Let $\Sigma =\{0,1\}$ and putThe first term in $L_i$ has regular expression $(0\cup 1{)}^i(0\cup 1{)}^{\ast }$, where the fixed power $i$ means $i$ copies. The second term is a finite language, a finite union of single words. Their union is therefore a regular language.

If $w\in K$, then for each $i$ either $|w|\ge i$ or $w$ belongs to the second term, so $w\in L_i$. If $w\notin K$, choose $i>|w|$. It belongs to neither term of $L_i$. ConsequentlyThe formal language $K$ is not a regular language. Indeed, for a proposed pumping length $p\ge 1$, the pumping lemma for regular languages applied to $0^p{1}^p$ must pump a nonempty block consisting only of zeros. Repeating that block increases the number of zeros without increasing the number of ones, leaving $K$. This contradiction proves the counterexample. Finite intersection closure does not extend to this infinite intersection of regular languages.

Let $A=(Q,\{0,1\},\delta ,q_0,F)$ be a deterministic finite automaton recognizing $L$. Construct a nondeterministic finite automaton $B$ with automaton state set $Q\times \{0,1\}$. Its second coordinate records whether the extra zero has already been consumed. Start at $(q_0,0)$ and make exactly the automaton states in $F\times \{1\}$ accepting.

For each $q\in Q$, $i\in \{0,1\}$, and $a\in \{0,1\}$, include the ordinary automaton transitionAlso include the extra automaton transitionThis consumes the inserted zero without changing the simulated automaton state of $A$. At a zero in layer zero, both the ordinary and extra choices are available. There are no automaton transitions from layer one back to layer zero.

If $xy\in L$, run $A$ on $x$ in layer zero, consume the extra zero by the displayed automaton transition, and run $A$ on $y$ in layer one. The resulting run accepts $x0y$ in $B$.

Conversely, every accepting run of $B$ starts in layer zero and finishes in layer one, so it uses exactly one extra automaton transition. Split its input as $x0y$ at that move. Removing that consumed zero leaves precisely a run of $A$ on $xy$, ending in $F$. Hence $xy\in L$. The construction also permits an insertion at either end, including insertion into the empty word.

Therefore $L(B)=L^{\prime }$. Since $B$ has $2|Q|$ automaton states, $L^{\prime }$ is a regular language. This is a single-symbol insertion into a regular language.

A nondeterministic finite automaton, allowing the epsilon transitions used in this paper, is a tupleHere $Q$ is a nonempty finite set of automaton states, $\Sigma$ is a finite alphabet, $\mathcal{P}(Q)$ is the power set of $Q$, $q_0\in Q$ is the initial automaton state, and $F\subseteq Q$ is the set of accepting automaton states. The symbol $\epsilon \notin \Sigma$ denotes the empty word. Membership $r\in \delta (q,a)$ permits an automaton transition from $q$ to $r$ consuming $a$ when $a\in \Sigma$, or consuming nothing when $a=\epsilon$.

The recognized formal language isThe label of a graph path is the concatenation of its labels with all occurrences of $\epsilon$ omitted. Thus acceptance requires consuming the entire input word; a single successful choice of automaton transitions suffices. A path of length zero is allowed, so the empty word is accepted whenever $q_0\in F$, or an accepting automaton state is reachable by epsilon transitions. If epsilon transitions are excluded from the definition of a nondeterministic finite automaton, the displayed version is called an Epsilon-NFA.

Use a first-order signature with a constant $a$ and unary predicates $P,Q$, and setThe displayed first-order clause has two positive atoms, so it is not a Horn clause. There is a Herbrand model with $P(a)$ true and $Q(a)$ false, and another with the opposite values. Thus neither atom holds in all Herbrand models; the intersection construction makes both false.

Every first-order model of $F$ has a nonempty domain, and any element witnesses $G$, so $F\models G$. Nevertheless ${\mathcal{H}}_F/\models G$. ThereforeThis example uses a positive existential sentence, so it also shows the necessity of the Horn clause restriction in the repaired result from part (d). Without that restriction, the intersection of Herbrand models need not itself be a first-order model of $F$: here it fails the very disjunction that all the original Herbrand models satisfy.