Galveston

From Esolang
Jump to navigation Jump to search

Galveston is an ω-language over the alphabet Σ = {NULL, v1, v2, ...}. A program in Galveston is a single ω-word from that language, i.e. a countably infinite sequence made up of symbols from a countably infinite totally-ordered alphabet.

The only fixed symbol in the alphabet Σ is the 0 indexed NULL character, v0 / \x00 / ␀ (visual). The remaining characters may be interpreted in any way convenient. A practical convention is to use ASCII and its superset Unicode to occupy the initial slots of this infinite alphabet, but it is not strictly required by the specification.

The concept of this language was inspired by Choose-your-own-Adventure style game books, and as such it may have some practical application as an interactive fiction engine.

Themes:

  • Encoding vs. computation.
  • Mapping input to output.
  • Interactivity.
  • Roles within computational systems (games).

Executing Galveston

Execution of a program is achieved by means of a function 

 y = g(x) : x ∈ ℕ, y ∈ Σ

Execution begins with x = 0, and at every step the resulting y is appended to the output. x is then incremented by 1 (by default), or a new x is chosen by the operator.

The convention is to continue the sequence from x = 0, in order, until y = NULL. Then follow any instructions or make any decisions about the next value of x as communicated by the output sequence so far.

Jump convention

Symbol v1 can be used to indicate the next symbol is to be interpreted as its index in alphabet Σ and used as the next input to g.

A sequence ... , v0, v1, vn can be used to output symbols, wait for a specific x input, or use x = n as a default, if no specific input is forthcoming.

It is up to the operator to follow this convention, or an interpreter to choose to provide an automatic jump facility.

Implementation Suggestions

One method to practically represent at least a subset of Galveston ω-words digitally is to store a relevant finite number of the output symbols sequentially in UTF∞ format, and assume any output beyond the length of the specified map is the NUL symbol.

These ω-word representations may be uncompressed (.glv), or gzipped (.glvz).

UTF∞

UTF∞ is a semi-facetious extension of UTF-8 to support arbitrarily large character (i.e. symbol) code points using arbitrarily large numbers of bytes. An as yet unpublished encoding implementation exists for Python.

Galveston Notation
Symbol Default byte representation Display notation Galveston assembly Description Symbol count Status
v0 \x00 ␀ {NUL} NUL symbol 0 1 Required
v1 \x01 ⇒ {JMP} Jump to next symbol index 1 Convention
v10 \x0A ␊ {LF} Line feed symbol 1 Convention
[:label:] Assembler label marker 0 Assembler notation
v48 – v57 [0–9]+ [0–9]+ (:label:) Assembler label to decimal (operator/player 1 readable number) 1 to many Assembler notation
vn (1 or many) {n} {:label:} Assembler label to symbol 1 Assembler notation

Where :label: is any string, excluding the reserved words NUL, JMP, LF, made from capital letters: A–Z, digits: 0–9, and the underscore character: _.

For ease of calculating offsets during compilation, the 'label to decimal' (:label:) output can be padded to a fixed width (with spaces or 0s) based on the size of the currently utilised region of the ω-word.

Examples

Plot of Truth machine ω-word

Truth Machine

(symbol notation) 

 Enter 30 for 0, 33 for 1.   ␊␀0␀␀1⇒!

Interactive scenario

In Galveston assembly (.gasm) format: 

[START]
You are standing in a small stone room.{LF}
There is a small desk in one corner and a door on the east wall.{LF}
[examine desk: (DESK_INITIAL)]{LF}
[examine door: (DOOR_LOCKED)]{LF}
{NUL}
{JMP}{START}

[DESK_INITIAL]
The desk is made of rough hewn oak.{LF}
It has a drawer with a small brass ring pull.{LF}
[open drawer: (OPEN_DRAWER)]{LF}
{NUL}
{JMP}{START}

[DOOR_LOCKED]
The door is locked. You need a key.{LF}
{NUL}
{JMP}{START}

[OPEN_DRAWER]
You open the drawer and find a large iron key!{LF}
{NUL}

