Our Thoughts On The [Extended] Church Turing Thesis!

Aditya Yadav
Nov 24, 2019 · 4 min read

What is the Church Turing Thesis?

The Church-Turing thesis states the equivalence between the mathematical concepts of algorithm or computation and Turing-Machine. It asserts that if some calculation is effectively carried out by an algorithm, then there exists a Turing machines which will compute that calculation.

In English for Laymen

Church Turing Thesis basically said (asserted) that if there is any physical process, or absolutely any computation using any algorithm, at all. Then a Turing Machine will be able to compute it.

In other words, anything computable in the physical world (in which we live) is computable by a Turing Machine.

Then, What is the Extended Church-Turing Thesis?

The Extended Church-Turing Thesis, or ECT, asserts that every physical process can be simulated by a “deterministic” or “probabilistic” Turing machine with at most “polynomial overhead”.

In English for Laymen

Basically the ECT extends the earlier assertion by adding “Probabilistic” Turing Machines to the statement.

And it adds that a Turing Machine will be able to do it in — Polynomial Time.

Lets understand why this happened?

Everyone started talking about Quantum Computing, which definitely wasn’t something which felt like deterministic, and rather more like probabilistic. So everyone thought maybe, maybe there is a chance Quantum Computing cannot be simulated/computed by turing machines. So we extended CT into ECT by adding the assertion that — everything in the physical world — can be computed by “deterministic” or “probabilistic” Turing Machines.

Aha,

And not only that, The Turing Machine will be able to do everything in Polynomial Time.

Then What Happened?

Everyone started saying — Quantum Computers will “Destroy” the Extended Church Turing Thesis. Because quantum computers will be able to do what no Turing Machine can ever do.

The Future Debate

Once we settle the if Quantum Computing will Destroy Extended Church Turing Thesis Debate.

We will probably look at “Super Turing” Machines or Oracle Machines, and see if they can “Destroy” the Extended Church Turing Thesis.

In English for Laymen

Basically after Quantum Computing, we will try to build physical computing machines and push the limits of Computability and see if we can build any machine which can do anything which a Turing Machine cannot do. If it can it will break the Extended Church Turing Thesis. If it can’t the Extended Church Turing Thesis Stands.

Settling The Debate By Automatski Once and For All

Quantum Computers can be efficiently and accurately simulated by Classical Computers. Hence the Extended Church Turing Thesis Stands.

But what about the future?

Can we ever build systems which can go beyond Turing Machines?

Automatski asserts No! Never!

Why?

Because the Entire Universe is a Simulation and its a O(N) Simulation. Hence anything that can be computed in the Universe can be computed on a Turing Machine (Automatski says on a Classical Computer)

Conclusion

Not only Quantum Computers can’t ever destroy the Extended Church Turing Thesis.

We can conclude that nothing in the future will even come close to Destroying the Extended Church Turing Thesis. Including but not limited to Oracle Machines, Super Turing Machines, Quantum Gravity Machines or anything else.

[Limited] Reference

About us

This is our website http://automatski.com

Please feel free to reach out to us on info@automatski.com at anytime with comments, questions or suggestions.

NirvanaThroughKarma

The transcendent state in which there is neither suffering, desire, nor sense of self, and the subject is released from the effects of karma and the cycle of death and rebirth.

Aditya Yadav

Written by

Millennium Inventor

NirvanaThroughKarma

The transcendent state in which there is neither suffering, desire, nor sense of self, and the subject is released from the effects of karma and the cycle of death and rebirth.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade