11
$\begingroup$

Does our PC work as Turing Machine? The model of a Turing Machine consists of infinite memory tape, which means infinite states. But suppose if our PC has 128 MB memory and 30GB disk it would have 256^30128000000 states and thus, it has finite states.

I know that we can write a type of program that, if during execution we run out of memory, will request to swap memory disk with empty memory disk and resume execution.

But what if we don’t swap memory disk, in this case is it right to consider PC as FA?

Improve this question
$\endgroup$
4
  • $\begingroup$ note even [large] disk is finite & therefore computation based on it can be represented technically as a FSM. very similar to this other question Turing complete and computational power $\endgroup$
    – vzn
    Apr 25, 2013 at 1:05
  • $\begingroup$ A computer isn't limited to internal memory; it can use external storage, too. $\endgroup$
    – reinierpost
    Oct 3, 2016 at 21:20
  • $\begingroup$ Nope, it works as a von Neumann machine. Also, $256^{30128000000}$ is closer to infinity than you might expect. $\endgroup$
    – Andrej Bauer
    Jun 12, 2017 at 20:35
  • 1
    $\begingroup$ Turing machines don't necessarily have an infinite amount of memory. They just have a sufficient amount of memory to do whatever you want to do. If you limit yourself to halting programs, a Turing machine may as well have finite memory. Either way, the amount of memory a turing machine will use at any given time is finite, although possibly increasing. Networked computers also have a finite, but possibly increasing amount of memory. $\endgroup$
    – DanielV
    Jun 12, 2017 at 20:59

4 Answers 4

Reset to default
13
$\begingroup$

You're right that physical computers have finite memory and so are not Turing-complete. There are other ways in which computability theory is not a good model for computing - it doesn't take into account time and memory constraints. Complexity theory was invented (perhaps) as a more realistic depiction of computing, but IMHO suffers from similar (but subtler) problems.

On the other hand, in order to mathematically study the capabilities and limits of computing, we need to use some abstraction which is unconstrained. That makes the analysis possible. Similarly, in statistical mechanics we assume that the number of elements (atoms or molecules) is so large, that the behaviour is close to the limit (that is, we let the number of elements tend to infinity). Studying computing from an asymptotic perspective has similar advantages, but sometimes is misleading. Here are some examples of the latter:

  1. In cryptography, exponential algorithms are sometimes feasible. If we choose the wrong security parameters, our encryption might be insecure even though it's "provably secure".
  2. Polynomial-time algorithms are supposed to represent efficient and feasible computing, but many of them aren't feasible. As an example, most sophisticated matrix multiplication algorithms aren't used in practice.
  3. Modern complexity theory is obsessed with worst-case performance, and cannot analyze heuristic algorithms which are used in practice. NP-hard problems are considered infeasible, yet they are being solved in practice all the time.

A separate issue is that real computers don't work like Turing machines at all. They work like RAM machines, which are a better abstraction for actual computing.

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

I think you've given the answer yourself already. If the main aspect you are concerned about is the (in)finity of states, then a Turing Machine as such only exists as "a hypothetical device".

No matter how much memory you'll give your PC, it will always be limited, hence you can find program that will run on a "real" Turing Machine, but not on this PC due to the bounded tape.

http://en.wikipedia.org/wiki/Turing_machine#Comparison_with_real_machines

Improve this answer
$\endgroup$
2
  • $\begingroup$ Turing machines have a potentially infinite number of states, but a universal Turing machine can simulate any Turing machine, while at the same time has a fixed number of states. $\endgroup$
    – Yuval Filmus
    Apr 23, 2013 at 12:30
  • 7
    $\begingroup$ @YuvalFilmus I think you're confused between states and configurations. All Turing machines have a finite number states, but due to their unbounded memory that can be in infinitely many configurations. Universal TMs too have only finitely many states, but might need unbounded memory to simulate their input-machine. $\endgroup$
    – adrianN
    Apr 23, 2013 at 13:29
1
$\begingroup$

At the time Turing machines were invented, computers were women who would execute calculations on scrap paper. That is the notion of computation Turing machines express. Their tape isn't part of them any more than scrap paper is part of a person performing calculations.

This is still a good model for computer-based calculation because the bounds on resources in computers are usually quite large. Inherently finite computation models only become useful when the number of possible states is very small.

Improve this answer
$\endgroup$
-1
$\begingroup$

A modern computer is Turing complete, generally this term is used with the exception of infinite storage device. In practice, the memory can be quite long. For example, along with being universal function approximators, recurrent neural networks with memory (and running repeatedly) are said to be Turing complete. Indeed, Neural Turing Machines take this idea to a stage further inferring simple algorithms.

Improve this answer
$\endgroup$
1
  • $\begingroup$ How does this answer the question? $\endgroup$
    – Raphael ♦
    Jun 13, 2017 at 4:42

Your Answer

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

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