[HAS_KEY]
You are standing in a small stone room.{LF}
There is a small desk in one corner and a door on the east wall.{LF}
[examine desk: (DESK_EMPTY)]{LF}
[unlock door: (UNLOCK_DOOR)]{LF}
{NUL}
{JMP}{HAS_KEY}

[DESK_EMPTY]
The desk is made of rough hewn oak.{LF}
It has a drawer with a small brass ring pull.{LF}
The drawer is open, and empty.{LF}
{NUL}
{JMP}{HAS_KEY}

[UNLOCK_DOOR]
You use the large iron key to open the door.{LF}
The lock is very stiff, but you manage to shift
 the bolts.{LF}
[leave room (WIN)]{LF}
{NUL}

[DOOR_UNLOCKED]
You are standing in a small stone room.{LF}
There is a small desk in one corner and a door on the east wall.{LF}
[examine desk: (DESK_EMPTY)]{LF}
[leave room: (WIN)]{LF}
{NUL}
{JMP}{DOOR_UNLOCKED}

[WIN]
You leave the room.{LF}
Congratulations! You are outside.{LF}
You have escaped. YOU WIN!{LF}
{NUL}{NUL}

Computational class

As specified, Galveston is not Turing complete. Some level of Turing completeness may be achieved with a willing human operator (able to store data, and enact decisions based on the encoded instructions) or a sufficiently featured interpreter able to perform similar functions based on some chosen conventions. One of the main purposes of this language was to explore these roles, and interactivity between systems. A Galveston program may be thought of as a self-referential function, requiring external encoding conventions to be interpreted correctly.

As a game theoretical game

A Galveston run may be thought of as a formal 'game' between two players. The g(x) Galveston ω-word represents the strategy of player 2, and the operator entity is player 1. Player 1 can play literally any strategy, but there should be some formal definition whereby winning strategies are only those that represent valid computations. Player 1 is strongly encouraged to play x = 0 as their first move, but can play anything. (It follows that all winning strategy outputs will have the same finite-prefix substring.)

Even without relying on player 1 to act as a memory store, Galveston should be able to represent all possible programs executable on bounded storage machines (therefore is equivalent to a FSM) but additionally is able to execute additional programs. A trivial example of this class of programs executable on this kind of system but not on a BSM is counting to infinity. This can be represented in Galveston as a program which outputs each symbol from Σ in order (which is equivalent to one that outputs line-feed separated base-10 representations of all natural numbers).

As an abstract machine, control flow is always the ultimate responsibility of player 1. Specific decision points are marked by the spec (NULL), and there is always a well defined default next move for player 1 (x + 1), and additionally the potential for suggestions and branch possibilities or jumps by convention, but at any turn player 1 is free to play an arbitrary x (which will likely break computation, and result in a loss).

Oracles

This language is able to represent theoretical oracles (at least an oracle, if not a full wikipedia:oracle machine).

An oracle maps x ∈ ℕ to some T/F answer for all values of x. An ω-word over sub-alphabet {vT, vF} ⊂ Σ represents exactly that. All possible 2 (or more)-symbol oracles are words in the Galveston ω-language. This suggests super-Turing completeness.

This model of computation could be compared and contrasted with a read-only Turing machine, since Galveston most definitely does not possess a write head (unless player 1 brings one to the table).

The problem with determining a computational class equivalence for this language is that this specification defines more of a game-theoretical game, with a deterministic strategy specified for one player (g(x), 'player 2' or the system player, where the ω-word defines a deterministic strategy). This seems related to, but not equivalent to a computational model. The overall computational ability arises from the interactions of both players, and the attributes of player 1 are not part of the spec, and can vary. The concept of 'conventions' allow the system player to potentially control the actions of the other player, but that is deliberately neither strict nor well defined. It is perhaps interesting that which player provides the most computational ability is not clear (in the theoretical Oracle case it is the system than provides the 'super'-TC power by proving infinte oracle data). Defining the possible roles for each player formally and how those relate to computation may be an interesting exercise.

All interactive languages could be analysed using a similar framework, and in some sense all useful programming languages require a non-system player 1, and conventions for choosing inputs and interpreting outputs.

External resources

Retrieved from "https://esolangs.org/w/index.php?title=Galveston&oldid=131899"