We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [computability]

Computability theory a.k.a. recursion theory.

Filter by
Sorted by
Tagged with
10
votes
1answer
327 views

Is predicting (in the limit) computable sequences as hard as the halting problem?

Question: Is predicting (as defined below) computable sequences as hard as the halting problem? Elaboration: "Predict" means successfully predict, which means make only finitely many errors on the ...
17
votes
5answers
3k views

Can a computer simulate itself as part of a simulated world?

Let's say you build a computer that will calculate the state of all atoms in the Universe at certain future point in time. Because the Universe is, by definition, everything that exists (and anything ...
15
votes
0answers
1k views

Can a Penrose tile cellular automaton be Turing-complete?

This question was based on an incorrect premise ... see Colin's comment below. Forget it. This was inspired by the discussion on this Math Overflow question. First, I need to define our terms. In a ...
40
votes
4answers
3k views

Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

This is a question related to this one. Putting it again in a much simpler form after a lot of discussion there, that it felt like a totally different question. The classical proof of the ...
5
votes
2answers
3k views

Are there other computer architectures apart fom the von neumann /turing architectures?

Are there other computer architectures apart from the Von Neumann /Turing architecture?
10
votes
1answer
221 views

Uniform hierarchy of problems that span complexity and computational hierarchies

Does anyone know of a set of problems that vary uniformly and span one of the "interesting" hierarchies of complexity and computability? By interesting, I mean, for example, the Polynomial Hierarchy, ...
4
votes
3answers
518 views

Is one definition of the word paradox, “something that can be used to prove the halting problem undecidable?”

I've been toying recently with the idea that the set of all "real-world" paradoxes...such as the Liar's Paradox, Russell's Paradox, the Unexpected Hanging Paradox, the Berry paradox, etc. ......
16
votes
2answers
2k views

What do we know about restricted versions of the halting problem

(UPDATE: a better formed question is posed here as the comments for the accepted answer below show that this question is not well-defined) The classical proof of the impossibility of the halting ...
0
votes
1answer
1k views

Question about Mapping Reductions (Clarify Example)

I cannot for the life of me wrap my head around these reductions. Specifically, the example I'm wrestling with: ...
28
votes
6answers
2k views

Maximum computational power of a C implementation

If we go by the book (or any other version of the language specification if you prefer), how much computational power can a C implementation have? Note that “C implementation” has a technical meaning:...
26
votes
4answers
1k views

Is there a non Turing-complete model of computation whose halting problem is undecidable?

I cannot think of any such model, maybe some form of typed lambda calculus? some elementary cellular automaton? This would almost disprove Wolfram's "Principle of Computational Equivalence": ...
29
votes
4answers
3k views

Can a probabilistic Turing machine solve the halting problem?

A computer given an infinite stream of truly random bits is more powerful than a computer without one. The question is: is it powerful enough to solve the halting problem? That is, can a ...
3
votes
0answers
191 views

Reference Request: Oracle applications outside cryptography

Oracles have been used to prove results in cryptography where all parties have access to a random oracle instantiated with some cryptographic primitive. I am looking for references to papers that have ...
9
votes
5answers
913 views

Writing universal recursive function [closed]

Is there a short explicit construction of an universal recursive function? All definitions I have seen involve numbering of Turing machines in some way, which is possible yet seems hard and ...
27
votes
6answers
2k views

How are real numbers specified in computation?

This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real ...
2
votes
3answers
596 views

Template Metaprogramming and Turing Completeness

I am trying to design a Turing Machine using C++ Template Metaprogramming. What steps must be taken to ensure that the code that I'm gonna write will actually build a Turing machine ? I have read that ...
19
votes
5answers
2k views

(False?) proof for computability of a function?

Consider $f(n)$, a function that returns 1 iff $n$ zeros appear consecutively in $\pi$. Now someone gave me a proof that $f(n)$ is computable: Either for all n, $0^n$ appears in $\pi$, or there is ...
12
votes
3answers
240 views

Is there a natural restriction of VO logic which captures P or NP?

The paper Lauri Hella and José María Turull-Torres, Computing queries with higher-order logics, TCS 355 197–214, 2006. doi: 10.1016/j.tcs.2006.01.009 proposes logic VO, variable-order logic. This ...
8
votes
3answers
449 views

Repeated Quine program

A Quine is a computer program which produces a copy of its own source code as its only output. Is there any Quine program that could print itself out n times, with n specified some way in the program?
6
votes
1answer
600 views

Definition of a monotone machine.

There is a definition of a 'monotone machine' in Li & Vitany's Book, and another one which is for example stated in this paper via c.e. (computably enumerable) sets. I can't see why these ...
8
votes
2answers
374 views

Relativization with Respect to Non-Recursive Oracles

In the paper Relativizations of the P = ? NP Question, Baker et al. showed that there are relativized worlds in which either P = NP or P ≠ NP holds. All oracles in their settings were recursive sets. ...
27
votes
4answers
5k views

Church's Theorem and Gödel's Incompleteness Theorems

I have recently been reading up on some of the ideas and history of the ground-breaking work done by various logicians and mathematicians regarding computability. While the individual concepts are ...
39
votes
7answers
4k views

Truly random number generator: Turing computable?

I am seeking a definitive answer to whether or not generation of "truly random" numbers is Turing computable. I don't know how to phrase this precisely. This StackExchange question on "efficient ...
7
votes
2answers
795 views

Universal Turing Machines in “Computational Complexity” by Papadimitriou

The first part of this question has been solved (see comments). In the book "computational complexity" by Papadimitriou, a Universal Turing Machine is given. But this machine is not concrete, in the ...
48
votes
2answers
7k views

Realizability theory: difference in power between Lambda calculus and Turing Machines

I have three related subquestions, which are highlighted by bullet points below (no, they could not be split, if you are wondering). Andrej Bauer wrote, here, that some functions are realizable ...
6
votes
2answers
599 views

Computable function $f = \Theta(g)$ with $g$ uncomputable

This question most likely has a simple answer; however, I do not see it. Let $g:\mathbb{N} \rightarrow \mathbb{N}$ be an uncomputable function and $c$ a positive real number. Can there be a ...
20
votes
2answers
898 views

$\ell_p$-norm preserving Turing machines

Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine. For people working ...
3
votes
2answers
690 views

Is the following language in RE?

There's a computability theory exercise that had me stuck for a long time. I have the language L={ M | there exists a reduction from HP to L(M) } I managed to ...
14
votes
1answer
2k views

What are the classic papers from the recursion theoretic area of complexity theory?

Two papers I would include are: D. Kozen, "Indexing of subrecursive classes", STOC, 1978. R. Ladner, "On the Structure of Polynomial Time Reducibility", JACM, 1975.
14
votes
3answers
1k views

Is there a complexity theory analogue of Rice's theorem in computability theory?

Rice's theorem states that every nontrivial property of the set recognized by some Turing machine is undecidable. I am looking for complexity-theoretic Rice-type theorem that tells us which ...
38
votes
9answers
19k views

What is the difference between non-determinism and randomness?

I recently heard this - "A non-deterministic machine is not the same as a probabilistic machine. In crude terms, a non-deterministic machine is a probabilistic machine in which probabilities for ...
49
votes
5answers
19k views

Relationship between Turing Machine and Lambda calculus?

Is there a relationship between the Turing Machine and the Lambda calculus - or did they just happen to arise about the same time?
15
votes
3answers
718 views

Can it be determined if language L lies in NP?

Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?
83
votes
10answers
14k views

What would it mean to disprove Church-Turing thesis?

Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why? Turing, Rosser etc ...
33
votes
4answers
860 views

Correspondence between complexity classes and logic

I took a class once on Computability and Logic. The material included a correlation between complexity / computability classes (R, RE, co-RE, P, NP, Logspace, ...) and Logics (Predicate calculus, ...