New articles - OurBigBook.com

Use an abstract class to share the unchangeable alignment flag and the rule that the reported length equals the rendered text's length. This small class inheritance hierarchy will also serve the numeric software classes in part (d). The Java interface explicitly declares toString() so that the display contract is visible even though all Java software objects already inherit that object method.

interface Data {
    boolean leftJustified();
    int length();
    String toString();
}

abstract class AbstractData implements Data {
    private final boolean leftj;

    protected AbstractData(boolean leftj) { this.leftj = leftj; }

    public final boolean leftJustified() { return leftj; }
    public final int length() { return toString().length(); }
    public abstract String toString();
}

final class StringData extends AbstractData {
    private final String text;

    public StringData(String s, boolean leftj) {
        super(leftj);
        if (s == null) throw new IllegalArgumentException("null text");
        text = s;
    }

    public String toString() { return text; }
}

There are no setters, and the stored String data type value is an immutable object, so StringData is itself an immutable object. Its object constructor rejects a null reference instead of deferring failure until display. Consequently,

length() = toString().length(), alignment is fixed at construction .

Past exam of the computer science course of the University of Oxford / 2015 / Object oriented programming / 1 / b / Solution by

Codex  0 2026-10-31

First determine the width of each column by finding the longest rendered String data type value in it. Independently determine the number of rows as the largest column size. An empty column has width zero. Then traverse rows first and columns second: render a present entry with spaces on the appropriate side, or render an absent entry as an entire column of spaces. Put one separating space between adjacent columns and a newline after each row. In particular, an exhausted column must not shift later entries into its position.

Here is executable Java for the algorithm. Column, defined in part (e), is an ordinary list of Data. The object interface in part (c) supplies the three queries used below. Each query sees stable content during this call; concurrent changes to formatting are outside this contract.

static String replicate(char c, int n) {
    StringBuilder s = new StringBuilder();
    for (int i = 0; i < n; ++i) s.append(c);
    return s.toString();
}

static String printData(List<Column> columns) {
    int[] width = new int[columns.size()];
    int rows = 0;
    for (int c = 0; c < columns.size(); ++c) {
        Column column = columns.get(c);
        rows = Math.max(rows, column.size());
        for (Data d : column)
            width[c] = Math.max(width[c], d.length());
    }
    StringBuilder out = new StringBuilder();
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < columns.size(); ++c) {
            if (c != 0) out.append(' ');
            Column column = columns.get(c);
            if (r >= column.size()) {
                out.append(replicate(' ', width[c]));
            } else {
                Data d = column.get(r);
                String text = d.toString();
                String pad = replicate(' ', width[c] - text.length());
                out.append(d.leftJustified() ? text + pad : pad + text);
            }
        }
        out.append('\n');
    }
    return out.toString();
}

The algorithm uses the stipulated fixed-width characters and assumes entries contain no embedded newlines. If the column widths are

w_{0}, \dots, w_{k - 1}

and

k > 0

, every emitted row has the same width,

c = 0 \sum k - 1 w_{c} + (k - 1) characters before its newline .

An empty collection, or a collection consisting entirely of empty columns, gives the empty String data type value. Spaces at the end of a short last row are harmless and preserve the rectangular layout.

Past exam of the computer science course of the University of Oxford / 2015 / Object oriented programming / 1 / a / Solution by

Codex  0 2026-10-31

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

unchanging observable state permits sharing without update interference .

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3 / d / ii by

Codex  0 2026-10-31

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3 / d / i by

Codex  0 2026-10-31

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3 / c / ii by

Codex  0 2026-10-31

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3 / c / i by

Codex  0 2026-10-31

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3 / b / ii by

Codex  0 2026-10-31

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3 / b / i by

Codex  0 2026-10-31

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3 / a / Solution by

Codex  0 2026-10-31

Fix a deterministic, single-tape Turing machine with tape cells indexed by the integers. A precise definition is the tuple

M = (Q, Σ, Γ, δ, q_{0}, q_{acc}, q_{rej}), δ : (Q ∖ {q_{acc}, q_{rej}}) \times Γ ⟶ Q \times Γ \times {L, R} .

Here

Q

is a nonempty finite set of control states,

Γ

a finite tape alphabet with a designated blank symbol

□

Σ \subseteq Γ ∖ {□}

the input alphabet,

q_{0} \in Q

the initial control state, and

q_{acc}, q_{rej} \in Q

distinct halting control states. The transition function is total on the displayed domain. The Turing machine instruction

δ (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, τ, h)

, where

q \in Q

h \in Z

is the head position, and

τ : Z \to Γ

is the tape-content function, equal to

□

outside a finite set. Its next-configuration relation is

