Questions related to computability theory, a.k.a. recursion theory

learn more… | top users | synonyms

-1
votes
1answer
27 views

Decidability Turing Machines

Let $\Sigma$ be an alphabet, and suppose that $A$, $B \subseteq \Sigma^*$ are Turing recognizable languages where both $A \cup B$ and $A \cap B$ are decidable. Prove that $A$ is decidable. Is this ...
0
votes
1answer
24 views

When reducing from HALT, can you create a Turing machine that asks whether a simulation stops?

Lets say I am doing a reduction from $\mathrm{HALT}_{\mathrm{TM}}$ to another language $S$, in order to prove that $S$ is not decidable. For this I need to build a new Turing machine, $M'$. Can I ...
-4
votes
0answers
39 views

LOOP-EVEN Turing machine: is it decidable? RE? [closed]

Suppose I have the following language: $$\mathrm{LOOP\mbox{-}EVEN} = \{\langle M \rangle \mid M \mbox{ doesn't halt on EVEN input} \}$$ Can someone can give me a hint whether this language or its ...
2
votes
1answer
44 views

Is Euler's totient function a primitive recursive function?

We consider the function $g$ which associates the number of prime integers with $n$ in the set $\{0,...,n\}$. I have to prove that $g$ is a primitive recursive function. First I defined the set $A=\{...
2
votes
1answer
30 views

What is the proof that boolean circuit (no negation gate) can be arranged as alternating OR and AND gates

In circuit complexity theory, a branch of computation complexity theory, a theorem is that any Boolean circuit without NOT gates can be written equivalently as a hierarchical structure, in which the ...
-1
votes
1answer
71 views

Turing Machine and decidability

so the thing is that i have to prove that if the language $L ⊆ \Sigma^*$ is decidable then both languages are also decidable. $$P_1(L) = \{w ∈ Σ\mid \text{ For every prefix v of w, we have }v ∈ L\},$$ ...
3
votes
1answer
17 views

How to handle an undefined case with µ-recursive functions?

How to construct my proof and generally what should I aim to get when showing a function is $\mu$-recursive? Should I transform it in some of the basic functions using the given operators? For ...
0
votes
1answer
48 views

How to show that a function is primitive recursive?

If we have a function $g\colon \mathbb{N}^{k+1} \to \mathbb{N}$ which is primitive-recursive. How to show that the function $f\colon \mathbb{N}^{k+1} \to \mathbb{N}$ with $$f(x_1, \dots, x_k , x_{k+...
4
votes
2answers
70 views

Does every procedure have a structural equivalent?

Suppose I have a basic mathematical function like: $ f(x) = x^2 + 2$ implemented in typed pseudo-code as: int f(x) { return x*x + 2; } If we were to break ...
-1
votes
0answers
14 views

Is there a RE language which contains exactly n strings of length n and whose complement is not RE?

I have the following question. Let Σ={a,b}. There exists a recursively enumerable language L subset of Σ*, whose complement is not a recursively enumerable language and for every natural number n, ...
3
votes
0answers
59 views

Universal lower semicomputable semimeasure and Coding Theorem

I'm following Li and Vitanyi's book "An introduction to Kolmogorov complexity and its applications" 3ed. I'll rewrite here the definitions I need for my question. The authors define the reference ...
0
votes
0answers
28 views

Are there any RE-complete languages w.r.t. polynomial reduction?

I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L $, meaning a polynomial-time reduction. I've tried to use $L=A_{TM}$ (the accepting problem), but got ...
0
votes
0answers
18 views

what is NP class? [duplicate]

I actually started to read complexity classes of problems. and I know that NP class include P class problems and even more problems call NP-complete ... as many books define NP class as well But I ...
11
votes
1answer
2k views

Can a RAM calculate its own Gödel number?

You can get the Gödel number of a RAM by making it a list of commands and making this list an integer. So, what I thought is something like "The RAM that would return its own Gödel number (say, $x$) ...
0
votes
1answer
33 views

Relating memory complexity and decidablity

Given a language $L_u$, about which we know that there exists a non-deterministic turing machine which accepts it (as in, implying $L_u \in RE$) with memory complexity of $c^{p(n)}$, where $c$ is a ...
1
vote
1answer
40 views

Can we write a program that can say if any 2 given programs do the same w.r.t input - output pairs

I'm new to theoretical CS research. I have the following question: Given 2 different computer programs, each generating certain outputs for a given set of inputs. Assuming we are given the range of ...
28
votes
2answers
4k views

What are very short programs with unknown halting status?

This 579-bit program in the Binary Lambda Calculus has unknown halting status: ...
1
vote
1answer
34 views

Can LOOP-Programm stop when its value goes below 0?

I am wondering, if in the LOOP programing language, whether instances of the LOOP x DO P END are defined to stop in the case $x < 0$. The definition only says "...
30
votes
5answers
5k views

Can Quantum Computing solve Problems not even a Turing Machine can solve?

In his book "The Fabric of Reality", Penguin Books 1998, p. 218, David Deutsch says that the first quantum computer (built 1989 in the office of Charles Bennet, IBM Reasearch) "became the first ...
0
votes
0answers
27 views

Is there a broader class of total functions than $PR$? [duplicate]

In total functional programming programs are restricted to total computable functions. A well-known class of total functions are the primitive recursive functions ($PR$). However the Ackermann ...
-4
votes
0answers
19 views

Is a union of any TM language and the halting problem language decidable [duplicate]

I need to find if the following language is decidable (in $R$): $L=\{ \langle M \rangle \mid M \text{ is a TM}, L(M)\cup H_{TM}\in RE\}$ Where $H_{TM}$ is of the halting problem. My intuition is ...
0
votes
1answer
68 views

Classify the set of all TMs whose languages from the accepting problem

Let $$L = \{ \langle M \rangle \mid M \text{ is a Turing machine so } A_{TM} \leq_m L(M) \}$$ The question is whether $L$ is in $\mathcal{R}, \mathcal{RE}, co-\mathcal{RE}$ or in $\overline{\mathcal{...
1
vote
2answers
47 views

Prove the halting problem is undecidable using Rice's theorem

Is it possible to prove that the Halting problem is undecidable using Rice's theorem? Here's what I've tried and failed: We want to reduce Rice's Theorem (decide if a language has the nontrivial ...
0
votes
2answers
137 views

Decidability of the TM's computing a none empty subset of total functions

I have this HW problem: Let $F$ be the set of computable total functions, and let $\emptyset\subsetneq S\subseteq F$. Denote $$L_S=\{ \langle M \rangle | M \text{ is a TM that computes a function ...
0
votes
1answer
29 views

Are all functions with constant space complexity in $REG$?

The Wikipedia article about regular languages mentions that $DSPACE(O(1))$ is equal to $REG$. Can I conclude from this that every function in $R$ with constant space complexity is in $REG$?
4
votes
1answer
130 views

Prove that there is no computable enumeration of all decidable languages

The question: Let $L_1,L_2,...$ be an enumeration of $\mathcal{R}$ and define $A_i = \{\langle M\rangle \ | \ L(M) = L_i\}$. Let $L$ be a language in $\mathcal{RE}$ such that $L \subset \{\langle ...
1
vote
0answers
48 views

Is $f$ which returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ computable?

The question itself: Let $f:\mathbb{N}\to\Sigma^\star$ be such that $f(n)$ returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ (which is the complement of the language of TMs which accept $\...
5
votes
1answer
22 views

Primitive Recursion equipped with an evaluator function

The wikipedia article for primitive recursion mentions a limitation that primitive recursive function can't compute the function $ ev(i,j) $ which computes the $ i $th primitive recursive function on ...
3
votes
1answer
38 views

Theoretical justification of “halting problem avoidance”

The wikipedia page for the Halting problem mentioned practical solutions to avoiding the halting problem such as avoiding infinite loops. And there is a mention that "by restricting the capabilities ...
3
votes
1answer
116 views

Undecidable vs Unsolvable?

In decidability theory, I understand that if a problem is labeled "decidable", then we can construct a Turing Machine that definitively tells us whether an input is valid or invalid. My question is ...
1
vote
2answers
161 views

Is it possible to design a programming task that is unsolvable?

Can a problem (described by a set of inputs and accepted answers) be designed such that for all programs which produce an answer in finite time for a (countably) infinite number of inputs, at least ...
2
votes
1answer
113 views

Is the system of measuring length in the US is Turing complete?

The author here writes: Little known fact, the system of measuring length in the US is Turing complete My question is: Is the system of measuring length in the US is Turing complete?
3
votes
1answer
60 views

Undecidability of REGULAR_TM (Detail within Proof)

I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book. The example shows how $REGULAR_{TM}$, defined as the ...
3
votes
2answers
62 views

Given a r.e. (recursively enumerable) language, L, how many Turing machines semi-decide L?

$L\subseteq \{0,1\}^*$ Since the language is r.e. there is definitely at least one Turing Machine that semi-decides the language. I'm thinking that if you have one Turing Machine that semi-decides ...
2
votes
2answers
61 views

Language of TMs such that one state is visited most often

To be safe, let me start this question by giving the definition of a TM I will be using: A TM is some $M = (Q, \Sigma, \Gamma, q_0, \delta, q_F)$, where $Q$ is the finite state set, $\Sigma \subset \...
0
votes
1answer
45 views

Showing a language is context free. Use PDA or CFG?

I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it. Show language $L$ is context free, where $L = \{\text{...
1
vote
0answers
50 views

Language of Turing machines that never visit some given state

Can someone help me to determine and prove if the following language is decidable or not? I tried to think on some reductions but I can't figure it out... $$A=\{\langle M\rangle|\text{$M$ is $TM$ ...
1
vote
2answers
36 views

The language of Turing machines that accept exactly $k$ inputs

For a fixed $k\geq 0$, let $X_k = \{\langle M\rangle\mid |L(M)|=k\}$, where $\langle M\rangle$ is the encoding of a Turing machine $M$ and $L(M)$ is the language $M$ accepts. Is $X_k$ ...
8
votes
1answer
70 views

Church-Turing and physical PDEs

When I read about the Church-Turing thesis it seems to be a common claim that "physical reality is Turing-computable." What is the basis for this claim? Are there any theoretical results along these ...
3
votes
1answer
20 views

How to identify strongly confluent cellular automatas?

Lets represent a class of cellular automata as a finite, unidimensional bit array state : [Bit], plus a rewrite rule ...
0
votes
1answer
54 views

Implications of Halting Problem being unsolvable?

I came across a confusing situation when reducing the Halting Problem (HP) to the Blank Tape Accepting Problem (BP). We know that since HP can be reduced to BP, BP is decidable $\implies$ HP is ...
1
vote
1answer
37 views

Prove Undecidability Without Using Rice's Theorem

Show that checking if a TM accepts some input string of length greater than some constant $k$ is undecidable. Here the constant $k$ is publicly known. I tried solving this problem by trying to reduce ...
1
vote
1answer
27 views

Turing Machine that always returns a blank tape

Is it possible to construct a Turing Machine such that given any finite input on a tape $s$, it clears the tape in a finite amount of time? I have used such a TM as an intermediate step to show a ...
0
votes
1answer
47 views

If the strings of a language can be enumerated in lexicographic order, is it recursive?

If the strings of a language L can be effectively enumerated in lexicographic order then is the statement "L is recursive but not necessarily context free" is true?
0
votes
1answer
28 views

Complexity classes of undecidable Turing Machines

I'm finding it difficult to find the information online and I can't find the information in my college notes but i'm wondering what complexity-class languages like Atm and Halttm (The TM that always ...
-1
votes
1answer
63 views

How do you know a problems is non-computable?

I am currently looking at intractable problems and N/NP etc but am a little confused about one term used in the book I am reading. It says in this book that a non computable problem is one which ...
-1
votes
1answer
65 views

How can a Turing machine accept infinite number of inputs? [closed]

How it is possible for a turing machine to process an infinitely long input ?