Although the Turing Machine is a theoretical model to describe computing power, in its basic idea today's computers are still (quite sophisticated) implementations of this basic concept, although you have random memory access and many ingenious optimisations to squeeze out as much performance as possible.

Anyhow, the computability is precisely the same as long as we don't hit the memory limit of a computer.

In Star Treks The Next Generation and Voyager we see lots of features and limitations of computer systems. For example, a hologram cannot be stored/copied as we would assume files can be handled in today's computers. The time a computation takes (whether it's on the ship's core or on Data, or whatnot) is also not always consistent with our intuition, which probably accounts for dramatic effect in particular scenes. Whenever "the computer needs time to compile the information" it's really an excuse to give the characters a chance to chat.

So, ultimately, is the core idea of the computers we seen in Star Trek (or more precisely on the NCC-1701-D, if you like) still a descendant of Turing's design, or is there a fundamental difference/innovation. Can these computers compute something a TM can't (e.g. decide the diagonal language on TMs)?

  • 1
    Star Trek's computer systems always seemed to have several "turing machine" style systems controlled by what could be described as a "lisp machine". Central processing is delegated to hardware or banks of general purpose processors. Astrometrics is driven by dedicated nagigation hardware (similar to modern GPUs) and many other systems have specific hardware processes built in. As always, this is my uneducated speculation. ...and only now do I realize the inspiration for this question. Commented Jun 23, 2012 at 2:40
  • There are also the gel packs, which seem like primitive neural networks. Commented Jun 23, 2012 at 3:17
  • 3
    From Wikipedia: The Turing machine is not intended as a practical computing technology, but rather as a hypothetical device representing a computing machine. So unless it's defined more precisely, I'd tend towards "yes"... Or "no": I mean, with random-access memory, we've gone beyond going forward/backwards on a tape already. Oh, and concurrent programming with multiple CPUs.
    – Izkata
    Commented Jun 23, 2012 at 3:18
  • 18
    The question shows a misunderstanding of what a Turing machine is. It is a purely theoretical construct and ANY computer can be modelled as a Turing machine, even neural networks. You seem to be confusing this with the "von Neumann architecture" or serial processing which most modern computers have. There has been some recent work trying to develop non-Turing computation, but they haven't been very successful. Commented Jun 23, 2012 at 6:37
  • 2
    @WilliamBSwift: No, I'm not. I'm mainly thinking about computability, really. The architecture, as I said, is very very remotely still based on a TM: You have a huge/infinite array of cells, and you can go modifying those. Whether you call these memory or tape is a minor distinction. We do have random access, yes, we do have parallel cpus, yes.
    – bitmask
    Commented Jun 23, 2012 at 12:45

5 Answers 5


Your second question seems to come down to whether Enterprise D's computer is capable of hypercomputation. The question boils down to whether physics allows compressing an infinite amount of storage into a finite space and/or completing an infinite number of computation steps in finite time and energy. Nothing we've seen in the Trek universe so far, even time travel, admits a theory of physics that allows either of those things, so I think the answer is no, Enterprise D is not a hypercomputer.

If that's true, then if you believe the Church-Turing thesis, Enterprise D has to be computer that can be simulated albeit slowly by a Turing machine, so the answer to your first question is yes.

  • 1
    Actually, Star Trek's worst episode ever does have an instance of compressing near-infinite amounts of information into a shuttle computer. But its canon is questionable, since not only is it never mentioned again, Paris specifically mentions that no one's gone Warp 10 in a later episode...
    – Izkata
    Commented Jun 23, 2012 at 19:45
  • 1
    @Izkata: Correction: the worst episode ever (even canonically!) is Code of Honor
    – bitmask
    Commented Jun 23, 2012 at 20:58
  • 1
    @bitmask: I think they had to recalibrate the scale for Threshold, which happned years after CoH. It just goes to prove there's always a new low to strive for.
    – Jeff
    Commented Dec 28, 2012 at 20:23

Since you want to limit the question to the Enterprise D; the "main computer" (which is actually a system of 2 redundant cores) uses isolinear chips and circuits to carry out the bulk of its tasks. These seem to conform to a traditional Turing machine, altough they are much faster than previous systems (such as duotronics).

In Voyager, we have gel packs, which are organic, and use what appear to be neural networks to carry out fuzzy logic.

EDIT: A non-cannon argument for quantum computers (which would not be Turing machines) is found in the ST:TNG Technical Manual. It says that "Each main core incorporates a series of miniature subspace field generators, which creates a symmetrical (nonpropulsive) field distortion of 3350 millicochranes within the faster-than-light (FTL) core elements."

