User:Snowyowl/Hello, world! in Formula
Hi. This is the page where I'm plotting how to write a Hello, world! program in Formula.
I'll move it to the right page once it's completed to my satisfaction. Feel free to edit this page and change the wording; I'm not quite explaining it as clearly as I'd like.
The program should output "Hello, world!" in ASCII. The bitstring we want is:
01001000011001010110110001101100011011110010110000100000011101110110111101110010011011000110010000100001
Now, we write this on a 2D grid:
v0
1v
v00
1v
v0000
11v
v00
1v
v0
1v
v0
11v
v0
11v
v000
11v
v0
11v
v000
11v
v0
1111v
v00
1v
v0
11v
v0000
1v
v000000
111v
v0
111v
v0
11v
v0
1111v
v0
111v
v00
1v
v00
11v
v0
11v
v000
11v
v00
1v
v0000
1v
v0000
1E
- Execution starts at the top-right 0.
- 0 on the grid means "output 0 and move left", and corresponds to Formula values between -0.5 and 0.
- 1 means "output 1 and move right", and corresponds to Formula values between 0 and 0.5.
- v means "move down", and corresponds to Formula values between -2.5 and -1.5.
- E means "end the program", and corresponds to a Formula value of exactly 0.
We now have to find a formula that produces this layout. Fortunately, the values not actually shown here can be anything we want. This grid could, for example, be covered for all directions in stripes of 0s and 1s, and then be "perturbed" in 52 locations to add the vs and the E. This works well, because the Formula for an infinite striped plane is very simple:
f(x,y) = -0.25*cos(3.141592*y)
...well, okay, it's not perfect, but we only need it to work for -51 <= y <= 0. The perturbations are also not that complicated. The vs have a margin of error, so we can get away with just subtracting (approximately) 2 from all the necessary grid locations (leaving the rest unaltered, to within reasonable error margins). The E is a little more refined, because it needs to be exactly 0. We can achieve this by multiplying the formula by something that is equal to 0 at (-6,-51) and almost equal to 1 everywhere else.
The grid locations where a perturbation is needed are:
positions of v: 0 -1 -1 0 -2 -2 -3 -1 -4 -5 -5 -3 -6 -5 -7 -4 -8 -5 -9 -4 -10 -5 -11 -3 -12 -4 -13 -2 -14 -5 -15 -3 -16 -4 -17 -2 -18 -5 -19 -3 -20 -4 -21 0 -22 -2 -23 -1 -24 -2 -25 0 -26 -4 -27 -3 -28 -9 -29 -6 -30 -7 -31 -4 -32 -5 -33 -3 -34 -4 -35 0 -36 -1 -37 2 -38 0 -39 1 -40 -1 -41 1 -42 0 -43 2 -44 -1 -45 1 -46 -1 -47 0 -48 -4 -49 -3 -50 -7 position of E: -51 -6
One suggestion for a perturbation is:
p_ab(x,y) = 0.001/((x-a)^2+(y-b)^2+0.001)
which is equal to 1 for x=a and y=b, and is less than 0.001 for all other integer x and y. Using this to create our finished Formula program, it gives:
Hello, world!
f(x,y) = ( -0.25*cos(3.141592*y)
-2*(
0.001/(y^2+(x+1)^2+0.001)
+ 0.001/((y+1)^2+x^2+0.001)
+ 0.001/((y+2)^2+(x+2)^2+0.001)
+ 0.001/((y+3)^2+(x+1)^2+0.001)
+ 0.001/((y+4)^2+(x+5)^2+0.001)
+ 0.001/((y+5)^2+(x+3)^2+0.001)
+ 0.001/((y+6)^2+(x+5)^2+0.001)
+ 0.001/((y+7)^2+(x+4)^2+0.001)
+ 0.001/((y+8)^2+(x+5)^2+0.001)
+ 0.001/((y+9)^2+(x+4)^2+0.001)
+ 0.001/((y+10)^2+(x+5)^2+0.001)
+ 0.001/((y+11)^2+(x+3)^2+0.001)
+ 0.001/((y+12)^2+(x+4)^2+0.001)
+ 0.001/((y+13)^2+(x+2)^2+0.001)
+ 0.001/((y+14)^2+(x+5)^2+0.001)
+ 0.001/((y+15)^2+(x+3)^2+0.001)
+ 0.001/((y+16)^2+(x+4)^2+0.001)
+ 0.001/((y+17)^2+(x+2)^2+0.001)
+ 0.001/((y+18)^2+(x+5)^2+0.001)
+ 0.001/((y+19)^2+(x+3)^2+0.001)
+ 0.001/((y+20)^2+(x+4)^2+0.001)
+ 0.001/((y+21)^2+x^2+0.001)
+ 0.001/((y+22)^2+(x+2)^2+0.001)
+ 0.001/((y+23)^2+(x+1)^2+0.001)
+ 0.001/((y+24)^2+(x+2)^2+0.001)
+ 0.001/((y+25)^2+x^2+0.001)
+ 0.001/((y+26)^2+(x+4)^2+0.001)
+ 0.001/((y+27)^2+(x+3)^2+0.001)
+ 0.001/((y+28)^2+(x+9)^2+0.001)
+ 0.001/((y+29)^2+(x+6)^2+0.001)
+ 0.001/((y+30)^2+(x+7)^2+0.001)
+ 0.001/((y+31)^2+(x+4)^2+0.001)
+ 0.001/((y+32)^2+(x+5)^2+0.001)
+ 0.001/((y+33)^2+(x+3)^2+0.001)
+ 0.001/((y+34)^2+(x+4)^2+0.001)
+ 0.001/((y+35)^2+x^2+0.001)
+ 0.001/((y+36)^2+(x+1)^2+0.001)
+ 0.001/((y+37)^2+(x-2)^2+0.001)
+ 0.001/((y+38)^2+x^2+0.001)
+ 0.001/((y+39)^2+(x-1)^2+0.001)
+ 0.001/((y+40)^2+(x+1)^2+0.001)
+ 0.001/((y+41)^2+(x-1)^2+0.001)
+ 0.001/((y+42)^2+x^2+0.001)
+ 0.001/((y+43)^2+(x-2)^2+0.001)
+ 0.001/((y+44)^2+(x+1)^2+0.001)
+ 0.001/((y+45)^2+(x-1)^2+0.001)
+ 0.001/((y+46)^2+(x+1)^2+0.001)
+ 0.001/((y+47)^2+x^2+0.001)
+ 0.001/((y+48)^2+(x+4)^2+0.001)
+ 0.001/((y+49)^2+(x+3)^2+0.001)
+ 0.001/((y+50)^2+(x+7)^2+0.001)
)
) * (1 - 0.001/((y+51)^2+(x+6)^2+0.001) )
Formula is a fairly strong contender for the most absurd language to write "Hello, world!" in. Or it will be, if someone hacks together an interpreter to see if this actually works like I say it does.
Notes on computational class
It's a relatively small modification to the perturbation function to make it perturb an infinite number of grid cells. Consider:
p(x,y) = 0.001/(10*sin(pi*(x-a)/20)^2+10*sin(pi*(y-b)/20)^2+0.001)
which is 1 when x = a mod 10 and y = b mod 10, and small-ish otherwise. (note: estimate exact size of deviation from 0) This lets us build infinite tilings. It should also be possible to build non-repeating tilings, such as by perturbing every cell whose x-coordinate is a square. This can simulate some Minsky machines and Collatz functions. Whether it can simulate a Turing-complete one remains to be seen.