3
$\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.

Improve this question
$\endgroup$
5
  • 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
    Commented Jun 23, 2018 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
    Commented Jun 23, 2018 at 21:14
  • $\begingroup$ Let's say a physical system defined in the theory of classical mechanics. $\endgroup$
    – Alex
    Commented Jun 23, 2018 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
    Commented Jun 23, 2018 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
    Commented Jun 24, 2018 at 3:06

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jun 23, 2018 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
    Commented Dec 10, 2018 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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