Poolshark
Poolshark is a family of languages discovered by User:Orby during February of 2019.
Introduction
The execution of a Poolshark program consists of a simulation of a point mass moving at constant speed undergoing specular reflections off the boundary of a well defined region D ⊆ Rn. The language is defined by the region D and a program is defined by the initial velocity (v0 ∈ Rn) and initial position (p0 ∈ Rn) of the point mass. Each point on the boundary of D may map to a 0 or a 1. A collision at such a point on the boundary causes that bit to be output. If the point mass collides with a point on the boundary which is not differentiable (i.e. the specular reflection is undefined) then the machine halts.
Examples
There are an infinite number of Poolshark languages. I will give examples of some of the interesting ones.
Poolshark on the unit square
Assume D to be the unit square, that is, D = [0, 1] x [0, 1]. The vertical sides output one upon collision. The horizontal sides output zero upon collision. The corners cause the machine to halt upon collision. Let's examine the set of programs which begin at the origin. Merely providing the slope of the initial trajectory is sufficient to describe the resulting collision map, so we will identify these programs by their slope.
Slope of 1
Let's begin with a simple example. Consider the program 1. That is, the point mass whose initial position is the origin and whose initial velocity is <1, 1>. The program 1 represents the motion of the point mass from the lower left hand corner to the upper right hand corner. No other collisions occur. This program simply halts and outputs nothing.
Slope of n
Slightly more complex examples include programs of the form n where n is a positive integer. It is not hard to see that they reflect off the horizontal walls (n - 1) times before colliding with a corner. Therefore they output (n - 1) zeros and halt.
Slope of 1/n
Programs of the form 1/n where n is a positive integer reflect off the vertical walls (n - 1) times before colliding with a corner. Therefore they output (n - 1) ones and halt. More generally, whatever sequence the program x outputs, the program 1/x will output it's logical negation.
Slope of n/m
Programs of the form n/m where n and m are positive integers exhibit more complex behavior. The program 2/3 outputs 101. 3/4 outputs 10101. In general, n/(n+1) will output 101010 ... (n - 1) times ... 1. 2/5 outputs 11011. Do you see a pattern? One thing they certainly all have in common is that they halt.
Irrational slope
Things get crazy when the slope is not rational. Ha! But in all cases, irrational programs never halt. One way of viewing this is saying that Poolshark on the unit square starting at the origin is the program which takes input in the form of a velocity slope and halts if that slope is rational. There is a problem with irrational programs though: the set of all of them is uncountable. Thus, we cannot assign a Godel numbering to them and they cannot properly be called programs. A countable subset of irrational numbers may properly be called programs though (e.g. algebraic numbers). It may make more sense to restrict input to computable reals, which are countable.
Magic mirrors
One useful tool is a so called magic mirror. A magic mirror is a curve which is differentiable only at points in a specific subset of Rn. By directing the point mass at a magic mirror, we can cause the machine to halt for points not in the subset, while controlling the trajectory of points in the subset according to the derivative of the magic mirror at those points.
Mark Lynch describes a method for constructing a magic mirror for the rationals in "A Continuous Function That Is Differentiable Only at the Rationals", linked bellow. This means that it is possible to construct a Poolshark machine which halts only for irrational inputs. The irrational numbers are not recursively enumerable, therefore such a Poolshark machine would be Hyperturing. Clearly we cannot simulate such a Poolshark machine.
See also
- Billiard ball machine also features things bouncing around.
- Trajedy is another particle simulation that can move non-orthogonally.
- Dynamical billiards is the mathematical field which inspired Poolshark.
- This paper describes the construction of a curve which is differentiable only at rational points.