Skip to main content

Questions tagged [computability-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
2 answers
152 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: "...
TheMatrix Equation-balance's user avatar
1 vote
0 answers
40 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 ...
Yechiam Weiss's user avatar
1 vote
1 answer
65 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 ...
Julius Hamilton's user avatar
1 vote
1 answer
109 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
65 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
1 vote
3 answers
103 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
2 votes
1 answer
97 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,139
3 votes
4 answers
176 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
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,608