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)

0
votes
1answer
35 views

Not all recursively enumerable sets are recursive

Is there a simple explanation which says why this is? I'm not looking for a proof or anything that contains too many technical terms. I've come across the example of the Halting problem but I don't ...
3
votes
2answers
278 views

How can addition be non-recursive?

Tennenbaum's theorem says neither addition nor multiplication can be recursive in a non-standard model of arithmetic. I assume recursive means computable and computable means computable by a Turing ...
0
votes
1answer
54 views

How many Turing degrees are there?

So I know there are precisely $2^{\aleph_0} $ Turing degrees, but is there a proof of this somewhere?
2
votes
0answers
76 views

Relationship between Complexity and Computability

As a response to comments,i'd like to put it in an abstract way,hoping this will make things clearer: f is a well-defined function of countably many inputs:f(a1,...,an,...). For a set of n objects ...
1
vote
1answer
51 views

Omega-model of WWKL consisting of random reals

I've been trying to show, as an exercise, that over $\mathrm{RCA_0}$ weak weak Kőnig's lemma (WWKL) does not imply weak Kőnig' lemma (WKL). I've been working on it by constructing an $\omega$-model ...
1
vote
1answer
73 views

non deterministic turing machine for concatenation

Let $L_1, L_2$ decidable languages on deterministic single-tape TM $M_1$ and $M_2$. How can I build non-deterministic TM that decides $L_1L_2$? What should be the formal definition of $\delta$ (the ...
0
votes
1answer
46 views

Can we know the first few digits of Chaitin's constant?

Chaitin's constant ($\Omega$) is a non-computable real number. Intuitively, it is the probability that a random program will halt. In reality, the actual value of $\Omega$ depends on the encoding ...
0
votes
2answers
21 views

Why are recursive sets also recursively enumerable?

Why is this? I'm not necessarily interested in a full proof, but just a quick, simple explanation that makes sense as to why this is.
1
vote
1answer
68 views

Are all computable functions continuous or vice-versa?

A famous result in intuitionistic mathematics is that all real-valued total functions are continuous. Since the requirements for a function to be admitted intuitionistically is that it must define a ...
0
votes
0answers
20 views

Is there a universal Turing machine on arbitrary number of input variables?

I know that for every $n \geq 1$ there is a partial recursive (p.r.) function $\phi^{(n+1)}_{z_n}(e,x_1,...,x_n)$ such that $\phi_{z_n}^{(n+1)}=\phi_e^{(n)}(x_1,...,x_n)$, where $\phi_e^{(n)}$ is the ...
1
vote
1answer
93 views

confusion about decidability

I just read the following sentence: "[T]here is no effective decision procedure for determining whether or not an argument T/X is valid, where T is any subset of PA or RA and X is any sentence." I ...
0
votes
0answers
23 views

equivalent definitions of recursively enumerable sets

In some textbooks, a n-ary set R is defined as r.e iff there's it is a domain of a recursive function. In others, definition is restricted to case n=1 and a set is called r.e. if it is a range of ...
1
vote
1answer
26 views

Characterization of $\Delta^0_0$ (rudimentary) functions

A $\Delta^0_0$, or rudimentary, functions $\Bbb N^k \rightarrow \Bbb N$ is a function whose graph is definable by a bounded formula. Can this class of functions characterized by means of closure ...
0
votes
1answer
18 views

prove this $L$ is not regular?

Consider the language $L=\{a^{n!}\mid n\in\mathbb{N}\}$. I want to prove that $L$ is not regular using the Pumping Lemma. So far i assumed by contradiction that $L\in REG$, so it has a pumping ...
0
votes
1answer
84 views

Example of a recursive set $S$ and a total recursive function $f$ such that $f(S)$ is not recursive?

Browsing wikipedia, I stumbled on the following: "The image of a computable set under a total computable bijection is computable." Given the form of the theorem, there must be some example of a ...
1
vote
2answers
51 views

Are all computable numbers constructable after a countable number of steps?

While looking at another question on this site about constructable numbers I started wondering. If you can take a countable number of steps (possibly infinite) can you draw an interval of a length ...
1
vote
1answer
50 views

Is the theory of Algebraically Closed Fields decidable?

It's easy enough to show that the theory of algebraically closed fields of characteristic p is decidable (since its complete). But does it follow from this that the theory of algebraically closed ...
0
votes
2answers
42 views

Formal languages

Let language $L$ be denoted by the regular expression $a^*b^*$ What is wrong with the following “proof” that $L$ is not regular? Assume that $L$ is regular. Then it must be defined by a DFA with k ...
0
votes
2answers
33 views

formal languages and computability concepts

Prove whether or not language $L$ ={$a^pb^q : p ≥ 100$ and $q ≥ 100$ are fixed integer values, and $i ≥ 0$} is regular. I'm not sure how to prove this.
0
votes
1answer
34 views

Formal languages and Computability

Can someone please tell me how would you start proving this? Thanks Prove whether or not language L = {a^(p+qi) : p and q are fixed integer values, and i ≥ 0} is regular.
0
votes
0answers
16 views

Decidability of the theory of ACF [duplicate]

The theory of Algebraically Closed Fields without specifying the characteristic is incomplete. Why is it decidable ?
1
vote
0answers
25 views

Decidability of the set of axioms of Algebraically Closed Fields

The set of axioms of $ACF_p$ is infinite. Why is it decidable? Is there a way to decide given a number whether it is a code of some axiom of $ACF_p$
2
votes
1answer
68 views

Problems understanding proof of s-m-n Theorem using Church-Turing thesis

I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem: Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a ...
1
vote
1answer
23 views

Is there any procedure saying “this function is not obtainable without using recursion at least n times”?

It is known that $sum(x,y)=x+y$ is not obtainable from any compositions of basic functions $z,s,id^n_i$(zero, successor, projections) without using at least one recursion. also, $\times(x,y)=x\cdot y$ ...
0
votes
1answer
21 views

In recursion theory, is $\Sigma_{i=0}^y f(x,i,z)$ primitive recursive?

It is known that given ternary primitive recursive function $f$, the function $g$ defined as $g(x,y,z)=\Sigma_{i=0}^z f(x,y,i)$ is primitive recursive. I wonder if this formulation can be modified; ...
1
vote
1answer
32 views

Which language is decidable

Just been at the Math-exam. One question I was really unsure about, was this question - so I didn't answer it, as you get minus point if the answer is wrong. Does somebody know, what the right answer ...
0
votes
1answer
30 views

Definition of a recursive ordinal

I'm having trouble understanding the definition of reclusive or computable ordinal - Wikipedia defines it as follows: "...an ordinal $\alpha$ is said to be recursive if there is a recursive ...
1
vote
1answer
52 views

How is the non-existence of a solution proven?

I've been wondering how an argument that a solution to a particular problem doesn't exist is put together. For instance "Pour-El and Richards found an ordinary differential equation ...
0
votes
1answer
25 views

Given a formal system show that a variable contains more of one symbol than an initial part of that variable

Given a formal system[of 4 symbols: 0, 1, ( , ) ] with rules: You may write down 0 or 1 at any time. if strings s and t have been written down, you may write down (st). write ⊢s to mean that s can ...
1
vote
0answers
82 views

Intuitonism and metamathematics.

There are various reasons why one would want to reject the law of the excluded middle when doing "normal" mathematics, which I won't get to here, but accepting those, does the same reasoning hold when ...
1
vote
1answer
53 views

Image of a strictly increasing computable function is computable?

I'm trying to show that if $f:\mathbb{N}\rightarrow\mathbb{N}$ is computable and strictly increasing, then $f(\mathbb{N})$ (the characteristic function of its image) is computable. My problem is that ...
0
votes
1answer
47 views

Reduction to/from REC and RE language?

Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to ...
-2
votes
2answers
38 views

Proove that Unions and intersections of recursively enumerable sets are also recursively enumerable [closed]

How do I prove that Unions and intersections of recursively enumerable sets are also recursively enumerable?
0
votes
1answer
58 views

Showing set is undecidable with Turing Machines

I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w$ reversed whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the bracket ...
0
votes
1answer
88 views

Is the set of languages over an alphabet Σ missing k words from Σ* countable?

My original question is whether $\mathscr{L}$, the set of all languages over an alphabet $Σ$, each of which missing finitely number of words from $Σ$* is countable. I think I can prove the set is ...
0
votes
0answers
22 views

Finding the Primitive Recursive Function for the Rem Function

When trying to show the remainder function is a primitive recursive function as defined to be as below (Copied from Proof Wiki): $\operatorname{rem} \left({n, m}\right) = \begin{cases} 0 & : ...
0
votes
0answers
32 views

Queue automaton algorithm for accepting primes

What is an example of a queue automaton algorithm that accepts prime numbers, encoded as strings of prime length? For example, if the input is either of ...
8
votes
2answers
399 views

Intuitive meaning of the concept “computable”

My question is a follow-up question to this one: How to show that a function is computable? The original question was: Is the following function $$g(x) = \begin{cases} 1 & \mbox{if } ...
1
vote
2answers
67 views

Is there a way to prove that a Turing machine computes the function we designed it to?

Say we design a simple Turing machine that adds two numbers together. Is there any way to formally prove that the machine actually computes the function we 'know' it does? Is there a general method ...
0
votes
1answer
70 views

Is it possible to create a software to find formal proofs?

Let's say I have a Hilbert style system, with a few axioms and rules of inference, and I want to find a proof for some formula $\varphi$, is it possible to create an algorithm that would find a proof ...
1
vote
1answer
35 views

Emptiness and infiniteness decidable for recursive languages?

The problem of determining whether a recursively enumerable language is empty or infinite cannot be solved. The proof goes by reduction to the problem of decidability, which is known to be unfeasible ...
0
votes
1answer
33 views

There are infinitely many recursively enumerable subsets of the natural numbers which are not recursive

How do I prove this claim? I understand that there are countably many recursive as well as recursively enumerable sets, and that the natural numbers have uncountably many subsets.
1
vote
1answer
57 views

Every infinite recursive set has a recursively enumerable subset which is not recursive.

Is the above statement true? If so, how do I go about proving it? Another thing: Given two recursively enumerable sets $Q_1$,$Q_2$, I want to prove that $Q_1\backslash Q_2$ isn't necessarily ...
0
votes
2answers
150 views

(Enumerable) set of natural numbers might not be effectively enumerable

It is well known that a set of natural numbers, although trivially enumerable, might not be effectively enumerable. I am trying to understand this fact intuitively. What is the decisive element in the ...
2
votes
1answer
33 views

Direct constuction of nonlow noncomplete c.e. sets

How can one construct a noncomplete nonlow c.e. set? (Background: I've been trying to construct, as an exercise, a nonlow low$_2$ set, but I do not know what kind of requirement is adequate for ...
2
votes
1answer
37 views

Does the existence of uncomputable functions imply that a theory is incomplete?

For example Kolmogorov complexity is uncomputable and Chaitin used that fact to prove incompleteness. If this is not the case, can you give me a counter example? Set of axioms is countable.
0
votes
0answers
29 views

A subset of $ \mathbb{N}$ is recursively enumerable iff it is the range of some recursive function from $\mathbb{N }$ to $\mathbb{N}$.

I know how to prove the converse of the statement, but given a recursively enumerable set, I don't know how to find such a recursive function. Also, how to prove that the function can be chosen as ...
0
votes
0answers
37 views

all recursive functions are turing computable

I'm studying with the book computability and logic(boolos). In chapter 5, the theorem is proved, indirectly, by showing that (recursive => abacus) & (abacus=> turing). But I want to prove ...
0
votes
0answers
41 views

Strange use of sigma notation in computability

Ok everyone, so I was reading about computability when I came across the following- ''Suppose that $f(x, z)$ is any function; the bounded sum $\sum_{z<y} f(x, z)$ is a function of $x, y$ given by ...
0
votes
0answers
32 views

A. A. Markov's paper on insolubility of the homeorphy problem [duplicate]

I am aware that this has been asked before, but the paper is nowhere to be found online, the provided link in the old thread leads to nowhere, and I'm really at wits end to find this paper, can anyone ...