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
0answers
21 views

simple questions on $TM$s runs lengths

Is it possible that the number of running steps in $TM$ that runs on word $w$ will be $0$? Is it possible that the number of running steps in $TM$ that runs on the empty word $\epsilon$ will be bigger ...
11
votes
1answer
440 views

Approximate spectral decomposition

A detailed attempt below. I am interested in effective and constructive computations for finding approximate spectral decompositions in some suitable format. Namely, let $A: H \rightarrow H$ be a ...
0
votes
0answers
61 views

Faster growing function than the fast growing heiarchy under Church-Kleene?

Is there a computable function that grows faster than any function in a fast growing hierarchy with index less than the Church–Kleene ordinal, where computable fundamental sequences are used? If the ...
0
votes
0answers
7 views

Simulating a k state Turing machine M would require a Turing machine M' that has some f(k) number of states

I am writing a proof for a problem, and in that proof, I am simulating a TM M that has k states and terminates after being started on a blank input. I want to show that to simulate M on a TM M', M' ...
0
votes
0answers
39 views

Prove that a certain intrinsic property of Turing machines is not decidable

Can anyone help me to prove that the following language is nod decidable? $$ A=\{\langle\,M,w,q\,\rangle\mid M \text{ is a $TM$ , $w$ is a word, $q$ is a state in $M$ and while $M$ runs on $w$ it ...
3
votes
2answers
53 views

Multiplicity of real numbers in a tuple with known cardinality decidable?

Given a tuple $(x_1, \ldots, x_n)$ of computable real numbers $x_1, \ldots ,x_n$ and its cardinality $|\{x_1, \ldots x_n\}|=d \leq n$, is it decidable which numbers have which multiplicity? In other ...
0
votes
0answers
42 views

Classifying languages

I'm working on understanding what kind of languages are decidable, recognizable, and co-recognizable. I came across this problem that I think will really help me but I'm still quite unsure of how to ...
1
vote
1answer
59 views

Decidable and Recognizable

I'm trying to work on this problem but I cant seem to find an approach to it: For any language L ⊆ Σ∗ define the language PREFIX(L) := {w ∈ Σ∗ | some prefix of w is in L} (a) Show that if L is ...
0
votes
1answer
23 views

decidable intersect undecidable

Hello I'm kind of having trouble with computability, so my question is I need to define af language A and B such that A is decidable and B is undecidable when I do $A\cap B $ is decidable. also ...
1
vote
1answer
47 views

Does this sketch proof that every formula is equivalent to one in the arithmetical hierarchy work?

In the lecture notes for my course, the arithmetical hierarchy is defined as follows: A formula is $\Sigma_0$ or $\Pi_0$ if every quantifier is bound; A formula is $\Sigma_{n+1}$ if it is of the ...
1
vote
1answer
97 views

Show that the following function is primitive recursive

Let $f$ be a function defined by \begin{array}{l} f(0)=1;\quad f(1)=2;\quad f(2)=3;\quad f(n)=0 \mbox{, for $n>2$} \end{array} How to show that $f$ is primitive recursive?
0
votes
0answers
21 views

Prove set L is recursive iff there is an increasing total computable function which it's range is L.

Set L is recursive iff there is an increasing total computable function which it's range is L. The function is on $\Sigma^{*} \rightarrow \Sigma^{*}$. And by increasing it means that if a comes ...
0
votes
0answers
21 views

Prove uncountability of set L that L and L' neither of which is recursively enumerable.

How do I prove that the set of all languages L on alphabet {0,1} that neither L or L' are recursively enumerable, is uncountable? Proving uncountability can be done through diagonalization like the ...
0
votes
1answer
36 views

proof that languages are/are not in RE (probably with mapping reduce)

Given $2$ languages: Let $u \in \Sigma^*$ (constant word). $A_u=\{<M> \big{|}\,\, u\in L(M) \text{ and M is TM }\}$ $B_u=\{<M> \big{|}\,\, L(M)=\{u\} \text{ and M is TM }\}$ I ...
1
vote
2answers
36 views

A semi-recursive infinite set is the range of some injective recursive total function

The wikipedia article for semi-recursive sets (formally titled "recursively enumerable sets") claims: A set S of natural numbers is called recursively enumerable if there is a partial recursive ...
2
votes
1answer
41 views

Ramsey theorems for the naturals and for general infinite sets

In reverse mathematics and in recursion theory, the infinite Ramsey theorems are usually stated in terms of coloring of $[\Bbb N]^n$. How do these (not) imply the Ramsey theorems for general infinite ...
1
vote
0answers
22 views

turing machine decidable description for the language

L = { | R is a regular expression that produces at least one word in {a, b} * which contains a symbol exactly 3 times} ...
0
votes
1answer
38 views

turing machine decidability language

I must show that this language is decidable but I think it's not {D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think I give a reduction from E(TM). I suppose that this ...
0
votes
0answers
47 views

AllTM is undecidable using recursion theorem

Basically I'm trying to prove that allTM is undecidable using recursion. I know that you basically suppose there is a decdier H for the language, you construct a TM M that get's own code, simulates H ...
0
votes
1answer
28 views

Showing a relation is primitive recursive, recursive, or semirecursive.

I am not sure what strategy to use to I should use to show this is primitive recursive. I believe I am to show all three cases: primitive recursive, recursive, and semi-recursive. The diagonal of $...
1
vote
1answer
26 views

Is image of recursive set under recursive function recursive? [duplicate]

Given $A$ - recursive set and function $f$ which is also recursive. Is $f(A)$ recursive? I think that it isn't recursive, but how to prove it?
0
votes
0answers
16 views

Prove by printing turing machine that RE closed under iteration

I do not know what is the formal name of printing turing machine in english, maybe "counter machine". This machine prints a whole language without any input. for example: counter machine that counts ...
0
votes
1answer
89 views

Prove claims about disjoint union and decidable/undecidable languages

Let $L\subseteq\Sigma^*$ decidable language and $A\subseteq\Sigma^*$. Let $B=A\sqcup L$ (a disjoint union). Prove: $1$. $B\in RE \Rightarrow A\in RE$ $2$. $B\in R \Rightarrow A\in R$ Thanks!
0
votes
0answers
50 views

Prereqisites for: Subsystems of second order arithmetic

As the title suggests, im wondering what the prerequisites for Simpsons book, Subsystems of... are? Unfortunately I cant find it in the preface. My background is a Bachelor in Philosophy and ...
3
votes
1answer
135 views

How are halting oracles related to set theory?

By the Curry Howard isomorphism, constructive type theory and computation are intimately related to mathematical logic and proofs. Moreover, type theory gives us a nice framework for describing ...
0
votes
1answer
37 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
293 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
56 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 {a1,...
1
vote
1answer
52 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
79 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
48 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
24 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
72 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
27 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
86 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
53 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
35 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
17 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
27 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
77 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; ...