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

learn more… | top users | synonyms (1)

2
votes
0answers
61 views

Why is positional number system natural?

In the theory of computation, one mainly deals with maps $\Sigma^*\rightarrow\Sigma^*$. To discuss computation on other sets $X$ than $\Sigma^*$, one fixes a representation ...
1
vote
1answer
221 views

Proof of undecidability of $FINITE_{\text{TM}}$ and $USELESS_{\text{TM}}$

I came across these 2 problems about proving of undecidability of languages: $1$. $FINITE_{\text{TM}} = \{\langle M \rangle | M \text{ is a Turing machine and } L(M) \text{ is a finite language} \}$. ...
4
votes
1answer
683 views

Why doesn't diagonalization prove that integers are not countable?

I understand how Cantor's diagonalization argument works with respect to disproving that a bijection between integers and real numbers can exist. What I don't get is why the same reasoning doesn't ...
0
votes
1answer
177 views

Arithmetic Hierarchy problems

Is $\Sigma^{0}_n$ closed under intersection? I think yes m I correct? Let $L_1$ be an $\Sigma^{0}_1$ complete language, and $L_2$ be a $\Pi^{0}_1$ complete language, such that $\emptyset \neq L= ...
3
votes
1answer
56 views

A diophantine program for a basic For Loop

By Matiyasevich, every computable function has a diophantine representation. I am wondering if there is a general way to represent a simple iterative for loop. Specifically: Let $f(x)$ be any ...
3
votes
1answer
60 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: ...
4
votes
1answer
125 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 ...
-4
votes
1answer
249 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 ...
1
vote
1answer
59 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. ...
3
votes
1answer
113 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 ...
1
vote
1answer
87 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?
1
vote
0answers
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 ...
3
votes
1answer
122 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 ...
8
votes
1answer
136 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 ...
1
vote
2answers
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 ...
21
votes
3answers
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, ...
1
vote
1answer
196 views

Non-computable numbers and surreals

Can non computable numbers be expressed with surreal numbers? Show the construction using Conway's definition of surreal.
1
vote
0answers
79 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 ...
15
votes
1answer
498 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 ...
4
votes
1answer
158 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 ...
9
votes
5answers
558 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 ...
3
votes
1answer
133 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 ...
5
votes
2answers
146 views

Running programs in nonstandard models of PA

I came across the following problem in several places, to paraphrase: Let $T$ be a recursively axiomatizable, consistent extension of PA. Then there exists some $e$ such that the $e'$th program ...
2
votes
2answers
127 views

Theory vs. Deductive Theory

Looking through some notes on model and computability theory, I noticed that the definition of the term 'theory' changed between them; in particular, the model theory (based on Hodges' text) defined a ...
0
votes
2answers
155 views

Universal Turing Machine with an Oracle

(Note: For convenience, I'm phrasing this in terms of computer programs rather than Turing machines.) Consider computer program P which does the following: It asks the user to enter the code of a ...
2
votes
1answer
112 views

A few basic questions about the arithmetical hierarchy, mostly about terminology.

I was reading about the arithmetical hierarchy, and I have a few questions, mostly notational. For completeness, here's the definition given over at Wikipedia. The classifications $\Sigma_n$ and ...
1
vote
1answer
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 ...
2
votes
0answers
102 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 ...
6
votes
1answer
120 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" ...
5
votes
2answers
236 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 ...
0
votes
1answer
133 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 ...
2
votes
0answers
96 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 ...
3
votes
1answer
174 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.
1
vote
0answers
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 ...
1
vote
1answer
89 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 ...
4
votes
1answer
435 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 ...
1
vote
1answer
24 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 ...
5
votes
1answer
67 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 ...
3
votes
1answer
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 ...
2
votes
1answer
131 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 ...
2
votes
1answer
77 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 ...
4
votes
2answers
190 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 ...
6
votes
2answers
197 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 ...
8
votes
2answers
157 views

Decidability of the consistency for complete finitely axiomatized theories?

Let $\Phi$ be a finite set of first order formulas over a signature $S$. Assume that (we can prove that) $\Phi$ is complete, i.e. for each first order formula $\phi$ over $S$, we have $\Phi \vdash ...
2
votes
2answers
89 views

Computational power of arithmetically complex sets

When learning basic computability theory we are usually given as examples of arithmetic sets sets which are complete for their level of the arithmetic hierarchy (like the halting set, the set of ...
18
votes
1answer
987 views

How to interpret “computable real numbers are not countable, and are complete”?

On page 12 of this (controversial) polemic http://web.maths.unsw.edu.au/~norman/papers/SetTheory.pdf Wildberger claims that Even the "computable real numbers" are quite misunderstood. Most ...
3
votes
3answers
664 views

Complete theories - dense linear order

There are two things I would like to prove. DLO - Dense linear order is complete, that means that when $\psi$ is a sentence of the language $\{<\}$ then $DLO\vDash\psi$ or $DLO\vDash\neg\psi$ ...
1
vote
1answer
102 views

First order sentences and Halting problem recursively enumerable

I am just finding searching for some examples of recurisvely enumerbale models and I do not know how to prove that the following ones satisfy this property. Consider the set of first order ...
0
votes
1answer
179 views

Recursively enumerable properties

In my textbook are three interesting properties listed (which I would like to prove) (1) A is recursively enumerable iff A is the domain of a partial computable function (2) A is recursievly ...
11
votes
0answers
209 views

Reference on standard types

This question is about what I presume is a basic construction in type theory. The finite types are defined as follows: 0 is a finite type; if $\sigma, \tau$ are finite types, then so is ...