Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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