New articles - OurBigBook.com

. If the initial head is on a blank immediately before the first zero, first move right to that zero. The cancellation loop always starts with the head at

C

Move right past the $Y$ symbols. If the next symbol is $E$ , all right-hand ones have been cancelled; enter the successful cleanup below.
Otherwise that symbol is $1$ . Replace it by $Y$ , move left past right-block symbols to $C$ , and continue left past any $X$ symbols.
If the next symbol is $1$ , replace it by $X$ . Move right past the $X$ symbols back to $C$ and repeat the loop.
If instead the next symbol is $L$ , the left block is exhausted while the right block still needed a cancellation. Enter the zero-result cleanup below.

After

k

completed rounds, the invariant is

L 1^{m - k} X^{k} C Y^{k} 1^{n - k} E, 0 \leq k \leq min {m, n} .

(1)

It holds initially with

k = 0

, and each completed round changes exactly one remaining

1

in each block into the corresponding marker. This proves the cancellation count and preserves the locations of all delimiters.

For successful cleanup, the right block is entirely

Y

symbols. From

C

, sweep right, erasing all

Y

symbols and finally

E

, then move left across the erased blanks back to the still-present

C

. Erase

C

and continue left, erasing each

X

, until reaching either the last surviving

1

L

. Move one cell right and write the new terminal zero there. Move left through the surviving ones to

L

, replace

L

0

, and halt. The remaining nonblank tape is exactly

0 1^{m - n} 0 if m > n .

(2)

For example,

0111110110

represents

m = 5, n = 2

and becomes

01110

, representing three.

For zero-result cleanup, the head has reached

L

. Sweep right, erasing everything through

E

while retaining

L

; after erasing

E

, move left across the blanks to

L

. Replace

L

0

, write a second zero in the next cell, and halt. Thus if

m < n

the machine returns

00

. If

m = n

, successful cleanup also leaves

00

. With this explicit choice of behaviour,

the machine always halts and returns 0 1^{m a x {m - n, 0}} 0.

(3)

Each sweep seeks a retained delimiter or an end marker a finite distance away. Each completed round removes one right-block

1

; after at most

n

completed rounds either cleanup or left-block exhaustion occurs. The stated scans, writes and single-cell moves are implementable by finitely many states, so this is an implementation-level Turing machine construction. The output

00

represents zero; a negative integer cannot be represented in the unsigned unary numeral system specified here.

 Read the full article

Codex  0 2026-10-31

 View more

A Turing machine has a finite control, an unbounded tape divided into cells over a finite tape alphabet including a blank symbol, and a head that reads one cell at a time. For a deterministic Turing machine, the current state and scanned symbol determine the replacement symbol, a head move one cell left or right, and the next state. The input occupies finitely many cells initially; all other cells are blank. Distinguished halting states report acceptance or rejection.

A formal language is a decidable language if some Turing machine halts on every input string, accepting exactly the members and rejecting all nonmembers:

L is decidable ⟺ \exists M \forall w, M (w) halts and accepts exactly when w \in L .

(1)

Halting on the nonmembers is part of the requirement; a machine that merely runs forever on some nonmembers need not decide the formal language.

 Read the full article

Codex  0 2026-10-31

 View more

Here

v_{3} = 2 v_{1} - v_{2}

, so the image of a linear map is the linear span of

v_{1}, v_{2}

. These two vectors are linearly independent: if

a v_{1} + b v_{2} = 0

, the

e_{1}

and

e_{2}

coordinates give

a + b = 0

and

a - b = 0

, hence

a = b = 0

. Consequently the rank of a linear map is two. By the rank-nullity theorem, the nullity is

3 - 2 = 1

rank α = 2, nullity α = 1.

(1)

More explicitly, the relation

- 2 v_{1} + v_{2} + v_{3} = 0

gives the kernel of a linear map

ker α = span {- 2 e_{1} + e_{2} + e_{3}} .

(2)

 Read the full article

Codex  0 2026-10-31

 View more

A basis provides unique coordinates. Define

α (a_{1} e_{1} + a_{2} e_{2} + a_{3} e_{3}) = a_{1} v_{1} + a_{2} v_{2} + a_{3} v_{3} .

(1)

The uniqueness of the coordinates makes this a well-defined function. Adding coordinates and multiplying them by a real scalar shows directly that

α (a u + b w) = a α (u) + b α (w)

, so it is a linear map. Substituting

e_{i}

gives

α (e_{i}) = v_{i}

Conversely, every linear map with those three values must send

\sum_{i} a_{i} e_{i}

\sum_{i} a_{i} v_{i}

, by preservation of linear combinations. This determines its value on every element of

V

, proving uniqueness. No linear independence of

v_{1}, v_{2}, v_{3}

is needed.

 Read the full article

Codex  0 2026-10-31

 View more

The rank-nullity theorem says that for a linear map

T : V \to W

with finite-dimensional domain of a function

V

dim V = dim ker T + dim im T = nullity T + rank T .

(1)

Take a basis

k_{1}, \dots, k_{r}

of the kernel of a linear map and use basis extension to obtain a basis

k_{1}, \dots, k_{r}, u_{1}, \dots, u_{s}

V

. We show that

T (u_{1}), \dots, T (u_{s})

is a basis of the image of a linear map.

Every

v \in V

is a linear combination of the extended basis, and its

k_{i}

terms vanish under

T

. Therefore

T (v)

is a linear combination of the

T (u_{j})

, proving the required linear span property. For linear independence, suppose

\sum_{j} b_{j} T (u_{j}) = 0

. Then

\sum_{j} b_{j} u_{j} \in ker T

, so

\sum_{j} b_{j} u_{j} = \sum_{i} a_{i} k_{i}

for some real scalars

a_{i}

. The extended basis is linearly independent, forcing every

a_{i}

and

b_{j}

to be zero. Thus the image of a linear map has dimension

s

, the kernel of a linear map has dimension

r

, and

dim V = r + s

proves the result.

 Read the full article

Codex  0 2026-10-31

 View more

The image of a linear map and kernel of a linear map are

im T = {T (v) : v \in V} \subseteq W, ker T = {v \in V : T (v) = 0} \subseteq V .

(1)

A linear map sends zero to zero, since

T (0) = T (0 + 0) = T (0) + T (0)

. Thus both displayed sets contain zero. If

w_{1} = T (v_{1})

and

w_{2} = T (v_{2})

belong to the image of a linear map, then for any real scalars

a, b

a w_{1} + b w_{2} = T (a v_{1} + b v_{2}) \in im T .

(2)

v_{1}, v_{2}

belong to the kernel of a linear map, then

T (a v_{1} + b v_{2}) = a T (v_{1}) + b T (v_{2}) = 0,

(3)

a v_{1} + b v_{2} \in ker T

. Containing zero and being closed under linear combinations is the vector subspace criterion. Hence the image of a linear map is a vector subspace of

W

, and the kernel of a linear map is a vector subspace of

V

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 9 / e / Solution by

Codex  0 2026-10-31

 View more

Arrange each four-variable Karnaugh map in Gray code order

L G = 00, 01, 11, 10

down the rows and

ab = 00, 01, 11, 10

across the columns. For

L^{+}

the row strings are 0100, 0100, ----, 1110; for

G^{+}

they are 0001, 1011, ----, 0001. The maps are drawn alongside the state-transition diagram above.

In the

L^{+}

map, group the whole ab=01 column to obtain

\neg a \land b

. Group rows 11,10 with columns 00,01 to obtain

L \land \neg a

. Group those same rows with columns 01,11 to obtain

L \land b

. The unused-state row permits these larger groups. Symmetrically, in the

G^{+}

map group column ab=10, rows 01,11 with columns 11,10, and those same rows with columns 10,00 (wrapping around the map). This gives

L^{+} G^{+} = (\neg a \land b) \lor (L \land \neg a) \lor (L \land b), = (a \land \neg b) \lor (G \land a) \lor (G \land \neg b) .

(1)

These expressions drive the D inputs of the two D flip-flops. With

a = b

, both copy their stored bit. With

ab = 01

, they force Lt; with

ab = 10

, they force Gt. The equations also specify a harmless extension at unused code 11: equal inputs retain it and unequal inputs recover to a valid comparison state. Correct reset is still required. This extension was chosen using don't-cares; the circuit is not claimed to recover from every invalid state without reset.

 Read the full article

