Questions tagged [computability-theory]
The computability-theory tag has no usage guidance.
7
questions
1
vote
1
answer
59
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 ...
- 136
1
vote
1
answer
84
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 ...
- 123
1
vote
0
answers
58
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 ...
- 121
1
vote
3
answers
99
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 ...
- 121
2
votes
1
answer
77
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?
- 1,065
3
votes
4
answers
166
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 ...
- 1,920
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 ...
- 9,492