Computational theory is the study of calculations. Important questions are: what can be computed? How quickly can it be computed? What requirements or abilities must a computer have?

learn more… | top users | synonyms

3
votes
2answers
81 views

Not Turing reducible = non-physical?

According to the following question, it is likely the physical universe can be simulated on a Turing machine. Is the universe isomorphic to a universal turing machine? If so, does this imply ...
5
votes
2answers
202 views

What exactly is it that Gödel is supposed to have done that an algorithm can't

I've heard a lot of people say that Gödel's proof shows that human intelligence somehow goes beyond what a computer could ever do. It's only ever been articulated to me very badly, though not for want ...
2
votes
6answers
193 views

Human Thinking versus Computer Thinking

I'm wondering about the fundamental differences between human thinking and computer thinking. And my questions are the following. Is it wise to consider all human thinking as algorithms? Would it be ...
1
vote
2answers
143 views

Computational counter-argument for solipsism

First let me elaborate the argument. Take a calculator (wolframalpha, google or other software tools may serve as well). Perform some very complex operation. Write down the operation and the result ...
0
votes
4answers
188 views

Determinism and P=NP

This one has been busting my brain for quite a while now. As far as physics currently tells us, we live in a world where the physical laws are inductive but not deterministic, because at some ...
6
votes
1answer
227 views

In what way is the lambda calculus stronger than first-order logic?

This wikipedia article on combinatory logic says that Combinatory Logic, Lambda Logic and Turing Machines are equivalent computationally, but that both of these exceed the expressive power of ...
1
vote
2answers
108 views

How does Lowenheim-Skolem theorem prove the relativity of mathematical models?

Stuart Shapiro mentioned in his book Thinking about Mathematics that Lowenheim-Skolem theorem showed the "relativity" of a model in mathematics. What does it actually mean? What does the phrase "to ...
2
votes
1answer
125 views

If the universe is a turing machine, must it be one without an oracle?

According to wikipedia, turing machines can be equipped with oracles that solve the halting problem; but then a new halting problem arises - whether machines equivalent to themselves ie with the ...
3
votes
2answers
332 views

What are the essential differences between Quantum & Classical Turing Machines?

The classical Turing machine comes in a variety of different flavours. The basic version is the one first outlined by Turing, the non-deterministic version allows finite branching at every computation ...
4
votes
3answers
223 views

Is the human mind equivalent in computational capacity to a Turing machine?

Is it possible to formally prove that the human mind is equivalent in computational capacity to a Turing machine? Some papers that were helpful to me in understanding this issue: Minds, Machines ...
4
votes
1answer
137 views

What are the philosophical implications of the fact that Rule 110 is universal?

I just read the Wikipedia article on Rule 110 and there was a short remark that the simplicity of that rule might imply that it can exist in physical systems in nature. "Physical systems may also be ...
2
votes
3answers
211 views

Succinct argument for the fundamental role of binary digits as information units

I will clear up the context of this question so that the potential answers can be effectively targeted towards what I'm looking for. Information (at least in the non-semantic, canonical sense of the ...
1
vote
3answers
216 views

Is reincarnation possible for a concious computer?

The physical substance of a computer can deteriorate and eventually stop functioning, but the immaterial program & its state can be transferred to another computer. Its conciousness is effectively ...
4
votes
6answers
765 views

How to understand numbers that become really large?

If we begin with a notion of number N that we denote F(N) as a function of time, can a decidable procedure exist on definability of the growth of numbers? Inspired by Tipler's Omega point and ...
3
votes
3answers
277 views

To be or not be—what would a conscious computer decide?

The Prometheus myth can be interpreted as consciousness being a burden. Camus used the myth of Sisyphus to debate the same issue. It is the theme of a famous speech from Hamlet. Heidegger talks of ...
14
votes
1answer
201 views

Computational ethics and a robot's ability to reason about morality from a consequentialist perspective

Gert-Jan C. Lokhorst has written a paper on "computational metaethics" (Computational Meta-Ethics: Towards the Meta-Ethical Robot), which explores the ability of formal systems (i.e. computers/robots) ...
2
votes
1answer
174 views

Problem of induction without i.i.d

In this paper of Aaronson's, a proof is given of Occam's razor by appealing to PAC learning. My understanding of Valiant's bounds for PAC learners is that it requires i.i.d. This is often a ...
5
votes
1answer
153 views

What role does “counting histories” play in Deutsch's critique of the “simulation argument”?

In his book The Beginning of Infinity, David Deutsch argues that there is a problematic assumption behind the simulation argument that "virtually all instances of us are in ... simulations and not in ...
6
votes
3answers
664 views

What is the best scientific argumentation against the Dust Theory?

The "Dust Theory", by Greg Egan, states that... ... there is no difference, even in principle, between physics and mathematics, and that all mathematically possible structures exist, among ...
15
votes
6answers
1k views

Is the universe isomorphic to a universal turing machine?

I often think about problems that require an understanding of the very essence of computation and its inherent limitations. So, my questions are as followed: Is the universe isomorphic to a ...