Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
5
votes
3answers
921 views
Relation between Undecidable problems and NP-Hard
I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.
And then, I realized that it is not certain where undecidable problems should be placed.
...
0
votes
0answers
15 views
Partial Recursive Functions of Kleene [on hold]
I am writing and asking for your help, if you could give me any good sources for the topic which is in the title. I have to do a powerpoint presentation this week and I really couldn't find any ...
1
vote
1answer
21 views
Decidability of factoring algebraic equations
Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution:
$$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$
And some arbitrary factorization constraints, say:...
2
votes
2answers
34 views
Can a RE language be reduced to a non-RE language?
In our lecture notes about many-one reduction we showed that the following statements hold:
$$ L, L' \subseteq \mathbb{N}\space and \space L\leq L'$$
$$(I)\space L' \in RE \implies L\in RE$$
$$(II)\...
0
votes
0answers
20 views
Witnessing for partial recursive functions
For all $f\colon \mathbb{N}^2 \rightarrow \mathbb{N}$ partial recursive there exists partial recursive $g\colon \mathbb{N} \rightarrow \mathbb{N}$ such that
a) $x \in \operatorname{Dom}(g) \...
0
votes
0answers
10 views
About a “modification” of the diagonal language $\{w_i \mid \text{Every turing machine } M_1 \ldots M_i \text{ reject } w_i\}$
I have given the seeming modification of the diagonal language $\{w_i \mid \text{Every turing machine } M_1 \ldots M_i \text{ rejects } w_i\}$, yet I can't prove that it is undecidable.
My thoughts ...
0
votes
0answers
12 views
Whether language of all turing machines is decidable or undecidable or semi-decidable?
I recently came across this language:
$L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$
It was asked in the question to find out whether language L is decidable or undecidable.
...
0
votes
0answers
11 views
Proof that a language is not r.e. via reduction [duplicate]
I have to proof that the following language:
L:={ DTM | DTM halts for an infinite amount of inputs }
is not recursively enumerable.
Intuitively, I'd pick the ...
1
vote
0answers
14 views
Can a CFG generate an accepting configuration? - or is there a turing-recognizable CFG language that is not decidable
I could not think of a way to concisely write down my question clearly, but I'd like to ask, from Sipser's book, $ALLCFG$ is an undecidable language (where $ALLCFG$ means that $G$ is a $CFG$ that ...
1
vote
1answer
41 views
Trying to prove semidecidability of an undecidable language
I have been having a hard time understanding whether the set $S = \{ M \mid |L(M)| = 5 \}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, ...
0
votes
0answers
16 views
Understanding the computational power of neural networks
It is known that a recurrent neural network with rational weights is computationally equivalent to a Turing Machine (a proof can be found in this paper).
I don't understand how is it possible, it ...
1
vote
0answers
37 views
Power of Turing machines that are not allowed to overwrite the input string [duplicate]
The question asks what kind of languages (regular, context free) can a Turing machine accept if you are not allowed to overwrite the input string. The initial configuration of the machine is start ...
-1
votes
0answers
14 views
Is it possible to convert a CNN into a Decision Tree?
transformation of Convulutional neural networks into Decision Tree possible or not?
4
votes
2answers
90 views
Is there any other computation theory besides the one in automata theory?
I'm a bit confused at a fundamental level.
In Computer Science, maybe some of us mostly use discrete mathematics since our computer is digital (like during studying operating system, algorithms, ...
0
votes
0answers
10 views
Proving that a language is undecidable [duplicate]
I'm trying to show that the language $L$ = {$<M,w>$ | $M$ is a TM that accepts $\overline{w}$} is undecidable, where $\overline{w}$ is the bitwise complement of $w\in \{ 0,1\}^*$. I know that ...
1
vote
1answer
24 views
In which environment we use NFA(Non Deterministic Finite Automata)?
We have two types of Automata. One is NFA and second is DFA. These are little bit different but thing is that in which environment we prefer NFA over the DFA?
0
votes
0answers
32 views
Context Free Grammar don't allow to assign constant/expression to a variable [closed]
I am writing a recursive descent parser for the below grammar (Decaf). But, my recursive parser says that the below program is not valid according to Grammar. In particular, it works till line 8 and ...
2
votes
2answers
41 views
Weaker, but similar conditions to Turing completeness?
A model of computation is called Turing complete if it can simulate any Turing machine.
This rules out for example a combinational logic circuit.
However, there is a sense in which combinational ...
0
votes
1answer
32 views
Would hypercomputation machines be capable of simulating/computing/programming everything?
If uncomputable numbers existed, could this hypercomputation machines compute them? Could hypercomputation compute all types of uncomputable things? Even truly inconsistent things? Even things that ...
0
votes
1answer
29 views
Prove that $L = \{a^i \;:\; (\exists x \in \mathrm{Lang}(M_i))\;[ xx \notin \mathrm{Lang}(M_i) ] \}$ not recursively enumerable [duplicate]
Past year paper question:
Let $M_i$ denote the Turing machine with code $i$ using the alphabet $\Sigma=\{a,b\}$.
Show that the following language is not recursively enumerable:
$L = \{a^i \;:\; (\...
0
votes
0answers
16 views
Non-Turing-recognizable Language [duplicate]
I have been stuck on this problem for a while:
Show that $L=\{\langle M \rangle : L(M) \text{ contains an even number of strings} \}$ is not Turing-recognizable.
I know that by Rice Theorem, this ...
-1
votes
2answers
74 views
Is a Turing machine too strong of a model to model physical computation?
I've heard many times people debate the possibility of a real world computation that is impossible for a Turing machine, especially in the context of a human mind. Implying that the Church-Turing ...
0
votes
1answer
28 views
Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference
Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A).
I know that ...
0
votes
0answers
25 views
Is this language of TM pairs, defined via properties of their languages, decidable? [duplicate]
Lets assume we have the following language
$$\{\langle M, N \rangle\ | \text{ All strings in } L(M) \cap L(N) \text{ begin with 110.}\}$$
How would we go about proving its decidability? Thanks.
2
votes
1answer
31 views
Converse of halting problem
It is well known that if some computing apparatus is Turing-complete, then the halting problem is undecidable for that computing apparatus. However, is it true that if the halting problem is ...
1
vote
1answer
23 views
Why aren't recognizable languages and co-recognizable languages not reducible to each other?
While learning to prove undecidability of problems, I came across a statement that you can't reduce a recognizable language to a co-recognizable language and vice-versa to prove undecidability. Why is ...
0
votes
0answers
47 views
Is it decidable that a given Turing machine never moves left on a given input? [duplicate]
$$\{\langle M, w\rangle\mid M\text{'s head never moves left on input }w.\}$$
My second thoughts for this problem is that is should be decidable. We can make a Turing Machine that takes as input and ...
2
votes
1answer
41 views
Decidability of Turing Machine accepting exactly 14 words
Would you say that the following problem is undecidable?
$$L_1 = \{\langle T \rangle \mid T \text { accepts 14 words}\}$$
My intuition says that this must be undecidable, and I want to try to reduce ...
0
votes
1answer
44 views
Is the language of all TMs accepting all strings starting with 010 decidable?
I am trying to figure out if this language is decidable:
$$ \{ \langle M \rangle \mid \text{$M$ accepts all strings starting with 010}\}. $$
My intuition is that it is. Whatever string $w$ starts ...
3
votes
2answers
52 views
Primitive recursive plus Ackermann
Let us consider the class $\cal F$ of functions that contains
all constant functions
all projections
the successor function
the Ackermann function
as basic functions, and that is closed under ...
2
votes
0answers
27 views
Semidecidable properties of computable reals
By computable real I mean $x\in\mathbb{R}$ such that there is some computable total function $p_x$ that takes a natural number $n$ and returns a dyadic rational $r$ such that $|x-r|<2^{-n}$. I ...
0
votes
2answers
28 views
Error in proof of decidability
$L=\{\left<M\right> \ | \ M $ is a TM s.t. $M$ does not accept any string starting with a '1' $\}$.
Assume the alphabet to be $\Sigma = \{0,1\}$.
By Rice's theorem $L$ is undecidable. I ...
1
vote
1answer
46 views
Prove $L = \{M \mid L(M)\text{ is infinite}\}$ is not Turing-recognizable
I'm supposed to prove this through mapping reducibility. I think I'm supposed to show that $A_{\mathrm{TM}} \le_\mathrm{m}\overline{L}$, which means that $\overline{A_{\mathrm{TM}}}\le_\mathrm{m} L$ ...
3
votes
2answers
67 views
Does Halts reduce to all other undecidable languages?
In a CS theory class I'm taking, we showed Halts was undecidable via a diagonalization argument. All other undecidable problems we looked at we either got by reducing Halts to them, or some chain of ...
2
votes
0answers
71 views
What is the simplest automaton that can compute the sum of two integers of arbitrary length?
It should be obvious that a Turing machine is capable of computing the sum of two integers. However, what is the simplest automaton that can compute the sum of two integers of arbitrary length?
I ...
1
vote
1answer
50 views
Is this system Turing complete?
I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries.
I came up with the ...
0
votes
1answer
42 views
Isn't the given characterisation of recursively enumerable subsets of the class of all recursively enumerable languages?
$S$ is a subset of the class of all recursively enumerable languages over some finite symbols then $S$ is recursively enumerable iff
If $L$ is in $S$ and $L'$ is a language such that $L ⊆ L'$ and $L'$...
0
votes
0answers
22 views
All the ways in which Turing machines are used
The Turing machine model can be used to do computation in several ways. Two ways I know are:
For a Turing Machine that checks whether a particular string is present in a language or not, when the ...
0
votes
1answer
45 views
What is the definition of computable partial function?
Let $f:\mathbb{N} \to \mathbb{N}$ be a computable partial functions and $T$ a Turing Machine which computes it. By this I understand that $T$ writes $f(n)$ on its tape and halts when $n$ is an input ...
0
votes
0answers
19 views
Which subsets of the set of all recursively enumerable languages is recursively enumerable?
I know that, Rice's say's any non trivial subset of the set of all recursively enumerable languages is not recursive. I also remember reading some characterisation of the recursively enumerable ...
3
votes
1answer
644 views
Does a notion of a context-free complete language exist?
Is there a notion of a context-free complete language (in the analogous sense to a $NP$-complete language)?
1
vote
1answer
16 views
How hard can identifying non-membership in a semi-decidable language be?
A language is called semi-decidable if there is an algorithm for identifying members. There are well-known examples of semi-decidable languages where identifying non-members is equivalent to $\...
1
vote
2answers
58 views
Why is the total number of atoms in the observable universe often considered as an upper bound for computational feasibility?
There are many papers and textbooks in computer science that claim that computational problems are not feasibly computable (technically, not theoretically as with the halting problem) using a ...
0
votes
0answers
29 views
Show that the language of TMs that halt for at least one input is partially decidable but not decidable
I am trying to prove that the language $L = \{w ∈ {0, 1}^∗ \mid M_w(x) \text{ converges for some input } x\}$ is partially decidable but not decidable. $M_w$ is one encoding of the turing machine $M$, ...
1
vote
1answer
34 views
Proof that the Blank Tape Halting Problem is undecideable [duplicate]
I have seen a few proofs that the Blank Tape Halting Problem is undecideable, however I'd like to check if the following is a valid proof (and if it isn't why not)
Proof: Suppose that the Blank Tape ...
0
votes
0answers
19 views
example of $A \leq_m B$ where $A$ is decidable but $B$ is undecidable [duplicate]
I know that given a mapping reducibility function $\leq_M$ from $A$ to $B$, if $A$ is undecidable, then $B$ is also undecidable. But if ever $A$ is decidable, from what I think, it does not ...
0
votes
1answer
29 views
Robustness of non-context-free proof against trivial manipulation
First, we state here a theorem that is well-known in computability theory:
$L=\{xx\mid x\in\Sigma^*\}\notin CFL$ for every fixed $|\Sigma|\geq2$
And, the standard proof is using pumping lemma. At ...
2
votes
1answer
49 views
How to reduce a problem?
I am a bit confused on how to reduce a problem. I'll give an example:
Let's say there is a problem called HALTEMPTY and we know it is undecidable.
$HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ ...
1
vote
2answers
42 views
How can MLTT etc encode computability?
I am recently thinking about proving the undecidability of some problem. This problem has been formalized in Coq and by staring at it, people including me think "for sure" this is undecidable. "For ...
1
vote
1answer
31 views
decision diagram and decision tree difference
What are the difference between decision diagram and decision tree? Is BDD a type of DD? what are the other type of DD? what are the algorithms used for it
