2
$\begingroup$

I posted a question about a month back regarding the significance of Turing machines (relative to other models of computation). In that post, I mentioned vaguely some conversion between an input string and a physical system as a model of computation. (I just got my BS in CS, so it's likely I have no idea what I'm talking about.)

Would the following be a valid, or at least meaningful, general model of computation:

Let $ f: Z \mapsto Z$ be a function. Then, $f$ is computable iff for all integers $a$, there exists a bijection $P$ from the integers to formal physical systems (Classical mechanics?), such that when $P(a)$ is "set into motion", it reaches and equilibrium or static state $s$ where $P^{-1}(s) = f(a)$.

If this makes sense, please let me know.

$\endgroup$
  • 1
    $\begingroup$ Your definition is not mathematical, since you haven't specified what a formal physical system is, and what happens when it is set into motion and reaches an equilibrium or static state. $\endgroup$ – Yuval Filmus Jun 23 '18 at 20:14
  • $\begingroup$ I know, but if you take those for what you think they mean, do you see what I'm trying to get across? $\endgroup$ – Alex Jun 23 '18 at 21:14
  • $\begingroup$ Let's say a physical system defined in the theory of classical mechanics. $\endgroup$ – Alex Jun 23 '18 at 21:14
  • 1
    $\begingroup$ Not really. An important aspect of models of computation is that they have a mathematical definition that allows us to reason about them. $\endgroup$ – Yuval Filmus Jun 23 '18 at 21:15
  • $\begingroup$ Well, by quantization, all physical quantities are really discrete. But then your system is pretty much equivalent to Turing machines and much harder to work with. $\endgroup$ – xuq01 Jun 24 '18 at 3:06
2
$\begingroup$

It would be meaningful, if you properly defined "formal physical system", "set in motion", and so on, in a mathematical way. Pretty much anything can be made meaningful in mathematics (which is what this sort of theoretical computer science really is).

The question is, is it useful?

It would seem that the functions computable by Turing machines are a subset of this new class, since you can make a Turing-complete physical computer with enough rolling marbles. (Or, if you allow transistors in your "formal physical systems", I could just use "my laptop at the moment when I run this Python code" as the system.)

Then, are there things your physical systems can do that Turing machines can't? Given that a Turing machine can simulate classical mechanics to arbitrary precision, given enough time and memory, I'm inclined to say no.

Finally, are your physical systems easier to work with mathematically? The answer seems like a pretty solid "no", given how much calculus is involved in classical mechanics, compared to the simple state-machine-plus-memory of a Turing machine.

So while you could in theory use physical systems to define computability, there doesn't seem to be an advantage to doing it this way.

$\endgroup$
  • $\begingroup$ The only reason I was thinking this way is because computation seems to equal a deterministic process. E.g., all our computers are such physical systems. (IDK if any of this makes sense) $\endgroup$ – Alex Jun 23 '18 at 22:02
  • $\begingroup$ Whether computation is necessarily deterministic is a deep question that enters the realm of quantum physics. As I understand it, part of the basis of the extended Church-Turing thesis is that there are problems where probabilistic algorithms can be efficient (i.e. solution computed in polynomial time) but known deterministic algorithms are not. That said, the relationships between the complexity classes P, PP, and BPP remain to be full understood. As an aside, a recent theoretical result gave evidence that BPP is a subset of BQP, which was attributed to quantum non locality. @Alex $\endgroup$ – Greenstick Dec 10 '18 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.