Can Turing Machines Be Represented by Polynomial-Sized Circuits?

Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
1 reply · 2K views
Dragonfall
Messages
1,023
Reaction score
5
How do you show that every polynomial-time turing machine has a family of equivalent polynomial-sized circuits?
 

Discussion

Physics news on Phys.org

Similar threads

Can Turing Machines Enumerate Union and Cartesian Product of Constructible Sets?

  • mathmari
  • · Replies 1 ·
  • Programming and Computer Science
Replies
1

Undergrad Can Turing Machines Understand Infinity?

  • Gear300
  • · Replies 14 ·
  • Set Theory, Logic, Probability, Statistics
Replies
14

Can Turing Machine Decidability Extend to Complex Algorithm Outputs?

  • mathmari
  • · Replies 1 ·
  • Set Theory, Logic, Probability, Statistics
Replies
1

Graduate How can Turing machines be used to model sets?

  • phoenixthoth
  • · Replies 12 ·
  • Set Theory, Logic, Probability, Statistics
Replies
12