# Our Thoughts On The [Extended] Church Turing Thesis!

# 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 LaymenChurch 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 LaymenBasically 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.