# Questions tagged [computability]

Computability theory a.k.a. recursion theory.

403 questions
Filter by
Sorted by
Tagged with
10 views

1k views

### What happens when the Linz halting problem proof is based on simulation of the input?

Applying a Simulating Halt Decider to the Linz Halting Problem Proof Of course it is obvious that no halt decider H can possibly return a correct halt status for any input defined to do the opposite ...
101 views

### Deciding whether there are directed paths between two vertices of all possible lengths

I recently read a paper The presence of a zero in an integer linear recurrent sequence is NP-hard to decide by Blondel and Portier, in which they prove the statement The problem of determining for a ...
168 views

### Primitive recursive permutations

How to show that the inverse of a primitive recursive permutation of $\mathbb{N}$ is not necessarily a primitive recursive function?
190 views

### Does every computable function have infinitely many "non-padded" representations?

It's well-known that every computable function has infinitely many representations (when they're expressed via recursive functions, or programs, etc.). I'm trying to understand whether there are ...
280 views

### What kind of string is produced by successive application of argmax M

Fix a version of Solomonoff's universal distribution $\mathbf M$ and consider the following procedure for generating an infinite binary sequence $\omega$. Start with some $\omega_0$. Each subsequent ...
105 views

### By Gödel numbering, is the set of computable(partially) transcendental numbers an immune set, productive set? [duplicate]

Every Turing Machine computing(output) real number is encoded as a natural number, namely, admissible numbering. Then what is the set of computable (partially) transcendental numbers? Is it an immune ...
56 views

1 vote
132 views

### Complexity of analytic functions and integrals

There exist polynomial - time computable functions, log - space computable functions, and NC - functions. Given this: To which class do analytic elementary functions, including trigonometric ones, ...
1 vote
69 views

### Primitive recursion relative to a logical system

In various places I have read that the normally considered non-primitive recursive Ackermann function is primitive recursive in higher-order logic. It's claimed to be due to "Reynolds, 1985",...
9k views

### What's the simplest noncontroversial 2-state universal Turing machine?

I'm wanting to encode a simple Turing machine in the rules of a card game. I'd like to make it a universal Turing machine in order to prove Turing completeness. So far I've created a game state ...
62 views

### Complexity measures for semi-decidable problems

Is there any sensible complexity measure that makes sense to compare the "hardness" of undecidable semi-decidable problems? Time and space are of course not suitable, because they cannot be ...