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)

3
votes
1answer
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: (...
4
votes
1answer
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 ...
-4
votes
1answer
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 ...
1
vote
1answer
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. ...
3
votes
1answer
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 ...
1
vote
1answer
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?
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
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 ...
8
votes
1answer
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 ...
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
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.
1
vote
0answers
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 ...
15
votes
1answer
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 ...
4
votes
1answer
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 ...
9
votes
5answers
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 ...
3
votes
1answer
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 ...
5
votes
2answers
151 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
130 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
158 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
113 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
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 ...
6
votes
1answer
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" ...
5
votes
2answers
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
3
votes
1answer
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.
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
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 ...
4
votes
1answer
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 ...
1
vote
1answer
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 ...
5
votes
1answer
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 ...
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 fact,...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
4
votes
2answers
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 ...
6
votes
2answers
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 ...
8
votes
2answers
158 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
1k 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
700 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
103 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 sentences....
0
votes
1answer
189 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
211 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 $\sigma\...
0
votes
1answer
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 ...
4
votes
3answers
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 ...
32
votes
4answers
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 ...
3
votes
1answer
243 views

Books on computational complexity

Can anyone recommend a good book on the subjects of computability and computational complexity? What are the de facto standard texts (say, for graduate students) in this area? I've heard a thing or ...
2
votes
1answer
111 views

Application Church-Turing thesis

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