LogoLogo
1.0.0
  • Home
  • Install
  • Docs
  • Contribute
  • Journey
1.0.0
  • Welcome
  • The Varphi Language Standard
    • Welcome
    • State Names
    • Tallies and Blanks
    • Head Directions
    • Lines
    • Comments
    • Varphi Programs
    • Addressing Ambiguities
  • Writing Varphi Programs
    • Your First Varphi Program
    • Running Varphi Programs
    • Debugging Varphi Programs
    • The Varphi VS Code Extension
    • Good Practices
    • More Examples
      • Addition By One
      • Add Two Numbers
      • Multiplication By Two
      • Rock, Paper, Scissors
      • Coin Flip
  • Turing Machine Theory
    • The Unary Number System
    • Turing Machine Tapes
    • Turing Machine Heads
    • Turing Machine States
    • Turing Machines
    • Nondeterministic Turing Machines
Powered by GitBook
LogoLogo

© 2025 Hassan El-Sheikha

On this page
  • Structure
  • The Condition and the Instruction

Was this helpful?

Edit on GitHub
Export as PDF
  1. The Varphi Language Standard

Lines

Structure

A line represents a transition rule in the Turing machine. Every line consists of five elements in the following order:

  1. A state name representing the current state of the Turing machine.

  2. A tally or blank representing the condition of the tape cell that the head is currently positioned at.

  3. A state name representing the state the Turing machine is left in after the transition is applied.

  4. A tally or blank representing the condition of the tape cell after the transition is applied.

  5. A head direction representing the direction the head will move in after the transition is applied.

A general line will look like the following:

STATE_NAME1 TALLY|BLANK STATE_NAME2 TALLY|BLANK HEAD_DIRECTION

The space between elements of a line is not restricted to being a single space. Any whitespace can be added between elements of a line without causing syntax errors, which makes it possible to format programs!

The parser uses the following pattern to match lines (assuming single spaces between elements, though this is not required):

q[a-zA-Z0-9_]+ 0|1 q[a-zA-Z0-9_]+ 0|1 L|R

The Condition and the Instruction

The first two elements of a Varphi line are called the condition. The condition can be read as follows:

If

  1. the Turing machine is using state [state], and

  2. the tape cell which the head is currently situated at [contains a tally/is blank]

The remaining three elements of the line are called the instruction. They instruct the Turing machine to perform a series of actions. You can read the instruction as follows:

Make

  1. the Turing machine use state [state]

  2. the tape cell at the which the head is currently situated at [contain a tally/blank]

  3. the head move to the tape cell immediately to the [left/right] of the tape cell which it is currently situated at.

Overall, you can read a Varphi line as follows:

If

  1. the Turing machine is using state [state]

  2. the tape cell which the head is currently situated at [contains a tally/is blank],

then make

  1. the Turing machine use state [state]

  2. the tape cell at the which the head is currently situated at [contain a tally/blank]

  3. the head move to the tape cell immediately to the [left/right] of the tape cell which it is currently situated at.

PreviousHead DirectionsNextComments

Last updated 3 months ago

Was this helpful?