# Examples

The best way to internalize Varphi's syntax and semantics is by reading and writing code. This section presents three fundamental programs that progress from simple state machines to multi-tape algorithms.

***

### 1. The Binary Incrementer (Single Tape)

This machine takes a binary number (e.g., `1011`) on the tape and adds `1` to it (resulting in `1100`).

#### The Logic

1. **Scan Right:** We start at the beginning (left) of the number. We must traverse to the far right end to find the Least Significant Bit (LSB).
2. **Scan Left (Carry):** Once we hit a `BLANK` at the end, we move one step left and enter the "carry" state.
   * If we see a `1`, change it to `0` and keep moving left (carry over).
   * If we see a `0`, change it to `1` and stop (carry consumed).
   * If we see a `BLANK` (overflow), write `1` and stop.

#### The Code

```
// Step 1: Move to the far right of the string
// If we see 0 or 1, keep moving RIGHT.
start   (0)      start    (0)     (RIGHT)
start   (1)      start    (1)     (RIGHT)

// When we hit a BLANK, we've passed the number. 
// Move LEFT back onto the last digit and switch to 'carry' mode.
start   (BLANK)  carry    (BLANK) (LEFT)


// Step 2: Perform the addition
// Case A: Found a '1'. Flip to '0' and keep carrying left.
carry   (1)      carry    (0)     (LEFT)

// Case B: Found a '0'. Flip to '1'. No more carry needed. Halt.
carry   (0)      halt     (1)     (STAY)

// Case C: Found a BLANK. This means we overflowed (e.g. 11 + 1 = 100).
// Write the final '1' and Halt.
carry   (BLANK)  halt     (1)     (STAY)
```

***

### 2. The Equality Tester (Multi-Tape)

This program compares two strings on two separate tapes to see if they are identical. It demonstrates the power of Varphi's variable support. We define a specific rule for "match" and a generic rule for "mismatch," relying on the compiler to pick the right one.

#### The Logic

1. **Match:** If Tape 1 has `$x` and Tape 2 has `$x` (the *same* symbol), move both heads right.
2. **Mismatch:** If Tape 1 has `$x` and Tape 2 has `$y` (implicitly different), the strings are not equal. Reject.
3. **End:** If both tapes hit `BLANK` at the same time, the strings were equal. Accept.

#### The Code

```
// Case 1: Both characters match
// In this case, just move both heads right
// Specificity: ($x, $x) uses 1 unique variable. 
// This is MORE specific than the ($x, $y) rule below.
// If both heads see the same symbol, this rule WILL be hit.
compare  ($x, $x)        compare  ($x, $x)        (RIGHT, RIGHT)

// Case 2: Both characters are BLANK
// In this case, the strings are equal (or we would've failed already)
compare  (BLANK, BLANK)  accept   (BLANK, BLANK)  (STAY, STAY)

// 3. Case 3: The two characters mismatch
// Specificity: ($x, $y) uses 2 unique variables.
// This rule runs only if the ($x, $x) rule above fails to match.
compare  ($x, $y)        reject   ($x, $y)        (STAY, STAY)
```

{% hint style="info" %}
We did not need to explicitly write transitions for length mismatches (e.g., `($x, BLANK)`). Because `($x, $y)` matches *any* two symbols (including a symbol and a blank), it automatically catches cases where one tape ends before the other.
{% endhint %}

***

### 3. The Palindrome Detector (Multi-Tape)

This machine determines if a string is a palindrome (reads the same forwards and backwards). We use a two-tape approach: copy the input to the second tape, then compare them in opposite directions to make sure the string reads the same in reverse order.

#### The Logic

1. **Copy:** Copy the input from Tape 1 to Tape 2. Both heads end up at the far right.
2. **Rewind Head 1:** Move the head on Tape 1 back to the start of the string. Keep the head on Tape 2 at the end of the string.
3. **Converge:** Move Head 1 `RIGHT` (forward) and Head 2 `LEFT` (backward). If the symbols match at every step, it is a palindrome.

#### The Code

```
// Step 1: Copy
// Copy Tape 1 to Tape 2.
// While there is input on Tape 1, write it to Tape 2.
start   ($x, BLANK)     start    ($x, $x)       (RIGHT, RIGHT)

// When we hit the end (BLANK), step back one cell to the last char.
// Switch to 'rewind' mode.
start   (BLANK, BLANK)  rewind   (BLANK, BLANK) (LEFT, LEFT)


// Step 2: Rewind Head 1
// We want Head 1 at the start of Tape 1, but Head 2 must stay at 
// the end of Tape 2.
// As long as Head 1 reads a symbol, move it LEFT.
// Keep Tape 2 where it is (STAY).
rewind  ($x, $y)        rewind   ($x, $y)       (LEFT, STAY)

// When Tape 1 hits the BLANK at the start, move it RIGHT once
// to land on the first character. Switch to 'compare'.
rewind  (BLANK, $y)     compare  (BLANK, $y)    (RIGHT, STAY)


// Step 3: Compare
// Tape 1 scans forward (RIGHT), Tape 2 scans backward (LEFT).
// ---------------------------------------------------------

// Case A: Match ($x, $x). 
// The symbols are the same. Continue checking.
compare ($x, $x)        compare  ($x, $x)       (RIGHT, LEFT)

// Case B: Success.
// If both hit BLANK, we finished the whole string successfully.
compare (BLANK, BLANK)  accept   (BLANK, BLANK) (STAY, STAY)

// Case C: Mismatch ($x, $y).
// Because ($x, $x) is more specific, this rule only runs if 
// symbols differ.
compare ($x, $y)        reject   ($x, $y)       (STAY, STAY)
```