Linked Questions

96 votes
9 answers

What would it mean to disprove Church-Turing thesis?

Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why? Turing, Rosser etc ...
user avatar
36 votes
8 answers

Alan Turing's Contributions to Computer Science

Alan Turing, one of the pioneers of (theoretical) computer science, made many seminal scientific contributions to our field, including defining Turing machines, the Church-Turing thesis, ...
62 votes
3 answers

Realizability theory: difference in power between Lambda calculus and Turing Machines

I have three related subquestions, which are highlighted by bullet points below (no, they could not be split, if you are wondering). Andrej Bauer wrote, here, that some functions are realizable ...
Blaisorblade's user avatar
  • 2,069
19 votes
3 answers

Why has hypercomputation research died down?

I see a lot of research on hypercomputation in the 1990's, but in more recent years there seems to be little work on the topic. Is it true that research in this area has died down? If so, what could ...
Velvet Ghost's user avatar
14 votes
2 answers

Landscape of interactive proof systems

My first question is whether an interactive proof system characterisation is known for all the classic complexity classes. I would call P, NP, PSPACE, EXP, NEXP,EXPSPACE, recursive and recursively ...
Vijay D's user avatar
  • 12.6k
-9 votes
2 answers

Is every "nontrivial" algorithm Turing-complete?

Recently there was a big response here to a question relating to the Church-Turing (from now on referred to as "CT") thesis [1]. this is another question that has nagged at me for close to ...
vzn's user avatar
  • 11k
4 votes
4 answers

Algorithm for finding similar images

If you go to FFFFOUND! and click on some image you will notice that on the new page, under the image, there is a section called "You may like these images." which suggests 10 images that look similar ...
please delete me's user avatar
1 vote
2 answers

Is true randomness and the physical Church-Turing thesis incompatible?

As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are ...
Christopher King's user avatar
1 vote
1 answer

Is multiprocessing possible on a Turing Machine? [closed]

I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on ...
user2707299's user avatar
0 votes
0 answers

mathematical study of the 'Church-Turing thesis'

The Church-Turing thesis postulates that essentially all models of computation -Turing machines, Post systems, lambda-definability etc yield the same class of computable functions. Now we can think of ...
Krishnan Narayanan's user avatar