The numerators for dyadic rationals which approximate sqrt(2) within precision 2^-k (within k-bits of precision) can be given by a recursive function f: |N -> |N
f(k) = least n [ n^2 > 2^(2k+1) ] for all k.
f(k):
2, 3, 6, 12, 23, 46, 91, 182, 363, 725, 1449, 2897, 5793, 11586, 23171, 46341, 92682, 185364, 370728,....
The idea of the function f is that for each k>0 it outputs the number of 1/2^k segments that fit into sqrt(2) plus one.
Since for each k, the value f(k) is the smallest integer such that f(k)/2^k > sqrt(2) we have
f(k)/2^k < sqrt(2) < (f(k)+1)/2^k for each k>0.
From this we obtain the error bound | f(k)/2^k - sqrt(2) | < 2^-k.
Conclusion:
Approximation of Sqrt(2) within precision 2^-k can be "represented" by a natural number f(k). To get the actual approximation by a dyadic rational just divide by 2^k.
Note:
This can be generalized to calculating the square root of any number and of any order.
QUESTION:
Can you give a Wang tile program for calculating the function f ?
http://grahamshawcross.com/2012/10/12/wang-tiles-and-turing-machines/
I was reading your quesion when browsing Research Gate questions. I am not too familiar with Wang tilings other than for having read a few papers attempting to Turing reduce tiling problems and a few papers on the so called EXPSPACE-complenetesss of the tiling problem...
But looking into the sequence you provided, I noticed the following pattern (unproven), that is, if you pairwise differentiate (discrete differentiation), you get:
1,.3
6,11
23,45
91,181
362,724
1448,2896
5793,11585
23170,46341
92682,185364
You'll notice the patterns 2x and 2x-1 recurring not periodically but almost with a phase shift. I didn't take the time to figure out the general iterated form. I wouldn't be surprise if the phase shift has a nice number theoretical rational.
But generally speaking, you get 2x plus or minus 1, the error bound. As the n-sequence grows large, your sequence takes an approximation error of O(n/2^n) if I am right.
If you see a Turing machine as the sequence of iterates f_i(x0)=x_(i-1)+r_i where x0 is a vector equivalent to the initial configuration of the tape and r_i the equivalent of machine operations in additive form, from the formula above, you would get an equivalent approximating Turing machine.
I read your linked paper and I think you would then have a way to convert the Turing machine to a Wang tile.
This being said, I am wondering if Wang tile programs could not take into account the error intrinsically.
All this said, I am not sure that the pattern (2x,2x-1) holds...
"Can you give a Wang tile program for calculating the function f ?"
I think that a "real world example" would require *A LOT* of work :-). However another approach, slightly different from the one suggested by Philon Nguyen, is 1) build an Universal Turing Machine with Wang Tiles, 2) build the equivalent TM program, 3) feed the Wang Tiles UTM with it
- Badges
- Science topic
- Similar topics
- Engineering
- Control Theory