Questions tagged [computability-theory]
The computability-theory tag has no usage guidance.
9 questions
3
votes
2
answers
163
views
How can the quality of "something being very improbable" be used as a philosophical argument?
Do you understand Marcelo Gleiser's "colossal waste of time" reasoning?
Physicist Marcelo Gleiser objects to the notion that posthumans would
have a reason to run simulated universes: "...
1
vote
0
answers
62
views
Fodor's central systems in computability terms
According to Fodor, the mind is comprised of both peripheral systems that are modular (and thus can be computed), and central systems which are not modular (and thus cannot be computed).
On the ...
- 4,144
1
vote
1
answer
66
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 ...
- 3,924
1
vote
1
answer
128
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
83
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
117
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
113
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,168
3
votes
4
answers
177
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 ...
- 2,324
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,709