$\begingroup$
$\endgroup$
2
Turing machines are defined over a discrete memory tape. Is it possible to use a continuous memory tape (i.e. symbolically) instead of a discrete one. Will such a machine be more powerful?
https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine comes up for general real number problems. Wikipedia even asserts that "BSS machines are more powerful than Turing machines". Are there any concrete BSS machines out there? Can someone explain how BSS machines work in a simple manner?
-
1$\begingroup$ BSS machines have a discrete tape just like a normal Turing machines. They allow reals to appear as contents of tape cells, not as tape position indices. It's quite unclear to me how you would want such a continuous tape to operate. $\endgroup$Emil Jeřábek– Emil Jeřábek2025年10月23日 13:48:06 +00:00Commented Oct 23 at 13:48
-
$\begingroup$ Let's think a band within the frequency domain. An impulse at x1 will be regarded as a True value (with a position of x1). Another impulse signal at x2. To calculate x1+x2 = x3, and this can be performed by a shift and element-wise Or. Namely, if we have x1=e and x2 =pi then x1+x2 will be e + pi exactly. This calculation can be performed with microwaves with enough resolution,, exactly when the computation is symbolic. So, Matlabs's symbolic toolbox is an example that ordinary machines can already perform e+pi. But how BSS machines are more powerful? $\endgroup$Yigit– Yigit2025年10月24日 13:10:36 +00:00Commented Oct 24 at 13:10