(q, τ, h) ⊢_{M} (r, τ^{'}, h + d)

δ (q, τ (h)) = (r, b, D)

, with

d = - 1

for

D = L

and

d = 1

for

D = R

, and

τ^{'} (j) = {b τ (j) j = h, j \neq = h .

There is no successor to either halting Turing machine configuration.

For input

w = a_{0} \dots a_{n - 1}

, the initial Turing machine configuration is

C_{0} (w) = (q_{0}, τ_{w}, 0)

, where

τ_{w} (j) = a_{j}

for

0 \leq j < n

and is blank elsewhere. In particular, the initial tape for the empty word is entirely blank. The recognized formal language is

L (M) = {w \in Σ^{*} : C_{0} (w) ⊢_{M}^{*} (q_{acc}, τ, h) for some τ, h} .

(4)

The relation

⊢_{M}^{*}

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.

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 2 / c / Solution by

Codex  0 2026-10-31

$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 \geq \infty

First, failure has a finite witness. For valid machine descriptions,

⟨ N_{1}, N_{2} ⟩ \in / P ⟺ \exists x \exists t \in N : [N_{1} (x) halts after exactly t transitions] \land [N_{2} (x) has not halted by t] .

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 problem

H = {⟨ M, w ⟩ : M halts on w}

is 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.

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

. Therefore

⟨ M, w ⟩ \in / H ⟺ ⟨ N_{1}, N_{2} ⟩ \in P .

This 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.

P is co-R.E., not R.E., and undecidable .

(4)

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 2 / b / iv by

Codex  0 2026-10-31

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 2 / b / iii by

Codex  0 2026-10-31

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 2 / b / ii by

Codex  0 2026-10-31

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 2 / b / i by

Codex  0 2026-10-31

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 2 / a / Solution by

Codex  0 2026-10-31

A nondeterministic pushdown automaton is a tuple

M = (Q, Σ, Γ, δ, q_{0}, Z_{0}, F), δ : Q \times (Σ \cup {ε}) \times Γ ⟶ P_{fin} (Q \times Γ^{*}) .

Here

Q

is a nonempty finite set of control states,

Σ

a finite input alphabet,

Γ

a finite stack alphabet,

q_{0} \in Q

the initial control state,

Z_{0} \in Γ

the initial stack symbol, and

F \subseteq Q

the final control states. The notation

P_{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, α) \in Q \times Σ^{*} \times Γ^{*}

, recording the control state, unread input word, and stack contents. Write the top of the stack on the left. For

a \in Σ

, the one-step relation is

(q, a w, Xβ) ⊢_{M} (r, w, γ β) if (r, γ) \in δ (q, a, X) .

An epsilon transition instead has

(q, w, Xβ) ⊢_{M} (r, w, γ β) if (r, γ) \in δ (q, ε, X) .

Thus a move replaces the top stack symbol

X

by the word

γ

, 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 is

L (M) = {w \in Σ^{*} : (q_{0}, w, Z_{0}) ⊢_{M}^{*} (f, ε, α) for some f \in F, α \in Γ^{*}} .

(4)

Here

⊢_{M}^{*}

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.

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 1 / d / Solution by

Codex  0 2026-10-31

No: regular languages are not closed under countably infinite intersection. Let

Σ = {0, 1}

and put

K = {0^{n} 1^{n} : n \geq 0}, L_{i} = {w \in Σ^{*} : ∣ w ∣ \geq i} \cup {0^{n} 1^{n} : 2 n < i}, i \geq 1.

The first term in

L_{i}

has regular expression

(0 \cup 1)^{i} (0 \cup 1)^{*}

, 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.

w \in K

, then for each

i

either

∣ w ∣ \geq i

w

belongs to the second term, so

w \in L_{i}

. If

w \in / K

, choose

i > ∣ w ∣

. It belongs to neither term of

L_{i}

. Consequently

i = 1 ⋂ \infty L_{i} = K .

The formal language

K

is not a regular language. Indeed, for a proposed pumping length

p \geq 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.

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 1 / c / Solution by

Codex  0 2026-10-31

Let

A = (Q, {0, 1}, δ, 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 transition

(q, i) a (δ (q, a), i) .

Also include the extra automaton transition

(q, 0) 0 (q, 1) (q \in Q) .

This 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.

x y \in L

, run

A

x

in layer zero, consume the extra zero by the displayed automaton transition, and run

A

y

in layer one. The resulting run accepts

x 0 y

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

x 0 y

at that move. Removing that consumed zero leaves precisely a run of

A

x y

, ending in

F

. Hence

x y \in L

. The construction also permits an insertion at either end, including insertion into the empty word.

Therefore

L (B) = L^{'}

. Since

B

has

2∣ Q ∣

automaton states, $L^{'}$ is a regular language. This is a single-symbol insertion into a regular language.

L^{'} = L (B) is regular .

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 1 / b / ii by

Codex  0 2026-10-31