Search Results

This problem is Turing equivalent to the constant problem (see also Wikipedia-constant problem), but it is open whether this problem is decidable. The constant problem is the problem of determining wh …

Let me propose a candidate: Kolmogorov complexity is not computable. That is, there is no computable procedure that, given a finite sequence $s$, produces the size of the smallest program (with respec …

The question whether $(p,q,n,s)\in R$ in any instance can be expressed as a sentence in the language of the structure $\langle\mathbb{R},+,\cdot,0,1,<\rangle$, a real-closed field, and by Tarski's the …

Update. As noted in the comments, this answer applies only to definable quotients of $\mathbb{N}$, rather than $\mathbb{N}^d$, and so it doesn't answer the question. The answer is yes, your relatio …

I like this question very much. Before answering, let me try to explain the question in my words. You are considering the structure $\mathbb{C}[t,e^{\lambda t}]_{\lambda\in\mathbb{C}}$, which is the …

As Timothy Chow pointed out, the OP's question is most naturally formulated as a promise problem: given a finite system of equations and inequalities in finitely many variables and the promise that it …

The first thing to say is that for a statement to be independent of some axioms means really two things, namely, that it is consistent with those axioms, and also that the negation of the statement is …

$\newcommand\Con{\text{Con}} \newcommand\Dec{\text{Dec}}$ Let $F$ be the formal system in which the proofs are to be carried out, when it comes to your formal assertions of the form $\Dec(\varphi)$. …

Furthermore, the procedure $\bar\varphi\mapsto R_\varphi$ is effective, regardless of the decidability of $T$. …

What you cannot do while remaining under the decidability result is quantify over the integers or the rational numbers. …

So the point is that you shouldn't consider such arbitrary enumerations when asking decidability questions about finitely presented groups, but rather you want to ask about decidability questions for the …

The answer appears to be no. Consider first the case of the anchor-tile periodic tiling problem, where we insist that a particular anchor tile is used. Let's modify the usual Wang tile argument, due …

If you want to determine truth in this language with real or complex entries, then Yes. All this is expressible in the language of real-closed fields, simply by using components, and is therefore expr …

When I teach computability, I usually use the following example to illustrate the point. Let $f(n)=1$, if there are $n$ consecutive $1$s somewhere in the decimal expansion of $\pi$, and $f(n)=0$ oth …

Goedel did indeed use the Chinese remainder theorem in his proof of the Incompleteness theorem. This was used in what you describe as the `boring' part of the proof, the arithmetization of syntax. Con …