Nellie Mullane

Cantor Set Proof

Language Decision: MOD 2

Description: This Turing machine decides whether the number of '1's in the input is even (MOD 2). It accepts if the number of '1's is even and rejects otherwise.

Run

Final State:

Final Tape:

Steps:

Result:

Function Computation: push

Description: This Turing machine computes the function push: {0, 1}^* → {0, 1, $}^*, where push(w) appends a '$' character to the beginning of string w (e.g., 101 → $101).

Run

Final State:

Final Tape:

Steps:

Result:

Language Decision: Palindromic Strings Around #

Description: This Turing machine decides whether the string on the left side of the '#' is the same as the string on the right side. For example, it accepts '0110#0110' but rejects '011#110'.

Run

Final State:

Final Tape:

Steps:

Result:

Function Computation: plus1

Description: This Turing machine computes the function plus1: {0, 1}^* → {0, 1}^*, interpreting the input as a binary number from least-significant bit (LSB) to most-significant bit (MSB). It outputs the binary representation of the input number plus one, processed bit by bit. For example, 101 (binary for 5) → 011 (binary for 6).

Run

Final State:

Final Tape:

Steps:

Result:

Function Computation: unary2binary

Description: This Turing machine computes the function unary2binary: {1}^* → {0, 1}^*, converting unary strings to their binary representation. The binary representation is processed and printed from least-significant bit (LSB) to most-significant bit (MSB), appearing reversed to us. For example, 111 (unary representation of 3) → 11 (binary representation of 3, printed as 11 from LSB to MSB).

Run

Final State:

Final Tape:

Steps:

Result:

Language Decision: {aⁱb^jc^k | i, j, k ∈ Z≥0, i < j < k}

Description: This Turing machine decides the language L = {aⁱb^jc^k | i, j, k ∈ Z≥0, i < j < k}. It checks whether the counts of 'a's, 'b's, and 'c's satisfy the strict inequality i < j < k (e.g., abbccc is accepted, but aabbccc is rejected).

Run

Final State:

Final Tape:

Steps:

Result:

Language Decision: {a^k | k is a power of 2}

Description: This Turing machine decides the language L = {a^k | k is a power of 2}, where k ∈ {1, 2, 4, 8, ...}. It identifies strings of 'a' whose lengths are powers of 2.

Run

Final State:

Final Tape:

Steps:

Result: