6
$\begingroup$

There are devices that do not allow users to load any application they want on it, only run a limited class of applications approved by the device vendor.

Take an iPhone as an example where new applications are loaded (solely) from app-store and programs that would allow execution of arbitrary code by user (without permission of Apple) are not permitted (e.g. Flash).

Are such machines where users cannot execute arbitrary code on themselves still Turing-complete computers? Can they still be considered as universal Turing machines?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Interesting question, but more philosophy than science. I suppose the answer to whether an iPhone is Turing-equivalent depends on (a) how you let Apple's permission influence computability in your model and (b) how Apple gives or denies permission for pieces of code. I'm inclined to let the question stay open, but if the community or another mod decides otherwise, in fairness, that's probably to be expected. $\endgroup$
    – Patrick87
    Commented Jun 6, 2012 at 20:44
  • 2
    $\begingroup$ @Dave, mrm, Raphael Why was "Is iPhone turing complete?" closed? $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jun 6, 2012 at 22:53
  • $\begingroup$ Are you talking about "general purpose computers" in place of Turing completeness? The coming war on general computation (by Cory Doctorow) Note that the machine is restricted for users i.e. apple can still run whatever program they want to. $\endgroup$
    – Kaveh
    Commented Jun 6, 2012 at 23:43
  • $\begingroup$ similar to this question, Turing complete and computational power $\endgroup$
    – vzn
    Commented Oct 4, 2012 at 17:34
  • $\begingroup$ see also tcs.se, applicability of TCS in malware research and the concept of a "sandbox" $\endgroup$
    – vzn
    Commented Oct 4, 2012 at 17:36

4 Answers 4

Reset to default
5
$\begingroup$

First, Apple may wish to restrict applications, but in practice, all versions of the iPhone can be jailbroken: you can then upload arbitrary machine executables. Whether the phone vendor likes or dislikes that you jailbreak the phone is immaterial to evaluating its computing power. But, for the same of the argument, let's add the hypothesis that the iPhone is not jailbroken, and more generally that you only use the iPhone in ways that are approved by Apple.

Whether you can load your code without Apple's approval or not is not relevant. The iPhone is Turing complete if there is some way of programming every computable function and of encoding arbitrarily long inputs and outputs. Turing completeness doesn't say that the encoding has to be what you consider the most natural, which is to install arbitrary machine code.

There is a killer argument which shows that the iPhone, like any other computer, is not Turing-complete: it only has a finite amount of memory. Therefore, the class of computing power is that of a finite automaton, no more.

If the iPhone was allowed to rely on an external storage medium that allowed to store an arbitrarily large amount of data (finite, but whose length is not bounded by the input size), and if network access was allowed, then it would be Turing-complete. One way would be to browse a website containing a Turing machine emulator or other Turing-complete computation mechanism, with input being defined as typing in a form and output being defined as changing the content of the page.

There are other ways of encoding Turing machines that don't require network access or non-default apps to begin with. You would need an iPhone augmented with an infinite tape to pull it off, though, so such an encoding would have to specify how the tape is used in addition to the use of actual iPhone features.

For example, you can type arbitrary JavaScript in bookmarklets in the web browser. If we ignore the problem that a concrete physical device has a finite amount of memory, JavaScript is a Turing-complete language. If you treat the bookmarklet arguments as input and the target URL as output, you can implement a universal Turing machine. JavaScript cannot i nteract with all hardware devices, but as far as pure computing power is concerned, it is sufficient to perform any calculation.

Improve this answer
$\endgroup$
4
$\begingroup$

The iPhone has a Turing Machine App. Therefore, if it has an infinite amount of memory, the iPhone would be Turing complete.

But no general purpose computer is Turing complete because it has a finite amount of memory, which is insufficient to model the infinite amount of memory required by a Turing Machine.

If you were to have an infinite amount of memory, then the fact that Apple controls what can go onto the device only plays a role if they limit the amount of memory available to the TM App.

Improve this answer
$\endgroup$
1
  • $\begingroup$ If I was being pedantic I might prefer "unbounded memory" to "infinite memory". I suspect it doesn't make any difference in this case, but the general idea is that the former can store arbitrarily but not infinitely large amounts of data – not, for example, the entire binary expansion of pi. $\endgroup$
    – Ben Millwood
    Commented Jun 12, 2012 at 2:03
3
$\begingroup$

It depends on what system you are considering.

No:

One of the criteria that could/should/must be used for approbation from the device vendor would be that the program does something, at least sometimes. It reasonably implies that the program terminates on at least one input.

Unfortunately for a system to be Turing-complete means that it can simulate all computable functions and that includes the partial function that is defined nowhere. (i.e. that never terminates). Surely such a program would not be approved. Therefore Turing completeness is impossible.

Yes:

You could consider that you can build a system on top of the system for example if you can have an interpreter being approved (see Dave's comment) then you can compose it with an external tool to be able to compute every computable function (just input the Turing machine into it), including the nowhere-defined function, even though the interpreter is only one function and thus is not all computable functions.

Improve this answer
$\endgroup$
3
$\begingroup$

Just an additional comment to complement the good answers above:

... just check in the game section of your favourite smartphone, if you find a puzzle game that is PSPACE complete (my favourite is Sokoban) and the game has a level editor and a help option to automatically find the solution, then you have a (deadly weird) Turing Machine (with finite amount of memory)!!! :-D

Improve this answer
$\endgroup$

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.