Talk:Techno
An alternative Turing-completeness proof for Ambient Techno
Here's an implementation of Tip in Ambient Techno (hardcoding the same example program as is used on that page):
[1,1,4,196608,1,16,1,1,0,3,1,16,1]<0><[0]*[[0]%6*2+1]/[[0]%6*2+2]>
We have a Tip program on the left (representing rationals as pairs of integers; "halt" is encoded as 1/0, which neatly triggers one of Techno's halting conditions), and an implementation of Tip's OISC commands on the right. (The two occurrences of "6" encode the repeat length of the Tip program, but otherwise the expressions are completely independent of the program.) It is obviously possible to encode arbitrary Tip programs in this form, thus Ambient Techno must be Turing-complete.
I like this construction because it's basically a ZISC design; you can use fixed expressions that implement a ZISC, and just store the program in memory along with the data. (However, arbitrary ZISCs are a little hard to encode in Techno because it can only modify one memory element at a time, and many ZISC constructions require modifying more than one element per step.)
This can trivially be modified into a TCness proof for regular Techno, by either undoing the steady increment of cell 0, or simply not using that cell at all. --ais523 12:11, 7 July 2020 (UTC)
- Now I've written that, it crosses my mind that the "6" could be stored in the memory array, giving an expression pair that's completely independent of the program:
[1,6,1,4,196608,1,16,1,1,0,3,1,16,1]<0><[0]*[[0]%[1]*2+2]/[[0]%[1]*2+3]>
- Untested, but should work, and give an Ambient Techno implementation of Tip that lets you change the program by changing only the memory array. --ais523 12:18, 7 July 2020 (UTC)