1
$\begingroup$

Well in many texts and places I have seen a called statement, which claims it self to the famous "Church Turing Thesis".

I have seen many texts say that based on Church-Turing Thesis :

"Anything that can be done by a digital computer can also be done by Turing Machine".

Peter Linz text roughly says that the thesis is :

"any computation that can be done by "mechanical" means can also be done by TM".

Linz even adds that mechanical term is not well defined. So TM can serve as a definition for mechanical machine.

A look in the Wikipedia says:

It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.

The Wikipedia indeed defines or considers Turing Machine to be that "mechanical" standard.

Googling about mechanical computation, results in the picture of a device something like this:

Mechanical Computer Mechanical Computer

Even Ullman text has a proof of equivalence of TM and modern computer using the simulation of instruction set... But there the authors make a twist by saying they assume their digital computer says "yes" or "no" for input given.

Sipser says:

The definition came in the 1936 papers of Alonzo Church and Alan Turing. Church used a notational system called the λ-calculus to define algorithms. Turing did it with his “machines.” These two definitions were shown to be equivalent. This connection between the informal notion of algorithm and the precise definition has come to be called the Church–Turing thesis.

Most of the problems that can be solved by a TM in fact can be solved by applying the algorithm mechanically by an actual human using pen and paper. Like given a graph, one can trace out the TSP tour using pen and paper by drawing it and marking out the path. Or given two integers one can find the sum using pen and paper.

So in that case are our modern computers more powerful than a TM ? What is this mechanical model?

Using modern digital computers we can play Super Mario. Though Mario is after all a program and runs on the processor. The graphics rendering algorithms are algorithms after all. And some texts says that the notion of algorithm comes from the concept of Turing Machine. But a TM cannot possibly produce audio/video.

Then why some people believe that TM is equivalent to modern digital computers ? Or could we somehow use a multi dimensional TM and use each cell as a pixel to produce a picture.... I doubt?

I have seen the question here but it does not answer my query.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ TM is a mathematical concept that gives us the ability to know what is undecdiable languages. We know computation because we know what is uncomputations. For example, Church-Turing thesis states that no matter what algorithms is in our world, then TM can simulate it. For example, you said that digital computer can play super mario, but super mario is a collection of many algorithms with physical device that all in all gives you super mario. You can if you like write all algorithms of super mario in TM model but it would be very boring job to do. $\endgroup$
    – YOUSEFY
    Apr 11, 2021 at 21:58
  • 1
    $\begingroup$ Also, we conjecture (this is why we called it thesis) that TM can simulate any computational model, but I'm not sure about digital computers, as you said some say yes and some say no. Mechanical process in TM model is step by step process. We can have parallel computation, quantum computation, many different model but all of them agree in that they halt after some steps. Each step is considered as a mechanical process. It is Church-Turing thesis is a thesis (and not a theorem) because we don't know if our understanding of the concept of mechanical process is right/wrong. $\endgroup$
    – YOUSEFY
    Apr 11, 2021 at 22:12

1 Answer 1

Reset to default
3
$\begingroup$

Modern computers are not more powerful than a TM.

The meaning/definition of "mechanical means" is not "a TM"; "mechanical means" refers to any step-by-step process that can be carried out in the real, physical world. For instance, it would include mechnical devices, electronic devices, a human following a procedure "mechnically", and so on.

Wikipedia does not define "can be calculated by an effective method" as "can be calculated by a TM". It doesn't define "mechnical" as can be calculated by a TM. Rather, it says that the Church-Turing hypothesis asserts that any computation that can be carried out mechnically, can be carried out by a TM. That's not a definition of what it means to carry out a computation mechnically -- that's a consequence of the Church-Turing hypothesis.

I think you are getting confused about the difference between a definition of computation, vs what the Church-Turing thesis claims/asserts/conjectures to be true about computation. The Church-Turing thesis is not intended as a definition of computation; it's intended as a statement/claim/assertion about computation. The Church-Turing hypothesis doesn't provide a formal definition of "effective computation" or "mechnical means"; it leaves that up to the intuition.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is what Wikipedia says about computation : Computation is any type of calculation includes both arithmetical and non-arithmetical steps and which follows a well-defined model (e.g. an algorithm).Mechanical or electronic devices (or, historically, people) that perform computations are known as computers. An especially well-known discipline of the study of computation is computer science. So now I understand as you said where I was having problem, where the thesis is not considered a definition but just a conjecture that any step by step working of a problem can be done by TM.Thanks! $\endgroup$
    – Abhishek Ghosh
    Apr 12, 2021 at 5:26
  • $\begingroup$ Also thanks for helping me with the meaning of the term mechanical in this context. The term is actually used in the sense, as in many mathematics texts which says : having said the steps, solving these types of problems is mechanical and can be easily done if the steps are followed. Now I can correlate. $\endgroup$
    – Abhishek Ghosh
    Apr 12, 2021 at 5:37
  • 1
    $\begingroup$ @AbhishekGhosh, good, you are welcome! Yup, that sounds right! $\endgroup$
    – D.W. ♦
    Apr 12, 2021 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.