Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,483
questions
1
vote
1answer
6 views
Doubt in definition of closure under concatenation operation in Recursive Enumerative languages
I recently started studying theory of computation.
Recusive enumerable language – closed under concatenation. Sir, I have a doubt regarding understanding of this.
Please Note - RE shortform i am ...
0
votes
2answers
41 views
An example of a computable problem that is not in P
I am trying to find a simple example of a problem that is computable but not in P, I know very well that it would be enough to get one in NEXTIME-complete however the problems that I find in this set ...
1
vote
1answer
22 views
Is this set computable?
Let be $B$ a Busy Beaver function and set $W=\{\langle M \rangle :\text{$M$ stops in less than $B(10^{1000})$ steps on an empty tape}\}$. Is this set computable?
I'm not sure how to approach this ...
1
vote
1answer
14 views
What is known about the sets enumerated by primitive recursive functions?
Let's say that a set of natural numbers $S \subseteq \mathbb{N}$ is primitive recursively enumerable if there exists some primitive recursive function $f$ such that $S$ is the range of $f$. That is, ...
0
votes
0answers
28 views
A condition for $\emptyset \neq S\subset RE$ under which $L_S \notin RE$
I read some computation theory lecture notes and after citing and proving the proposition: $\emptyset \in S \Rightarrow L_S = \{\langle M \rangle : L(M)\in S\} \notin RE$ it says that $\emptyset\in S$ ...
3
votes
1answer
57 views
Problem in downvote system
Problem
For my game, I'm building a system where players have power/weight, and they can downvote each other, players with 66% of downvote weight are banned. The weight of the votes is calculated ...
0
votes
1answer
23 views
Can you determinize an NFA in PSPACE?
QUESTION
Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$?
MORE DETAILS
I'm asking this as I want to be able to ...
0
votes
0answers
16 views
Why are CFL not closed under set difference, and complementation? [duplicate]
I was wondering why CFL are not closed under set difference, and complementation can anyone explain? I tried searching, but no luck.
0
votes
1answer
21 views
Proving whether an input sequence is in a given RE language
I've learned this a few years ago that this is impossible unless one simply 'executes' (in a modern computing sense) the input with the language rules, but I have some problems in just using this ...
2
votes
1answer
46 views
How strong is an oracle that avoid don't-halt
Consider such an oracle:
Given a turing machine[1], return the halting state it falls on, or arbitary result(but don't stuck in) if the TM doesn't halt.
How strong is a TM with the oracle?
Can the ...
1
vote
1answer
24 views
How to detect infinite loop exist in linear bounded automata (LBA)?
The following theorem from Michael Sipser's book "Introduction to the Theory of Computation" states:
$A_{\textrm{LBA}}= \{ \langle M, w \rangle \mid \text{$M$ is an LBA that accepts string $w$} \}$....
1
vote
3answers
87 views
Is the calculation of infinite sums solvable by a computer?
The question is: I give the computer a sum, such as $\sum_{n=1}^\infty\frac{1}{n^3}$, the computer is expected to return an elegant closed-form solution, because the answer may be irrational. Has this ...
-1
votes
2answers
145 views
The Halting problem proof is wrong?
First, let's see the pseudocode proof of halting problem:
P(x) =
run H(x, x)
if H(x, x) answers "yes"
loop forever
else
halt
Then we have a ...
-1
votes
1answer
104 views
Is the infinite program Turing-recognizable/decidable?
Imagine we have a program which does an infinite loop: while(true){loop}
We run the program on a linux machine(assume the compilation is ok), then this linux ...
1
vote
1answer
41 views
How can the VC-dimension of Turing machine be finite?
The VC-dimension of a hypothesis class $\mathcal{H}$ is defined to be the size of the maximal set $C$ such that $\mathcal{H}$ cannot shutter. This paper shows that the VC-dimension of the set of all ...
0
votes
0answers
33 views
Is the language $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$ decidable?
I have stumbled upon this language: $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$. At first, it looked like an undecidable problem, but I have failed to prove it, and now ...
2
votes
2answers
54 views
Decidable Program Equivalence
Determining whether two programs always return same output for same input is undecidable (easily reduced to the halting problem). My question is, is there a complexity class in which this problem is ...
3
votes
2answers
71 views
Is there any recursive function f whose code is unique?
I am doing some reviewing for the term final on computability and found out this simple exercise. I am very fresh on theoretical computer science so if you do have an answer please make it simple.
...
1
vote
0answers
24 views
PCAs and Kleene's Recursion Theorem
I might need some help with the following question.
Given a Partial Combinatory Algebra, we can define the fixed point combinator $Y := [\lambda^{*}xy.y(xxy)][\lambda^{*}xy.y(xxy)]$. How does this ...
0
votes
0answers
25 views
why does the pumping lemma want us to only consider the first repitition of states?
In Sipser's Intro to Theory and computation, He writes:
I don't understand the constraint on x. Shouldn't it be just y <=p? (Equal bc in the case when machine M runs through all states p) Making ...
1
vote
0answers
24 views
Questions about Seth Lloyd's Programming the Universe?
I have been interested in Seth Lloyd's cosmological model (which proposes that the universe is a computer: https://en.wikipedia.org/wiki/Programming_the_Universe, https://arxiv.org/abs/quant-ph/...
1
vote
1answer
26 views
Prove that there is no computability reduction HP $\le$ $\Sigma$*
I tried to prove in negative way that there is computability reduction HP $\le$ $\Sigma$* and accept contradiction because of HP $\in$ RE and $\Sigma$* $\in$ R but it feels that is not strong ...
0
votes
1answer
42 views
prove that there is a complete language in $L \cup \{A_{TM}\}$
$A_{TM} = \{\langle M,w\rangle\mid w\in L(M)\}$
$L$ = complexity class containing decision problems that can be solved by a deterministic Turing machine using logarithmic space
Given the language $L ...
1
vote
1answer
30 views
It is decidable whether a pushdown automaton will accept a word? [duplicate]
I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable.
I would say that you can simulate a push down automaton with a Turing Machine and, if it ...
1
vote
2answers
42 views
L(M)=L where M is a TM that can move right or stay, so L is decidable
Suppose that L(M)=L where M is a one tape TM that can move right or stay.
I need to Show that L is decidable.
I thought of reducing a PDA to this TM, since moving to the right is equivalent to ...
8
votes
3answers
3k views
Show that there are infinitely more problems than we will ever be able to compute
I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot ...
0
votes
1answer
123 views
What does it mean for a TM to solve a problem?
When we say a TM solves a problem, what does this mean?
2
votes
1answer
60 views
Difference between multi-tape Turing machine and single tape machine
A beginner's question about "fine-grained" computational power.
Let $M_k$ be a $k$-tapes turing machine, and let $M$ be a single tape turing machine. We know that $M_k$ and $M$ both have the same "...
1
vote
2answers
42 views
Is a language whose Turing Machine doesn't halt for some positive cases but for others does not recursive?
Say language $L$ is recursively enumerable, but not recursive.
Say $a$ and $b$ are symbols of the alphabet and $w$ a word.
Say we have the following language:
$L' = \{ aw | w \in L \} \cup \{ bw | w \...
3
votes
1answer
36 views
How to prove the union of languages recognized by a set of turing-recognizable Turing machines is also turing-recognizable?
Let $G = \{\langle M_1\rangle, \langle M_2\rangle, \langle M_3\rangle,\cdots\}$ be an infinite turing recognizable language, whose members are descriptions of turing machines.
How can one prove that ...
1
vote
1answer
68 views
How to determine if this problem is decidable?
I am currently stuck on the following problem:
Given a WHILE-program P and the knowledge that all input variales are set to 0, is it decidable if a specific instruction is reached 1000 times?
My ...
0
votes
1answer
21 views
Getting from one language to the other using closure properties(automata) [duplicate]
I am trying to deduct how i can, using closure properties, deduct that since the following language is not context free $$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}...
2
votes
2answers
71 views
Using pumping lemma to show a language is not context free(Complicated)
How can i show that the following long language is not context free using the pumping lemma?
$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}...
0
votes
0answers
13 views
Herbrand structure of satisfiable clauses
Hello I am torn with the following clauses to either prove satisfiability or non satisfiability.
I am looking for the Herbrand structure of these clauses (if there are satisfiable).
(Satisfiability ...
-1
votes
1answer
60 views
Is halts-if-valid decideable?
I have a suspicion that Turing's famous proof that the halting problem is undecidable may not prove exactly what people assume that it proves.
It may only prove that it is possible to limit the ...
0
votes
1answer
45 views
Is function `number of TM which terminates on an empty word` computable?
Let f: N → N be a function where ...
0
votes
2answers
31 views
Does there exist an undecidable problem such that the answer is YES for exactly one input to a UTM, and NO for all others?
Suppose I have a universal Turing Machine (UTM) which accepts some input in binary. Is there a computational problem such that the answer to the problem is YES (accepting) for exactly one input (and ...
-2
votes
1answer
66 views
Church Turing thesis [closed]
What is the exact statement of the Church Turing thesis?
Is it fair to say anything computable in the physical world can be computed by a Turing machine? If so, how does a Turing machine handle ...
5
votes
4answers
2k views
Are Finite Automata Turing Complete?
Something is Turing Complete if it can be used to simulate any Turing Machine.
So, can a Finite Automaton simulate a Turing Machine?
On the question Can regular languages be Turing complete? they ...
0
votes
1answer
19 views
In a Turing machine, what is the difference between the instruction table and the algorithm?
In a Turing machine, what is the difference between the instruction table and the algorithm?
The instruction table seems to be an algorithm for completing the task no?
3
votes
1answer
40 views
Uncomputably coded model of computation
There are many different but equivalent models of computation. I assume their equivalence is shown by coding input of one model to the input of the other model and making an argument why should there ...
1
vote
1answer
74 views
Is “Query Equivalence” decidable?
I have studied in my Computability course that it is impossible to design an algorithm $A(x,y)$ which decides, for every couple of programs ($P_1$, $P_2$), whether they are equivalent (e.g. $\forall d ...
4
votes
1answer
251 views
How does a Turing machine with one tape read its input?
It's often implicitly assumed that we don't have to pay much attention to the difference between the program (which specifies the function being computed) and the input (the value on which that ...
-1
votes
1answer
78 views
Can we find every 216 digit number combination? [closed]
This question popped to my head when I watched Pi where the mathematican told the Jews "Didnt you calculate every 216 digit number allready?"
So I want to find every possible 216 digit number ...
2
votes
1answer
19 views
Proving a language comprised of 2 languages is regular(with suffix and prefix)
I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular:
$$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\...
0
votes
1answer
48 views
Advantages of Lambda calculus over Turing machine and vice versa [closed]
What kind of advantages does Lambda calculus have over Turing machine, and vice versa?
4
votes
1answer
24 views
Proving a language comprised of 2 languages is regular
So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it.
The question:
$L_1$ and $L_2$ are regular languages over the ...
2
votes
1answer
84 views
Can these two languages be reduced to one another?
Given:
$L_1=\left\{ \left\langle M\right\rangle :L\left(M\right)\ni w_{0}\right\}$
$L_2=\left\{ \left\langle M\right\rangle :L\left(M\right)=\left\{ w_{0}\right\} \right\}$
I believe I've managed ...
2
votes
1answer
35 views
Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?
We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^* $ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ ...
1
vote
1answer
43 views
Examples for Partial Combinatory Algebras
I am currently working on my Bachelor thesis about Turing Categories (see Introduction to Turing Categories [1]). In this context I got some questions regarding Partial Combinatory Algebras (PCAs), ...