I don't recall what the current knowledge of quantum computing at the time of TNG being produced was, so this might have been the writers trying to create a quantum computer without knowing what one was (which can be hinted at by the FTL processing).

  • What would make them a non-traditional Turing machine would be if they used quantum logic. I would assume that they do, but I can find no reference for it. See en.wikipedia.org/wiki/Quantum_Turing_machine Commented Jun 23, 2012 at 10:24
  • @BenHocking, the only references to uses of quantum effects are in teleporters and replicators. I would assume there are quantum computers in use (if not on ships, then at least for some other federation uses), but can't find a cannon example for the Enterprise D. Commented Jun 23, 2012 at 13:59
  • It's Enterprise-E that has gel packs, not D.
    – ewanm89
    Commented Jun 25, 2012 at 1:42
  • The subspace field generators the computer cores are essentially a mechanism to "overclock" it by increasing the signal propagation speed above the speed of light. They don't alter what problems it can compute or their time complexity.
    – smithkm
    Commented Oct 31, 2019 at 23:01

To answer your zeroth question, "Does the computer-system on the Enterprise NCC-1701-D still follow the basic architecture of a Turing Machine?" I would argue that no modern computer actually follows that architecture: modern computers are more accurately described as Von Neumann machines in that the program is stored, there is a distinct external storage, registers, program counters, etc. All modern computers have all of these basic building blocks and the Enterprise-D computer seems to have several of each.

In fact, the Enterprise-D computer would seem to be a massively parallel supercomputer with extremely fast access to an extraordinary amount of data (that, going by the reported data storage capacity of that computer seems also to be extremely well compressed).

Is the design of the Enterprise-D computer a descendant of Turing's design? Assuming it was designed based on Earth's principles of computer science and not, say, by Binars or Vulcans, I'd say yes: it'saVon Neumann machine and Von Neumann machines are descendants of Turing machines.

As pointed out by Kyle, the Enterprise -D computer is not a hypercomputer.

  • The Von Neumann architecture predates the Turing machine. There is no relationship (other than mathematical) between Turing machines and modern computers.
    – OrangeDog
    Commented Oct 30, 2019 at 10:41
  • @StopHarmingMonica IIRC, Turing’s article on the universal computing machine predates Von Neumann’s architecture proposal by almost a decade (1936 vs 1945 IIRC) and Von Neumann knew about Turing and his work. I agree that modern computers are nothing like the model Turing described, but “no relationship” is a bit of an exaggeration...
    – Ronald
    Commented Nov 1, 2019 at 2:22
  • 1
    my mistake on the dates, I thought it was ‘48
    – OrangeDog
    Commented Nov 1, 2019 at 8:25

Post singularity AIs are not depicted as benign because fiction needs an antagonist. It was Star Trek that perfected that concept with the borg.

Star Trek is a future look at our own society and considering we are 50 years from the singularity, they must be post singularity.

Aditionally using the dogma set fourth in TNG. Data is sentient and has far less capibility than the Enterprise computer. Furthermore, when ships are built the computer spends several months partnered with other similar ships so it can learn from them and get used to their bodies (the ship). The Enterprise was partnered with the USS Galaxy for its learning period.. . Being sentient doesn't mean acting luke a human. This also is a tool of fiction called personification. .

  • You don't seem to address the actual question (or I don't see it). Furthermore, I don't see where your claims about the development of the ship's computer are supported by canon sources.
    – bitmask
    Commented Dec 29, 2012 at 12:48
  • Its covered in the ST Technical Manual. The question asks if the computer is a Turing machine which means they are asking if it is an AI.
    – Phil
    Commented Dec 30, 2012 at 3:26
  • Turing machine and Turing test are not the same thing; both were invented by the same person, however.
    – Nick
    Commented Feb 19, 2013 at 12:13

I believe that we are failing to consider that the Enterprise-D computer is a post-singularity technology and as such is enlightened and therefore benign. Being enlightened it would inherently stay in a neutral state. This is why it only answers what it is asked. For example the captain may say 'computer can you please reconfigure the sensors and re scan for this variable?' The computer would have already been aware of this option and its outcome, however it would not volunteer the information without being asked. This is also why the computer does not try to save itself in the event that it is ordered to self destruct.

We have other examples of post-singularity enlightened technology. R2D2 and Marvin are both great examples. If you pay close attention to the Star Wars movies you will see that R2D2 is in all the major scenes and knows what is going on at all times, but, he never tells anyone. For example he is a mechanic and had the plans to the death-star in his memory banks, however he followed the suggestion from the humans that they ask the death-star computer how to deactivate the tractor beam. He could have just told them.

In the case of Marvin he knew what 42 meant the whole time. It didn't take him millions or billions of years to figure it out. Even though he did have billions of years to figure it out. The difference with Marvin was the GPP which made him suffer and as a suffering being he tried to tell everyone but no one would listen.

  • 4
    The ships in Star Trek are not sentient, and the Federation society is not post technological singularity. No idea where you even got "enlightened and therefore benign" from, as post singularity AIs typically aren't depicted as very benign...
    – Izkata
    Commented Dec 14, 2012 at 6:18

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.