# Tag Info

Accepted

### What is an 'effective' encoding?

Computability is not always defined using natural numbers. For instance Turing machines work with tapes, and the natural contents of those tapes are strings, collections of which are called languages. ...
• 4,253

### What is an 'effective' encoding?

There is no and there cannot be any a formal definition of this. For example, take for $D$ the set of graphs. There are many possible encodings of a graph as a natural number: for example, you could ...
Accepted

### Analytic sets vs recursively enumerable sets

Short version: see Chapter 3 of Sacks' book Higher recursion theory. Longer version: First of all, neither parallel is perfect. That said: I would argue that one of the major realizations of ...
• 250k
Accepted

### To what extent can Primitive Recursion perform wellfounded recursion?

Yes, your conjecture is true. In fact, primitive recursive functions can perform a huge variety of set-theoretic tasks, which makes primitive wellfounded recursion straightforward... Or at least, it's ...
• 2,211
Accepted

### Examples of index set not Turing equivalent to the Halting Problem?

No. This is because any non trivial index set must compute the halting problem, and the only c.e. sets that compute the halting problem are Turing equivalent to it. Let $I\subseteq\mathbb{N}$ be a non ...
Accepted

### Divergence defined w.r.t infinity? Or Divergence defined w.r.t there being a finite N s.t the iteration diverges at N? Mandelbrot Set.

Questions Define Mandelbrot sequences $f_{n\,;\,p}:=\begin{cases}0 & \text{ if }n=0\\\left(f_{n-1}\right)^{2}+p & \text{ otherwise}\end{cases}$. Here is my interpretation of possible intended ...
• 24.7k

### 'The' Halting Problem or Many Halting Problems?

There is a straightforward bijection between strings and natural numbers, so any algorithm on natural numbers can also be regarded as an algorithm on strings. Or, to put it another way, while you can ...
• 5,467
Accepted

### Questions on Effectively Denumerable Sets and Universal Programs in Computability Theory

I thought the same when reading the first fragment: the author is being informal in the definition of an effectively denumerable set. I'm going to offer an alternative formulation. Let an effectively ...
• 596
1 vote

### Abstracting the Undecidability of the Halting Problem

It's possible to abstract the structure of the argument. However, it's not really possible to do so correctly without knowing the details of arguments for specific systems. I've formalized two ...
• 4,253
1 vote

### Non-termination proof for all non-terminating algorithms?

First, the equivalence $\text{DoesNotHalt}(\text{alg}) \iff \lnot\text{Halts}(\text{alg})$ is constructively true, as $\lnot\exists x, P(x) \iff \forall x, \lnot P(x)$ is a tautology of intuitionistic ...
1 vote
Accepted

### Definition of a length function

Your example is wrong: by definition, we have $\langle 2, 0 \rangle = \langle 2, 0, 2 \rangle^3 = | 3, 2 | = 17$, and $(17)_2^2 = 2$ as expected. Note the definition of variable-length sequences, page ...
• 2,513
1 vote
Accepted

### $\omega$-consistency in Goedel's completeness

As mentioned in the comments, the issue is that when you assume $\mathbb N\models \sf PA,$ you are assuming full soundness of $\sf PA.$ This is stronger than assuming $\omega$-consistency, which is ...
• 60.6k
1 vote

### Is the following a good/accurate definition for an enumerator (a kind of Turing machine)?

I know I am late :-), but maybe I have a more formal solution for the exercise 3.4. For the definition of enumerator I would say: definition: An enumerator is a two-tapes Turing Machine \$E = (Q, \...
• 101

Only top scored, non community-wiki answers of a minimum length are eligible