New answers tagged

1

The Church-Turing thesis is a kind of axiom that links an informal notion of "computation by pen and paper method" to a formal definition of a turing machine model. It has been proven that many different formal machine models can simulate each other and therefore satisfy the same informal notion of computation. They have been proven to be ...


5

I'll address just the first part of your question. Neither the Church–Turing Thesis nor the Extended Church–Turing Thesis is a purely mathematical or formal statement. You phrased the C–T Thesis as, "There exists no computation model capable of recognising languages that a Turing Machine cannot." I would recommend not phrasing it this way, because ...


Top 50 recent answers are included