0
$\begingroup$

I took an extremely interesting intro to CE course, learning about transistors/memory/logic gates up to LC-3 assembly. Something that was really interesting to me was learning about how a processor's frequency is its speed, determined by the clock signal (if anyone can point to a link of how a clock cycle is made/works or explain, highly appreciated) but my main question is about his claim that any turing-complete computer can accomplish the task of another - performing the same binary operations, just in different amounts of time - that the processor doesn't matter. This depends on memory, though, right? A modern video game wouldn't be able to run on a 64 KiB computer, so I'm wondering if when the textbook and my prof make that claim, it's simply referring to the frequency of the clock cycle (and assuming unlimited/uncapped memory). Thanks!

$\endgroup$

migrated from stackoverflow.com Apr 2 '18 at 21:02

This question came from our site for professional and enthusiast programmers.

  • 2
    $\begingroup$ Turing-completeness is about what you can compute, not how fast you can compute it. No real computers are Turing complete, because they don't have infinite memory, so they can't perfectly simulate or be equivalent to a classic Turing machine moving over an infinite tape. But within the limits of memory, LC-3 can do anything that a modern x86 can, just slower. en.wikipedia.org/wiki/Turing_completeness $\endgroup$ – Peter Cordes Mar 31 '18 at 20:24
  • $\begingroup$ Put graphics capabilities aside for a moment, and yes everything is computable. But some tasks can't wait, like for recording the mic audio. One big jump in tech at this time was audio capabilities. See how is made numeric audio, bitrate, samplerate, it's good stuff to learn. Basically an audio card is a realtime numeric oscilloscope, to say the least! This was not doable without a minimum cpu speed $\endgroup$ – Cryptopat Mar 31 '18 at 20:30
  • 3
    $\begingroup$ Your clock signal question is not an SO question, but it is simply a periodic pulse signal which regulates and synchronises a computer's logic timing. The concept is general to many (synchronous) digital electronics applications, not just computer processors. en.wikipedia.org/wiki/Clock_signal $\endgroup$ – Clifford Mar 31 '18 at 20:37
  • 2
    $\begingroup$ You can build a 2 KiB machine to take 2 people to the Moon and safely return them to Earth. But you can only do that six times and the amount of effort and money that took was staggering beyond belief. Doing it 7 billion times does take better hardware. $\endgroup$ – Hans Passant Apr 1 '18 at 0:55
  • $\begingroup$ Re. Hans Passant: Apollo was reasonably cheap. It was only ~£150B (inflation adjusted). The F-35 programme is ~£400B and counting. And that's only 2% of US GDP anyway (even if you built all of them in one fiscal year) $\endgroup$ – Paul Uszak Apr 2 '18 at 22:56
4
$\begingroup$

The key considerations are infinite memory and unlimited time. If those two considerations were met, then all modern computers are equivalent. Since no real computers have infinite memory, and no real humans can afford to wait forever for a calculation, that equivalence is more conceptual than real.

$\endgroup$
3
$\begingroup$

The concept of Turing Complete is purely about data manipulation rules (i.e. a computer's instruction set), not its memory capacity. A machine is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine. A Turing machine is conceptual and has infinite memory. All real machines are necessarily constrained by actual memory.

Your question is answered directly in the Wikipedia entry on Turing Completeness in the section Comparison with real machines

The proposition put forward in the class/lecture you have attended is that both the LC-3 and a modern processor both have instruction sets capable of implementing a Turing Complete machine - what both lack however is the infinite memory and infinite time. Instruction sets and higher-level programming languages are often described as Turing Complete in this context.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy