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

learn more… | top users | synonyms

-3
votes
0answers
27 views

Show that the following sets are not recursively enumerable [on hold]

Show that the following sets are not recursively enumerable. a) { i | Wi = ∅ } b) { i | Wi = all integers } (a) { i | Wi = ∅ } As the set is empty set then ...
1
vote
1answer
24 views

Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$)

I have difficulties to differentiate the $H_0$ from the $E_{TM}$ problem. What exactly means $L(M)= \emptyset $? Is it dffierent from $input~ \varepsilon$ or is $L(M)= \emptyset \leftrightarrow ...
1
vote
1answer
82 views

Calculi for a computability class

Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the ...
1
vote
1answer
29 views

Equivalence of regular grammars

I know that proving context free grammars equivalent is undecidable. I also know that proving if a context free grammar recognizes a regular language is undecidable. Here is my question: is proving ...
2
votes
1answer
61 views

Is the memory usage of total languages deterministic?

I'm interested in the memory usage of various programming languages when implemented on actual hardware. I believe that a Turing-complete programming language has, in general, unknowable memory usage ...
4
votes
0answers
136 views

Is the halting problem decidable for 3 symbol one dimensional cellular automata?

I've been trying to figure out if the halting problem is decidable for 3-symbol one-dimensional cellular automata. Definition. A cellular automaton has halted in state $s$ if running the automaton on ...
-2
votes
1answer
67 views

Language is decidable or not? [on hold]

Prove each languages decidable or undecidable. { <M> | L(M) is not recognizable} I am not able to understand how this works. And what is recognizable ...
3
votes
1answer
363 views

Is something more than Turing complete Turing complete?

In complexity theory, we do not call a decision problem that is not in NP "NP-complete". But in computability, do we call a machine model "Turing complete" if it can compute functions which Turing ...
4
votes
0answers
41 views

Turing reductions by NX ∩ coNX and binary relation problems

Let $A$ be a non-deterministic algorithm computing a binary relation between an input string and possible output strings. Let NX be a (potentially non-deterministic) complexity class. What is a good ...
-1
votes
2answers
60 views

Is the following language decidable, enumerable or non-enumerable?

$$L = \{\langle M_1 \rangle, \langle M_2 \rangle \mid \text{\(M_1\) and \(M_2\) are TMs and \(\forall X, M_1(X) = M_2(X)\)}\}$$ Is this language decidable, enumerable, or non-enumerable? And in ...
3
votes
2answers
50 views

Is it decidable whether a given context free grammar generates an infinite number of strings?

Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or ...
1
vote
2answers
37 views

Non Recursively Enumerable Languages

Can someone give me an example of Non Recursively Enumerable language... i.e. A language which no Turing machine can accept ? What makes a language non recursively enumerable ?
-1
votes
1answer
38 views

A program for polytime languages

Does their exist a program P[m,s] which always halts and for any polytime language exists an m; possibly incomputable; such that P[m,s] accepts only those strings s which are in the language.
4
votes
1answer
227 views

EQtm is not mapping reducible to its complement

This is a problem from Sipser's book (marked with an asterisk). $EQ_{TM} = \{(\langle M \rangle, \langle N \rangle)$ where $M$ and $N$ are Turing machines and $L(M) = L(N)\}$ We know that neither ...
3
votes
1answer
37 views

Is the following language recursively enumerable?

Let $L =\{ <M> | $ the amount of words $w\in\Sigma^*$ that $M$ does not halt on is finite $\}$. I would like to prove that $L\notin RE$. I can show that $\overline{L}\notin RE $ that is ...
3
votes
2answers
64 views

The language of machines that accepts all palindromes is not Turing recognizable

I have this question: $L = \{\langle M \rangle | M$ is TM that accepts every palindrome over its alphabet $\}$ Proof that $L$ is not Turing-recognizable by showing reduction from other non ...
4
votes
1answer
29 views

Reduction from ATM to ATM-complement

Is there a reduction from ATM to ATM-complement? (ATM denotes the language $\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$) I have been thinking about it too much and couldn't find the ...
1
vote
0answers
19 views

Reduction of decidable and undecidable problems [closed]

Let: f be a decidable decision problem. g be an undecidable decision problem. I refered to those rules: If $f$ reduces to $g$ and $g$ is decidable $\implies$ $f$ will be decidable. If $f$ ...
5
votes
2answers
215 views

Is the set of TMs that does not reach most cells to the right computable?

Let $L_{NTF} = \{ \langle M \rangle \mid $ for every $x\in\Sigma^* $ the machine $M$ does not reach the $|x|+10$'th cell during its calculation on $x$. $ \}$. I would like to prove or disprove ...
4
votes
1answer
38 views

How to prove the following language is not in R

Let $c\in \mathbb{N}$. Denote: $L _c= \{ \langle M \rangle \mid \exists _{U \subseteq \Sigma ^* }$ s.t. $|U| $ is infinite and for each $w\in U $ the TM $M$ accepts $w$ within no more than $c$ steps ...
1
vote
1answer
13 views

Reduction from $A_{TM}$ to Rice theorem: what if input of $A_{TM}$ loops?

I'm learning this reduction from $A_{TM}$ to $R_P$ for the proof of Rice's theorem. This is the reduction: https://gyazo.com/10cdc3b833a8d1bd9cdbb1eb08e76303 (Source of the slides: The University of ...
1
vote
1answer
16 views

recursively enumerable sets closed under concatenation

I'm trying to show the set of all recursively enumerable sets is closed under concatenation. I'm trying to use the definition of recursively enumerable sets to construct the argument. I believe that I ...
0
votes
1answer
30 views

How the website owner keep track of your times of access? [closed]

To be specific, I am using the online website of Strait Times News. It limits users to 30 articles to read per month. I just do not understand how do they know you are accessing? We use different IP ...
1
vote
1answer
49 views

two languages reducible to each other can belong to RE and recursive?

If two languages L1 and L2 both are reducible to each other in polynomial time then which of the following is false? A L1 is decidable and L2 is undecidable. B L1 is recursive and l2 is RE C ...
1
vote
0answers
15 views

Computing shifted fix point in the BSS model

Let $p \colon \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ be a one-dimensional function that fulfills $p(0)=0$. Moreover, we are given some value $u \in \mathbb{R}_{> 0}$ such that $p$ is ...
1
vote
2answers
39 views

Undecidable language and Turing Machines

I am reviewing some old papers for a final tomorrow, and there is a question that I'm not sure about. If a language A is Turing-Recognizable and Undecidable, what can be said of the Turing-Machine ...
13
votes
4answers
654 views

Why are computable functions also called recursive functions?

In computability theory, computable functions are also called recursive functions. At least at first sight, they do not have anything in common with what you call "recursive" in day-to-day programming ...
0
votes
1answer
42 views

Given a λ-term, can I decide which machine model I need to express it?

I am having a hard time figuring out the specific relationship, of various things in computability. So we have a hierarchy of machines, with a (real life) upper bound of Turing machines, moving on ...
2
votes
0answers
28 views

What language features would I need to remove from a real programming language to make it decidable? [closed]

Let's say that I want to restrict certain features of a common programming language--for instance, C--such that the result is decidable, and thus no longer Turing-complete. What language features, at ...
1
vote
1answer
29 views

Minimal class of grammar required to run program

In computability we have the hierarchy of grammars "https://en.wikipedia.org/wiki/Chomsky_hierarchy". In this hierarchy we have many classes of grammar. This hierarchy has Turing machines at the top, ...
-3
votes
1answer
37 views

Need help understanding a decider

currently working through slides and I've noticed this which I believe to be an error. Shouldn't the two DFA's be swapped around, so that the one that reaches the accept state is with L(M)=nothing is ...
1
vote
0answers
82 views

Is English Recursively enumerable? [closed]

The title says it all. I've tried digging up debate on this issue to see a proof one way or the other but it doesn't look like anyone is able to say whether or not it is. Clearly there are recursive ...
9
votes
2answers
338 views

How to prove that 3-coloring is decidable?

In order to prove that 3-coloring is decidable, is it sufficient to say: Each node in the graph has 3 possible colors Therefore we can enumerate over all $3^n$ possibilities and then check that no ...
1
vote
2answers
49 views

Why does the proof of undecidability of $A_{TM}$ require the universal TM to take input $\langle M,\langle M\rangle\rangle$?

I've read a proof explaining why $A_{\mathrm{TM}}$ is undecidable, and I don't seem to understand why we need to give the opposite of $H$ function $D$ itself as input. Here's the copy-paste of that ...
7
votes
1answer
212 views

Problems whose decidability status is unknown but known to be less hard than the halting problem

Are there problems the decidability of which is unknown but it is known for certain that the problems are less hard than the halting problem.
21
votes
2answers
373 views

Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?

Every undecidable problem that I know of falls into one of the following categories: Problems that are undecidable because of diagonalization (indirect self-reference). These problems, like the ...
1
vote
1answer
85 views

A question on encoding

Assuming there is a machine which can effectively calculate functions not computable by a TM (or the Church-Turing thesis as false) What can we say about aTM solving a problem encoded by this ...
0
votes
1answer
34 views

How can we prove that an enumerable/decidable group of languages is closed under an operation?

For example: If the XOR operation on two languages, A and B, is described as: $A\;\mathrm{XOR}\;B = (A \cup B) \setminus (A \cap B)$, 1) How can we prove that the set of enumerable languages is ...
0
votes
0answers
22 views

Are there any classes of functions whose definitions can be easily procedurally generated and have implementations easily procedurally checked, but

Are there any classes of functions whose definitions can be easily procedurally generated and have implementations easily procedurally checked, but for which valid implementations are difficult or ...
5
votes
2answers
120 views

Will encoding affect computability?

I think this question arises from not having a clear idea on encoding. So, If I have a problem intuitively there may be many ways of encoding it using TM's alphabet set. Slight variation in the ...
1
vote
2answers
146 views

Turing machine - infinite tape - does that thing exist?

Can we use a Turing machine with infinite tape as a basis to prove anything disregarding the fact that such a thing can never exist? Do we have the right to regard a machine (a construct) in the same ...
4
votes
1answer
60 views

Machines whose languages are their own encoding

Is the language $S = \{\langle M \rangle \mid M \text{ is a Turing Machine and } L(M) = \{\langle M \rangle\}\,\}$ decidable, recognizable and/or co-recognizable? I tried diagonalization but can only ...
0
votes
0answers
35 views

What can be said about the Halting Problem if we can include the halting status to the input?

I was reading about Turing Machines and the Halting Problem, i understand that you need an oracle to decide whether given input will halt or loop forever. But why do we need an oracle if we can ...
0
votes
0answers
36 views

Busy Beaver problem - Proof by contradiction

I am trying to understand a proof regarding the Busy Beaver problem that uses a proof by contradiction approach to show $\sum(n)$ is Turing-uncomputable: Find $\sum(n) = max \{\sum(M) | M \in M(n) ...
-1
votes
1answer
52 views

How to make an undecidable Turing Machine decidable?

I came across the following question in my revision. I would like to know how to solve this and in general what are the techniques I can use to make an undecidable TM decidable by changing inputs? ...
6
votes
1answer
80 views

How can the class of tail recursive functions be compared to the classes of PR and R?

How can the class of tail recursive functions (TR) be compared to the classes of primitive recursive functions (PR) and recursive functions (R)? The computation of a PR function always halts. This ...
1
vote
2answers
356 views

Is how much memory a program needs computable?

We know that how much time a program needs is not computable. Do we know how much memory a program needs is decidable?
1
vote
0answers
40 views

Showing that $H'$ is not semi-decidable

I have an introductory class in computability theory and I'm currently working on my first exercises. I'm wondering if I'm on the right track with proving undecidable languages. Could you please have ...
4
votes
1answer
54 views

Given computable function, what are conditions for computability of inverse function?

If $f:\mathbb{N}\rightarrow\mathbb{N}$ is computable and has an inverse, under what conditions is $f^{-1}$ also computable? I couldn't find that in a textbook, and googling gets some vague suggestions ...