Post Dominos

From Esolang
Jump to navigation Jump to search

Post Dominos is a declarative esolang. It was discovered shamelessly ripped by User:Orby in 2019.

Introduction

Emil Post introduced what has come to be known as the Post correspondence problem in 1946. The tiles, or "dominos", used to model the problem are the basis of Post Dominos. A Post Dominos program consists of a finite number of dominos, each with a left string and a right string composed of a finite set of symbols. Any sequence of dominos for which the concatenation of the left strings is equal to the concatenation of the right strings is accepted by the program. All others are rejected.

Examples

The strings of a domino may be composed from any finite set of symbols, but we will restrict ourselves to the set {"0", "1"}. We will delimit the left and right strings with a space. An example of a domino is "101 10" where "101" is the left string and "10" is the right string. An example of a program consisting of four dominos is

 1 1101
 101 10
 01 1
 1101 1

This program accepts an infinite set of strings, one example being

10110111101110110110101 (*)

which is derived from the following sequence of dominos

101 10, 1 1101, 01 1, 1 1101, 1 1101, 101 10, 1101 1, 101 10, 101 10, 01 1

Notice that the concatenation of the left strings is equal to (*), as is the concatenation of the right strings.

Canonical programs

For any sequences a and b that are accepted by a program, the sequences aa, ab, ba, and bb are also accepted by the program for obvious reasons.

Hello, World!

 "Hello, World!" "Hello, World!"

See also