Math Is Fun Forum

potterRules

Member

Registered: 2012-04-25

Posts: 3

Turing machine

Hi

I think that universal Turing machine is needed in proof of Cook's theorem - correct?

Church-Turing thesis can be proven using universal Turing machine - correct?

I believe that both are correct.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,649

Re: Turing machine

hi potterRules,

Welcome to the forum!

Don't know whether this will help.

http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem

Bob

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

potterRules

Member

Registered: 2012-04-25

Posts: 3

Re: Turing machine

Thanks. Universal Turing machine is needed in proof of Cook's theorem - correct? - No. Because deterministic Turing machine is needed, not universal.  I was wrong.

Church-Turing thesis can be proven using universal Turing machine - correct? I still think that this is true.

potterRules

Member

Registered: 2012-04-25

Posts: 3

Re: Turing machine

My question is still open. Can someone please verify or deny these:

universal Turing machine is needed in proof of Cook's theorem - incorrect?

Church-Turing thesis can be proven using universal Turing machine - correct?