Over nearly 20 years (!) of such comments, your aggressive ignorance has proved itself about the most impenetrable of any I’ve ever seen. Thus, now that I’ve explained the matter for anyone else who might be reading, all further comments from you will remain in moderation.

]]>Consider $$\text{Syr}'(n) = \frac{n}{2^{\lceil k/2 \rceil}}, n \text{ even; } 3n+1, n \text{ odd}$$ with \(k\) defined to be the maximal power of 2 dividing \(n\). I believe we can create a rewriting system implementing Syr’. The standard Collatz function takes $k$ steps to get from an odd number to an odd number; your function S takes (I believe) \(\lfloor\frac{k+1}{2}\rfloor \) steps; Syr’ takes ~\(lg(k)\) steps. Likewise, your rewriting systems take \(k\) steps to commute a trinary digit through a string of \(k\) f’s, and this system would take \(O(lg(k))\).

Here is the idea behind the rewriting system. Retain your symbols \(\langle,\rangle, f,t,0,1,2\); add symbols [,],u,d,S,H,x,y. We write \(n\) again as before in mixed binary/trinary with f,t,0,1,2, surrounded by \(\langle,\rangle\). However, M sequential f’s will be represented as f[M-1], with M-1 written in binary using bits u,d.

So instead of “f”, we have “f[]”, and instead of “fffff” we have “f[udd]”. Add a rule \([d \rightarrow [\) to get rid of leading 0s.

Now we drop the rules \(f0 \rightarrow 0f\), \(f1 \rightarrow 0t\), \(f2 \rightarrow 1t\), \(f\rangle \rightarrow \rangle\).

We instead have $$]0 \rightarrow 0], u0 \rightarrow 0u, d0 \rightarrow 0d, f[0 \rightarrow 0f[,$$ $$u]1 \rightarrow uSH]0t, d]1 \rightarrow dSH]0t, f[]1 \rightarrow 0t,$$ $$u]2 \rightarrow uSH]1t, d]2 \rightarrow dSH]1t, f[]2 \rightarrow 1t,$$ $$uS \rightarrow dy, dS \rightarrow Su, [S \rightarrow [x, yu \rightarrow uy, yh \rightarrow e, xu \rightarrow x, f[xH] \rightarrow e,$$ $$u]\rangle \rightarrow ]\rangle, d]\rangle \rightarrow ]\rangle, f[]\rangle \rightarrow \rangle.$$

The characters x,y,S,H implement a binary decrement Turing machine; the presence of the H prevents multiple decrements from happening at once. The last set of rules implements the \(n\) even case of Syr’.

Now, this already represents a partial speedup. To get the full speedup we would want a binary *adder*, so some \(O(lg(M+N))\) sequence of rewrites could take “f[M]f[N]” to “f[M+N]”, and do so without having issues with substrings of the form “f[M]f[N]0”, “f[M]f[N]1”, “f[M]f[N]2”, “f[M]f[N]f[P]”.

]]>https://www.quantamagazine.org/why-is-quantum-computing-so-hard-to-explain-20210608/

]]>Non-fungible tokens (cryptocurrency that is unique, like signed collectibles) is now all the rage in crytocurrency community. Could there be unique quantum states, such as an unknown quantum state prepared by an encrypted process/algorithm? ]]>