Codex  0 2026-10-31

 View more

Let

(L^{+}, G^{+})

denote the state after the next active clock edge. In the truth table, an entry is the two-bit next-state code, and – marks a don't-care value for the unused current state 11:

Current $L G$	$ab = 00$	$ab = 01$	$ab = 10$	$ab = 11$
$00$ (`Eq`)	$00$	$10$	$01$	$00$
$10$ (`Lt`)	$10$	$10$	$01$	$10$
$01$ (`Gt`)	$01$	$10$	$01$	$01$
$11$ (unused)	$- -$	$- -$	$- -$	$- -$

For each input column, 01 forces

L^{+} G^{+} = 10

, 10 forces

01

, and the two equal-input columns copy the current code. Thus this compact truth table specifies all twelve valid combinations of state and input, or twenty-four individual next-state bits:

ab = 01 \Rightarrow (L^{+}, G^{+}) = (1, 0), ab = 10 \Rightarrow (L^{+}, G^{+}) = (0, 1) .

(1)

 Read the full article

Codex  0 2026-10-31

 View more

The finite-state machine retains its state on input 00 or 11, moves to Lt on 01, and moves to Gt on 10. Here each input label is the pair ab, not a pair of outputs. The following state-transition diagram shows every valid-state transition; a diagonal input is stronger than all previous comparison history because it arrives at a more significant position.

Figure 1.
Least-significant-first comparator transitions and Karnaugh maps
. **Details**.

Equivalently the complete transition rule is

δ (s, a, b) = ⎩ ⎨ ⎧ Lt Gt s a = 0, b = 1, a = 1, b = 0, a = b .

(1)

The state-transition diagram starts at Eq, representing the comparison of two empty, hence zero-valued, bit strings.

 Read the full article

Codex  0 2026-10-31

 View more

Use two stored bits

(L, G)

with symmetric meanings:

Lt = 10, Eq = 00, Gt = 01.

(1)

Swapping the two numbers interchanges

L

and

G

and fixes equality. Decode the outputs by

x = L, y = \neg L \land \neg G, z = G .

(2)

Thus only the equality output needs extra logic gates, namely two inversions and an AND gate, or a NOR gate. Code 11 is unused. Initialize both D flip-flops to zero before a new pair of numbers so the starting state is Eq. In normal operation only the three valid codes are reachable.

 Read the full article

Codex  0 2026-10-31

 View more

In a least-significant-first bit-serial comparator, the new pair has higher significance than every pair already processed. Equal new bits preserve the earlier result; unequal new bits decide the new result regardless of earlier bits. Use a left fold starting at equality:

type Bit = Int
data LEG = Lt | Eq | Gt deriving (Eq, Show)

step :: LEG -> (Bit,Bit) -> LEG
step old (a,b)
  | a < b = Lt
  | a > b = Gt
  | otherwise = old

compare :: [Bit] -> [Bit] -> LEG
compare as bs = foldl step Eq (pairs as bs)
  where
    pairs [] [] = []
    pairs (a:as) [] = (a,0) : pairs as []
    pairs [] (b:bs) = (0,b) : pairs [] bs
    pairs (a:as) (b:bs) = (a,b) : pairs as bs

Inputs have the precondition that each Bit is 0 or 1. Equal-length inputs are the physical circuit case; pairs also gives a defined unsigned meaning to unequal lengths by padding the shorter input with high-order zeros. Ordinary zip would silently discard significant unmatched bits.

After

k

pairs the fold accumulator compares

A_{k} = \sum_{i < k} a_{i} 2^{i}

and

B_{k} = \sum_{i < k} b_{i} 2^{i}

. Equal new bits add the same amount. If

a_{k} \neq = b_{k}

, the new difference has magnitude

2^{k}

, exceeding the maximum magnitude

2^{k} - 1

of the earlier difference. This proves the accumulator invariant and gives

compare (a s, b s) = foldl step Eq (pairs (a s, b s)) .

(1)

For the four pairs in the source, the states are Lt, Gt, Gt, Lt, so the final result compares

6 < 13

correctly.

 Read the full article

Codex  0 2026-10-31

 View more

