# Tagged Questions

Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

211 views

110 views

96 views

### How are weakly universal Turing machines actually defined?

For what I know, the definition of a universal Turing machine is something along the lines of the following (of course, details might vary from source to source): A Turing machine $M$ is called ...
75 views

### Show undecidability by reducing from Hilbert's $10^{th}$ problem

To show that the existential theory of $\mathbb{Z}$ in the language $\{0, 1; +, \mid , \mid_p\}$ (where $x \mid_p y \Leftrightarrow \exists r \in \mathbb{N} : y=\pm xp^r$) is undecidable we have to ...
97 views

### How to find the shortest path of a graph in a turing machine

I'm reading about Turing machine and I saw some examples as: Let $M_{1}$ a Turing Machine and the language $B = \{w\#w \vert w \in \{0,1\}^{*}\}$, We want $M_{1}$ to accept if its input is a member of ...
109 views

### Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
523 views

### algorithm for solving diagonal quadratic equations over real or complex numbers

I found the following statement in the paper http://www.math.uni-bonn.de/~saxena/papers/cubic-forms.pdf (page 22, in the middle): For $\mathbb F\in\{\mathbb R, \mathbb C\}$ and $b, a_i\in\mathbb F$...
32 views

### Online Encyclopedia of continuous and/or computable real valued functions?

Background: Oeis OEIS, the online encyclopedia of integer sequences tabularizes functions from the natural numbers to the integers. It looks like most sequences they list are computable. Some are ...
29 views

### Can all computable numeric functions on church numerals in ski-combinator calculus be expressed using only completely evaluated terms?

Let a term in ski-combinator calculus be called "complete" if every primitive is partially applied (so all S's are applied to at most two arguments, all K's to at most 1, and all I's are not applied). ...
61 views

### Positive existential theory of an extension of the ring

When we know that the positive existential theory of a ring $R[x]$ in a language $L$ is undecidable, does it follow that the positive existential theory of $R[x,y]$ in the same language $L$ is also ...
53 views

### Induction Can't Prove Complexity?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
123 views

### What does “Turing-complete” really mean?

People talk about various programming languages or computational models being "Turing-complete." But what does that technically mean? The technical definition is buried under tons of informal "...
47 views

### Computability of determining whether an expression equals zero

Suppose we are given an expression composed of integers,$+, *, -, /,$ elementary functions $(exp, sin, cos, tan)$ and their inverses (and for simplicity, assume each argument to these functions is in ...
198 views

### Efficient algorithm for calculating the tetration of two numbers mod n?

I'm trying to study the algebraic properties of the magma created by defining the binary operation $x*y$ to be: $x*y = (x \uparrow y) \bmod n$ where $\uparrow$ is the symbol for tetration. ...
155 views

### Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$A_{0}(y)= y+1$$ $$A_{x+1}(0)= A_{x}(1)$$ $$A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
158 views

### Simplifying Relations in a Group

Let $K$ be the group generated by four elements $x_1,\cdots,x_4$ with relations that any simple commutator with repeated generator is trivial; for example, $[[x_2,[x_1,x_3]],x_3]=1$. As I have asked ...
315 views

### How to derive Church-Kleene ordinal

Crossing-out: (How does one prove the existence of Church-Kleene ordinal? Also, why is it labeled as $\omega_1^{CK}$? And why is it first ordinal not hyperarithmetical, and is the first admissible ...
22 views

44 views

### Is there any research on Diophantine Approximation with computable numbers

I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
99 views

### Properties of Ackermann's function

I want to show the following properties of Ackermann's function: $A(x,y)>y$. $A(x,y+1)>A(x,y)$. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$. $A(x+1, y) \geq A(x,y+1)$. $A(x,y)>x$. If ...
44 views

### Is the probabilitistic distribution of the digits in the Chaitin's constant computable?

The Chaitin constant can in principle be computed with exponential effort on each sucessive digit by brute forcing all programs of a given length and simply proving special theorems on each case that ...
48 views

51 views

### Decidability of a language

Let $C$ be a conjecture about natural numbers. Let $$S = \{n\in N: n > m \text{ where m is the first number found for which C is false} \}$$ Is $S$ decidable? If $C$ is true for all ...
33 views

62 views

### Clarification of the argument for the set of total recursive functions not being recursively enumerable?

I read that the set of partial recursive functions is recursively enumerable while the set of total recursive functions is not. Isn't the set of total recursive functions a proper subset of the set of ...
80 views

### Check that constructed recursive function proves that set is recursive.

Let $\forall\exists$-formula be any formula that looks like $\forall x_1...\forall x_m$$\exists y_1...\exists y_n \phi$, where $x_1...x_m, y_1...y_n$ - variables, $m,n \ge 0$ , $\phi$ - unquantified. ...
85 views

### Eager vs. lazy interpretation of recursive functions

One of the ways of defining the set of recursive functions is to define first a language $L$ by induction in the following way: $\mathsf{Z}^1 \in L$; $\mathsf{S}^1 \in L$; $\mathsf{P}^n_k \in L$ for ...