What is the slowdown of a universal circuit compared to a Turing machine?

  • Level: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Circuit Universal
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
Sign up Log in
1 reply · 2K views
Dragonfall
Messages
1,023
Reaction score
5
A universal Turing machine is up to a log factor slower than the TM it's trying to simulate. What is the slowdown (depth increase, if any) of a universal circuit?

Thanks in advance for the help!
 
Last edited by a moderator:
Physics news on Phys.org

Discussion

Similar threads

Can Turing Machine Decidability Extend to Complex Algorithm Outputs?
  • mathmari
  • · Replies 1 ·
  • Set Theory, Logic, Probability, Statistics
Replies
1
Graduate N-dimensional Universal Turing Machine?
  • Loren Booda
  • · Replies 6 ·
  • Set Theory, Logic, Probability, Statistics
Replies
6
Undergrad Turing machine problem to getting startet
  • markonan
  • · Replies 1 ·
  • Set Theory, Logic, Probability, Statistics
Replies
1
Graduate Complement of Universal Turing Machine - Does this exist?
  • controlfreak
  • · Replies 4 ·
  • Set Theory, Logic, Probability, Statistics
Replies
4
Is a Turing machine that moves one cell per step Turing-complete?
  • 2sin54
  • · Replies 2 ·
  • AI and Computer Science
Replies
2
Is this number a Gödel number of a Turing machine?
  • mathmari
  • · Replies 3 ·
  • AI and Computer Science
Replies
3
Design an Infinite NTM for Any Input String: Turing Machine Question
  • leo0liver
  • · Replies 5 ·
  • Engineering and Comp Sci Homework Help
Replies
5
Insights P vs. NP conjecture and what is a Turing Machine (TM)?
  • fresh_42
  • · Replies 6 ·
  • AI and Computer Science
Replies
6
A brain-like implementation of a Turing machine
  • ShayanJ
  • · Replies 2 ·
  • AI and Computer Science
Replies
2
Help explain this Turing machine notation
  • mishima
  • · Replies 2 ·
  • AI and Computer Science
Replies
2