# Tagged Questions

Questions related to computability theory, a.k.a. recursion theory

9 views

### Run through the power of generators

Sorry to bother every one. I now get stuck about how to write a command to run through the following process. sage:v1=[-0.414213562373095, -0.275075988673055, -1.05169737482124, -5.21012399490145, 0....
9 views

### Is language L in R||RE/R||CO-RE/R||not in CO-RE or RE - any intuition/tips?

I have a test in computational models coming this Sunday, and it seems no matter how many questions from the type "is this language in R or RE or CoRE or not in CORE or RE" I solve, I always manage to ...
2k views

### Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?

On this site there are many variants on the question whether TMs can decide the halting problem, whether for all other TMs or certain subsets. This question is somewhat different. It asks whether ...
161 views

### Is C actually Turing-complete?

I was trying to explain to someone that C is Turing-complete, and realized that I don't actually know if it is, indeed, technically Turing-complete. (C as in the abstract semantics, not as in an ...
42 views

### Negligible functions in definitions of statistical closeness and computational indistinguishability

Statistical closeness implies computational indistinguishability. Is there any (simple) relationship between negligible function that is used in definition of statistical closeness and negligible ...
48 views

26 views

73 views

### Does every procedure have a structural equivalent?

Suppose I have a basic mathematical function like: $f(x) = x^2 + 2$ implemented in typed pseudo-code as: int f(x) { return x*x + 2; } If we were to break ...
68 views

### Universal lower semicomputable semimeasure and Coding Theorem

I'm following Li and Vitanyi's book "An introduction to Kolmogorov complexity and its applications" 3ed. I'll rewrite here the definitions I need for my question. The authors define the reference ...
30 views

### Are there any RE-complete languages w.r.t. polynomial reduction?

I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L$, meaning a polynomial-time reduction. I've tried to use $L=A_{TM}$ (the accepting problem), but got ...
18 views

### what is NP class? [duplicate]

I actually started to read complexity classes of problems. and I know that NP class include P class problems and even more problems call NP-complete ... as many books define NP class as well But I ...
2k views

### Can a RAM calculate its own Gödel number?

You can get the Gödel number of a RAM by making it a list of commands and making this list an integer. So, what I thought is something like "The RAM that would return its own Gödel number (say, $x$) ...
37 views

### Relating memory complexity and decidablity

Given a language $L_u$, about which we know that there exists a non-deterministic turing machine which accepts it (as in, implying $L_u \in RE$) with memory complexity of $c^{p(n)}$, where $c$ is a ...
44 views

### Can we write a program that can say if any 2 given programs do the same w.r.t input - output pairs

I'm new to theoretical CS research. I have the following question: Given 2 different computer programs, each generating certain outputs for a given set of inputs. Assuming we are given the range of ...
4k views

### What are very short programs with unknown halting status?

This 579-bit program in the Binary Lambda Calculus has unknown halting status: ...
36 views

### Can LOOP-Programm stop when its value goes below 0?

I am wondering, if in the LOOP programing language, whether instances of the LOOP x DO P END are defined to stop in the case $x < 0$. The definition only says "...
5k views

### Can Quantum Computing solve Problems not even a Turing Machine can solve? [duplicate]

In his book "The Fabric of Reality", Penguin Books 1998, p. 218, David Deutsch says that the first quantum computer (built 1989 in the office of Charles Bennet, IBM Reasearch) "became the first ...
### Is there a broader class of total functions than $PR$? [duplicate]
In total functional programming programs are restricted to total computable functions. A well-known class of total functions are the primitive recursive functions ($PR$). However the Ackermann ...