# 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).

62 views

### Can this simple functional language be simplified further without losing any computational power?

Here is a definition of a very simplistic programming language (it is not Turing complete). Input to a function is any natural number. The following functions are primitive to the language: (...
130 views

### Decidable & Recursive predicates

Let $C$ be a decidable predicate in the language of arithmetic HA, that is $$\vdash (\forall \underline x)\: C(x) \vee \neg C(x).$$ $C$ is recursive if there exists a computable characteristic ...
250 views

### How does 3-sat work in laymen's terms?

I know only basic math like so: (+,-,x,\,). And I studied a little bit of programming up to the point of knowing a little bit about Boolean values.I desperately want to understand the 3-sat question ...
63 views

### Partially correct algorithm for a decidable problem

$D$ is decision problem whose inputs are the natural numbers. Suppose $A$ is an algorithm to solve $D$ in which we know that it is: partially correct for all inputs halts on all inputs >= 1000. ...
114 views

### Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this

Suppose we have a computable function $f$, say over the naturals, and a decidable set $S$ of naturals, such that $f(x) \in S$ for all $x$. In this case, for any specific $x$, there is some specific ...
89 views

### Why SKI when SK is complete

Why people talk about SKI calculus when S and K combinators can be used to create any other combinator including I?
56 views

### A diophantine definition of the Kleene star

Let $f(x \, | \, y_1, \dots, y_n)$ be a Diophantine polynomial that generates the Diophantine set $F$. By Matiyasevich, the set $F^*$ (Kleene star of $F$) is also Diophantine. My question: how can ...
127 views

### Showing the Rec is $\Sigma_3^0$-complete

In Soare's Computability Theory and Applications, he gives a very quick proof that the following set is $\Sigma_3^0$-complete: $$\text{Rec} := \{e \mid W_e \text{ is recursive}\}$$ It's fairly ...
138 views

### Does an undecidable decision problem have a ZFC-independent instance?

Is it true that every undecidable decision problem has an instance whose solution is independent of ZFC? For example, let $G$ be a finitely-presented group with undecidable word problem. Does there ...
1k views

### Is the function, calculating square root of natural number — computable?

My question is about domain of the term "computable". Consider Turing machine, that calculates square roots of natural numbers. If it gets 4 then it prints out ...
5k views

### Are there any examples of non-computable real numbers?

Is this true, that if we can describe any (real) number somehow, then it is computable? For example, $\pi$ is computable although it is irrational, i.e. endless decimal fraction. It was just a luck, ...
197 views

### Non-computable numbers and surreals

Can non computable numbers be expressed with surreal numbers? Show the construction using Conway's definition of surreal.
84 views

### Systematic way of creating the complement of a regular grammar?

Regular languages are closed under complement. And any regular language can be generated using a regular grammar. Is there a systematic way to create the rewrite rules for the complement of a regular ...
518 views

### Explicit automorphisms of the field of algebraic numbers

The field $\overline {\bf {Q}}$ of algebraic numbers admits many automorphisms other than conjugation. This follows from Galois theory: the field $\overline {\bf {Q}}$ can be realized as the union ...
193 views

### A Turing machine for which halting is outside ZFC

If, given Turing machine T, "T halts" or "T doesn't halt" could be derived from axioms of ZFC, halting problem would be in R. As it isn't, there must exist a Turing machine for which truth or ...
575 views

### A computer's memory is finite, so how can there be languages more powerful than regular?

A computer has a finite memory. There are no computers with infinite memory. Therefore the only languages that a computer can process are those whose member strings are finite. As I recall, the ...
134 views

### Why do complex grammars require powerful algorithms?

I am reading a fabulous book on Formal Languages and in the book it says: As the rewrite rules of a grammar become more complex, the algorithm for recognizing the associated language becomes ...
151 views

61 views

### Computability text emphasizing the arithmetical point of view?

I learned here that A set is recursively enumerable if and only if it is at level $\Sigma^0_1$ of the arithmetical hierarchy. Is there an introductory text in computability theory that takes ...
104 views

### Acceptable numbering of partial computable functions required to be one variable?

Soare in a yet unpublished textbook (I happened to be in a class taught by one of his former graduate students where we were field-testing a rough draft of his new textbook) Computability Theory and ...
124 views

### Ackermann function and $f_\omega$

The Wikipedia page of Ackermann function states that Ackermann function is "roughly comparable" to $f_\omega$ in fast-growing hierarchy. Is there some standard way to make the "roughly comparable" ...
244 views

### Random reals and Martin-Löf randomness

My questions are about the relationship between the following notions of randomness: A real $r$ is random over the model $M$ if $r\notin B$ for every null Borel set $B$ coded in $M$. A real $r$ is ...
134 views

### Let F be a function from $N ^{n} \longrightarrow N$. Show that if F is computable/ recursive then its graph is computable

Let F be a function from $N ^{n} \longrightarrow N$. Show that if F is computable then its graph is computable. According to the definition of computable/recursive I am looking at, a relation is ...
98 views

### Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete

Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete This is a question from Soare's Recursively Enumerable Sets and Degrees. I have little idea how to ...
181 views

### If P=NP, then NP = coNP. Why is this so?

I read that if we assume that P = NP, then NP = coNP. I am unable to understand why this is so.
50 views

### Regular Functional Algorithms

A language is regular if it is accepted by a read-only Turing machine. I am curious about applying this model to functional problems rather than decision problems. Definition: A functional read-only ...
90 views

### Density of PA degrees

As suggested by Carl Mummert, I will ask a separate question (this question was posted but then deleted). The following letters $a, b, e,\ldots$ denote Turing degrees. We say $a\gg b$ if there exists ...
469 views

### How to prove primitive recursive functions are definable in Peano Arithmetic?

Background: I'm working on a talk that presents Godel's first Incompleteness Theorem from a computability-theoretic perspective. The idea is to show that the first incompleteness theorem follows from ...
26 views

### Show how the Diophantine sets are closed under concatenation.

It follows easily from Matiyasevich's Theorem that the Diophantine sets are closed under concatenation. I am trying to figure out the mechanism by which they are closed under concatenation. In other ...
68 views

### Omitting Types… recursively

I'm working on the following problem at the moment: Let $\mathcal{L} = \{R\}$, where $R$ is a binary relation symbol. Let $T$ be a consistent, decidable $\cal{L}$-theory, and let $p(x)$ be a ...
65 views

### Complexity of index sets in nonprincipal ultrafilters

Let $U$ be a nonprincipal ultrafilter on $\omega$. It can be shown that the set $I = \{e \mid W_e \in U\}$ (where $W_e$ is the $e$th r.e. set in some given enumeration) cannot be $\Delta_2^0$ (in fact,...
135 views

### What does noncomputable really mean?

I believe I understand the definition of a noncomputable problem from an introductory computer science class, but I don't understand what it really means. One of my hypothesis was that a ...
78 views

### Regarding playing an infinite number of games that could last infinitely long amounts of time

So after watching the last Stanley cup game, a problem popped up in my head for which I have no solution. Say we have a game, like a hockey game, that has the possibility of going on forever. Of ...
195 views

### How do we know that every halting Turing Machine can be expressed as a recursive function?

I've hear many times that a major result in Recursion Theory is the equivalence of Turing and Godel's models: the functions implementable on a Turing machine are precisely the functions that can be ...
201 views

### Undecidability of the halting problem

One can prove by reduction from the special halting problem $H_S$ the undecidability of the (general) halting problem $H$. Is the converse also possible? That is, is it possible to prove the ...
158 views

72 views

### Tally method to build a machine (on paper, Turing Machine

Consider function $q$: For any even integer $x\ge0$ (including $0$): $q(x) = 4x$ I want to design a machine (on paper of course) to compute q under the Tally system. Another restriction is that when ...
401 views

### Book on lambda calculus logic and type theory

Can someone recommend me a book for self study which will cover topics of logic, lambda calculus and type theory. I know about "Computability and Logic" written by Bolos but it describe recursive ...
1k views

### Why do we believe the Church-Turing Thesis?

The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to ...
I would like to give examples of problems which are solvable with an algorithm, for example the function $f$ which maps the tuple $(n,m)$ to the greatest common divisor. This map is recursive. I would ...