0
$\begingroup$

Church-Turing thesis states that any effectively computable process is computable by a TM. Let's assume for now that it means that every physical machine is computable by a TM. Let's call it A.

Now if this process has an unbounded number of states (for example we could think of an engine in a car and take the geographic coordinates of the car as its states) we could say that A is also Turing complete.

And therefore Turing equivalent.

Edit: Let's try to see more precisely how A could be considered as Turing complete even if the physical is continuous. Let's for example consider a car moved by an engine. And let's consider a planet where towns' names are built with the classic alphabet A, B, C etc. following rules that make the number of towns on that planet potentially infinite or unbounded. Now let's imagine that my vehicle is programmed by an algorithm to drive from town to town indefinitely. Let's call these towns the states of my system. Now I am certain (but please correct me if I am wrong) that my physical system is indeed Turing complete - and not just a push down automaton. Now if you accept that any state an observer (typically a physicist) will use to describe a physical system can be coded in a finite alphabet i.e. an integer (even if the physical world is continuous) then surely we could use the vehicle experience to say that in human eyes the physical world is Turing complete.

Is that correct?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ No. Unfortunately for you, the devil is in the details. You don't get to paint with broad strokes to define equivalence. If you want to show something is turing equivalent, you should show how it would simulate an actual TM. NB: An answer to this question will not resolve your previous one. $\endgroup$
    – Nicholas Mancuso
    Commented Sep 7, 2016 at 0:36
  • 3
    $\begingroup$ 1. Please don't use "Edit:..."; instead, write your question to read well for someone who experiences it for the first time. I encourage you to edit the question accordingly. 2. Usually you should try to avoid making edits that change the question in a fundamental way that invalidates existing answers. If you find yourself doing that, it usually indicates that the original question wasn't sufficiently clear, so you should take more effort to make your question precise and clear the first time. $\endgroup$
    – D.W. ♦
    Commented Sep 7, 2016 at 17:57
  • 1
    $\begingroup$ Plus, this platforms works really badly for ongoing discussions or teaching sessions. Since it seems you want to talk these things out, I recommend you seek out a trained computer scientist in the real world, or visit Computer Science Chat. $\endgroup$
    – Raphael
    Commented Sep 7, 2016 at 22:36
  • 1
    $\begingroup$ The last car example makes no sense to me -- if something is Turing-complete, I must be able to program that something. If the car simply wanders from town to town, how can I program it to compute, say, the factorial? To stress the point: a basic calculator, even with unlimited digits, is not Turing-complete - I can't program it. $\endgroup$
    – chi
    Commented Sep 8, 2016 at 13:10
  • 1
    $\begingroup$ @Jerome But that likely means that the car has a Turing equivalent computer on it. The cities look irrelevant now. Worse, if you assume the car can implement any transition system between infinite cities, then you went far beyond Turing -- you can implement any natural-valued function (uncountably many), and not only the computable ones (countably many). $\endgroup$
    – chi
    Commented Sep 9, 2016 at 7:36

2 Answers 2

Reset to default
1
$\begingroup$

No. You can't just sweep everything under the rug like that. The answer depends on what model of reality / physics you subscribe to.

If your model of reality is continuous (e.g., Newtonian physics), then it's not necessarily true that that every physical machine is computable by a TM. TM's are discrete, not continuous; if physics is actually continuous, then your assumption is probably not correct. (It might be true that the outcome of a process can be computed to an arbitrary degree of accuracy by a TM, but that's a subtly different statement. TM's compute discrete values, not continuous values.)

If your model of reality is discrete and finite, then it might be true that that every physical machine is computable by a TM. But now the number of states is not unbounded.

You can't have it both ways. Or, to put it another way, you can't just assume things without justification.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What about discrete and infinite? That's the assumption we use to justify TMs, isn't it? $\endgroup$
    – Raphael
    Commented Sep 7, 2016 at 9:34
  • $\begingroup$ Some stuff I assume obvious are not. Sorry for the confusion. I have edited my question $\endgroup$
    – Jerome
    Commented Sep 7, 2016 at 16:17
  • $\begingroup$ @Raphael, not following you -- can you elaborate? The output of a TM is always discrete and finite. If your model of physics says values are continuous, then no, you can't assume that an TM can output those values (e.g., output the location of an object after a certain amount of time -- you can't just assume that a TM can do that, if the location is a continuous value). $\endgroup$
    – D.W. ♦
    Commented Sep 7, 2016 at 17:55
  • $\begingroup$ @D.W. Going from infinite-continuous to finite-discrete seemed like a huge leap to me, in particular since our TCS-world is infinite-discrete. TMs can attain an unbounded number of different states! (In theory. We can't built those, of course, but that doesn't seem to be the issue here.) $\endgroup$
    – Raphael
    Commented Sep 7, 2016 at 22:39
1
$\begingroup$

Pushdown automata have unbounded inputs and (potentially) unbounded stack size, hence also an infinite state space. They are still not Turing-complete (not even close).

Improve this answer
$\endgroup$
0

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.