1
$\begingroup$

I am not a computer scientist and this is my first question.

This question is a question in layman terms and I also want the answer in layman terms.

When I searched hyper-computation. There was a list of models of hyper-computers.

Now, my question is that what are the problems with those models and if it is possible to create models of computers which can compute non-Turing computable things then doesn't, that already proves the Church-Turing thesis wrong and if it does prove that Church-Turing thesis is wrong then why people still consider it to be a thing?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

The Church–Turing thesis is about physically realizable machines. To the best of our knowledge, hypercomputation models cannot be realized in the physical world. They are a figment of our imagination.

If someone would find a new law of physics which enables solving the halting problem, that would make a big fuss in the world of science. But I am not holding my breath.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How would you feel if someone invents a model for physically realizable hypercomputer ?? $\endgroup$
    – Rounak Sarkar
    Jan 23, 2021 at 7:41
  • 1
    $\begingroup$ It’s unlikely to transpire. $\endgroup$
    – Yuval Filmus
    Jan 23, 2021 at 11:49
1
$\begingroup$

I'll just address one model. WP says: The Zeno machine performs its first computation step in (say) 1 minute, the second step in ½ minute, the third step in ¼ minute, etc. By summing 1+½+¼+... (a geometric series) we see that the machine performs infinitely many steps in a total of 2 minutes. We can imagine all kinds of devices. But, looking around, we see that researchers who want to study an idealization of a physically-realizable machine, in order to get insights into what is mechanically computable, do not find that studying these is fruitful.

Improve this answer
$\endgroup$

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.