Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
0
votes
1answer
19 views
Why a TM with infinite states can decide the halting problem?
Assuming we have a model of TM with an infinite number of states.
The domain and range of the transition function are also infinite.
Given a description of a TM $M$ and a string $w$ how can we use the ...
-4
votes
0answers
14 views
#P=NP: All satisfying solutions are valid answers by programs for NP [on hold]
In fact, the implication looks like an equivalence too.
All satisfying solutions to a boolean formula
are valid answers by programs for NP
is equivalent to saying
the class #P equals the class NP.
...
0
votes
0answers
29 views
Decidablity of time complexity
Let $t:\mathbb{N}\rightarrow\mathbb{N}$ be a time constructible function with $t(n)\geq n + 100$. Show that there is no TM $T$ that given the gödel number of another TM $M$, decides wether or not M is ...
-1
votes
0answers
56 views
Undecidability of the “Single-Halting Problem”
I have to show for a turing machine S that is taking another TM T and a word x as input and only halt for one specific T and x, that it is not decidable. The idea is now to reduce it to the halting ...
5
votes
1answer
726 views
What is the complement of a language?
If given any language L, how do I find the complement of said language?
I lack the basic understanding required to determine if a language is co-recognizable. I understand that a language, $L$, is co-...
2
votes
0answers
30 views
Is the language $L$ of coded CFG's Turing decidable?
Consider the following language
$L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$}
Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
1
vote
2answers
46 views
Recognizer for decidable language and words it doesn't halt on
Suppose we have a decidable language B (there exists some TM that decides it). Suppose we have another TM M which only ...
0
votes
1answer
22 views
Is the set of surjective recursive functions in RE/coRE?
Let L be a set of recursive funtions with $L = \{i\in \mathbb{N}|f_i\space is\space surjective\}$ where $i$ is a gödel number of f.Is $L\in RE,\space coRE$?
I can't think of a way to show either of ...
1
vote
2answers
91 views
Are the capabilities of programming languages the same?
Is the capability of every programming language the same since it is eventually translated into machine code. Python, Java etc. are all together instructions the CPU is going to process. So, you could ...
0
votes
0answers
21 views
How strong is a FSM with long enough(but not infinite) tape?
Like turing machine, but your tape is finite. To make a program valid it should have a limit result when the length of tape tends to infinity.
Whether the tape has two ends or is cyclic doesn't ...
0
votes
0answers
41 views
Mathematical resource material accompanying TAPL
I'm currently reading Types and Programming Languages by Benjamin C. Pierce and just arrived at chapter 21 Metatheory of Recursive Types.
Prior to this chapter I found the book challenging but ...
4
votes
1answer
53 views
Is Rice-Shapiro theorem bidirectional?
Rice-Shapiro theorem states that
version A
Let $\Gamma$ be a set of computably enumerable sets, and $I = \{e : W_e \in \Gamma\}$ its index set in some admissible enumeration of c.e sets. If $I$...
1
vote
1answer
24 views
Can the complement of an unrecognizable language be a recognizable language?
I know that complement of a language that is recursively enumerable, but not recursive, is definitely not recursively enumerable (or unrecognizable). So my question is what can be said about the ...
1
vote
1answer
31 views
How to prove that a problem is undecidable by using the Halting problem?
I cannot understand how to reduce the halting problem to a property to show that is undecidable.
For example, I have this property of a Turing Machine and I have to prove if it's recursive or not:
"...
1
vote
3answers
60 views
Proof Idea: There are irrational numbers whose decimal expansion cannot be computed
The online lecture I am watching stated a proof idea:
The set of all possible programs is countably infinite, yet
the set of irrational numbers is uncountably infinite.
I don't think this is ...
0
votes
1answer
52 views
Halting problem with extra input
Can there be a function HALT(f, y) so that:
There are some x such that f(x) halts iff there ...
1
vote
1answer
24 views
Is a set $B = \{y, \exists x \in A, f(x)=y\}$ recursive if A is a recursive set and f is a $N->N$ total computable function?
Obviously, B would be recursive if for every TCF f, there was an inverse fuction that would return all possible values, as we could just take these and then check if any of them is in A. However I ...
1
vote
1answer
29 views
Are physical laws uncomputable in any type of computation (according to this article)?
It seems that this article (https://arxiv.org/pdf/1312.4456.pdf) proposes that laws of physics are uncomputable (i.e., they could not be reproduced on a computer), but I'm not sure about it.
In some ...
0
votes
0answers
14 views
Is ${M :|L(M)| \leq 330}$ Recursively enumerable? [duplicate]
M is a Turing machine description, L(M) is the language recognized by M and |L(M)| is the size of this language.
2
votes
1answer
82 views
Which one of these two sets is computably enumerable?
M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language.
{M : |L(M)| <= 330}
{M : |L(M)| >= 330}
I don't quite understand what this question is asking. ...
1
vote
1answer
34 views
Reduce ATM to REGULAR_TM
Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$.
Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\...
4
votes
1answer
132 views
Language that fulfills pumping lemma but is not in RE
I am supposed to find a language $$L\subseteq \Sigma ^*, \Sigma \subseteq \mathbb{N}$$ that fullfills the pumping lemma and is not in RE and not in coRE. I've never constructed a language with a given ...
0
votes
1answer
29 views
Are non-regular languages decidable?
Given a language L, I've shown that L is not regular. Can I conclude that it is not decidable or are there non-regular languages that are decidable?
2
votes
2answers
34 views
Quotient in LOOP program [closed]
I want to construct a LOOP-computable program for the integer division (quotient):
x = a DIV b
The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP_(programming_language)
I ...
2
votes
0answers
56 views
What is the relationship between “model of computation” and “algorithm”?
Traditionally, the usual definition you find for model of computation is "an abstract description of how an output is computed given an input" (Wikipedia and my TCS course are my sources, but the ...
6
votes
2answers
1k 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.
...
2
votes
1answer
37 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
46 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
27 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
17 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.
...
1
vote
0answers
22 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
64 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, ...
-1
votes
0answers
17 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
39 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 ...
5
votes
2answers
97 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, ...
1
vote
1answer
26 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?
2
votes
2answers
45 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
33 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
30 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
17 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 ...
0
votes
3answers
111 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
36 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 ...
4
votes
2answers
86 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
26 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 ...
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
61 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
53 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
28 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
29 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
58 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$ ...
