Questions tagged [computability-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
11 votes
4 answers
3k views

What are the philosophical implications of the Halting Problem?

In a great answer, a community member gave the following proof sketch that the halting problem is undecidable: Proof that the halting problem is undecidable. If there were a computable procedure to ...
Joseph Weissman's user avatar
  • 9,582
3 votes
4 answers
172 views

Scrutiny on the definition of the Turing Machine?

Wiki states: A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Has this intuitive ...
More Anonymous's user avatar
2 votes
1 answer
82 views

Halting Problem Oracle

Halting problem is unsolvable. There is no method to solve it, so no human can solve it. So why is any theory utilising an oracle (which can solve halting problem) not simply nonsense?
Ajax's user avatar
  • 1,083
1 vote
3 answers
100 views

The Relationship between the Church–Turing Thesis and Physical Computation

Consider the following thesis (aka Church-Turing (CT) Thesis): Every function that can be calculated by an effective method is Turing-computable. Suppose there is a physical process that allows for ...
ASA's user avatar
  • 121
1 vote
1 answer
62 views

A universal construction on some data D

I am picturing a sequence of symbols S, of length L. The symbols are from alphabet A, with k distinct symbols. The symbols can repeat, there can also be 0 of a particular symbol in sequence S. This is ...
D J Sims's user avatar
1 vote
1 answer
94 views

Continuum and Choice sequence

I am reading a paper on Brouwer's intuitionism. It mentions that according to Brouwer, the concept of continuum is perceived as a whole by intuition. However, it also mentions setting up choice ...
Irene's user avatar
  • 123
1 vote
0 answers
62 views

Church-Turing Thesis and the human brain

A question on my homework: Imagine that scientists discover that the behavior of the brain can be completely described by some mathematical function. Given the Church–Turing Thesis, would this ...
ASA's user avatar
  • 121