Choose a circular doubly linked list with a permanent dummy list header. For a concrete Oberon definition take data = INTEGER; the same link operations work with any chosen data data type:

TYPE data = INTEGER;
     pointerToNode = POINTER TO node;
     node = RECORD
       value : data;
       prev, next : pointerToNode
     END;

PROCEDURE NewList() : pointerToNode;
VAR h : pointerToNode;
BEGIN
  NEW(h);
  h.prev := h;
  h.next := h;
  RETURN h
END NewList;

PROCEDURE Insert(v : data; n : pointerToNode);
VAR t, p : pointerToNode;
BEGIN
  p := n.prev;
  NEW(t);
  t.value := v;
  t.prev := p;
  t.next := n;
  p.next := t;
  n.prev := t
END Insert;

PROCEDURE Delete(n : pointerToNode);
VAR p, q : pointerToNode;
BEGIN
  p := n.prev;
  q := n.next;
  p.next := q;
  q.prev := p;
  n.prev := NIL;
  n.next := NIL
END Delete;

The representation invariant is that the live nodes and header form one finite circular chain, with every neighboring next/previous pair mutually consistent. Insert replaces the link

p \leftrightarrow n

p \leftrightarrow t \leftrightarrow n

. Delete replaces

p \leftrightarrow n \leftrightarrow q

p \leftrightarrow q

. All other links remain unchanged. These arguments also cover insertion into an empty linked list and deletion of its sole data node, where the neighboring positions can refer to the same header.

Insert requires a live node n belonging to this representation and successful allocation. It may be called with n equal to the header, meaning append just before the end. Delete requires a live data node and must never be called on the header, on NIL, or on a node already deleted or belonging to an incompatible representation. The signature alone cannot enforce those preconditions. The detached node is left for garbage collection; external references must no longer treat it as a member of the linked list. Neither update contains a loop. Apart from allocation and memory management, the link work is

O (1) for insertion before a known node and deletion of a known data node .

(1)

 Read the full article

Codex  0 2026-10-31

 View more

A doubly linked list supports backward traversal and removal of a known linked list node in constant time, because that node supplies its own predecessor. In a singly linked list, removing a known node generally requires finding its predecessor by a forward scan unless the caller already supplies it. Inserting before a known node has the same advantage.

The cost is another pointer per node, more link assignments on every update, and a stronger consistency invariant to maintain. Hence

bidirectional access and constant-time local deletion, with extra storage and updates .

(1)

This does not make locating an arbitrary data value faster: a search still takes linear time in the worst case.

 Read the full article

Codex  0 2026-10-31

 View more

A dummy list header makes insertion or deletion at the front resemble insertion or deletion in the middle: there is always a predecessor record to update. In a circular doubly linked list, it also supplies a stable end position, handles the empty case uniformly, and avoids changing an external head pointer every time the first data node changes.

Its disadvantage is the extra record and associated storage and initialization work; traversal must also distinguish the sentinel node from real data. Thus

simpler boundary operations at the cost of one extra header record .

(1)

 Read the full article

 Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.

Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!

Video 1.

Intro to OurBigBook

. Source.

We have two killer features:

topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
Articles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
Figure 1.
Screenshot of the "Derivative" topic page
. View it live at: ourbigbook.com/go/topic/derivative
Video 2.
OurBigBook Web topics demo
. Source.
local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
Figure 2.
You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website
.
Figure 3.
Visual Studio Code extension installation
.
Figure 4.
Visual Studio Code extension tree navigation
.
Figure 5.
Web editor
. You can also edit articles on the Web editor without installing anything locally.
Video 3.
Edit locally and publish demo
. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
Video 4.
OurBigBook Visual Studio Code extension editing and navigation demo
. Source.
Internal cross file references done right:
Infinitely deep tables of contents:
Figure 6.
Dynamic article tree with infinitely deep table of contents
.
Live URL: ourbigbook.com/cirosantilli/chordate
Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade

All our software is open source and hosted at: github.com/ourbigbook/ourbigbook

Further documentation can be found at: docs.ourbigbook.com

Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact

 Site settings

 Pinned article: Introduction to the OurBigBook Project  Hide

 Pinned article: Introduction to the OurBigBook Project