Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,508
questions
0
votes
0answers
20 views
Why does such reductions work
In class we saw examples of reductions like from Independent Set (IS) to Longest common subsequence (arbitrary number of sequences) (LCS)
$V = \{v_1,\ldots,v_n\} E =\{ e_1,\ldots, e_m \}$
The ...
1
vote
1answer
24 views
Reductions from non decision problems
I want to show a minimization problem $Y$ has no approximation factor of 1.36. To be more specific the problem $Y$ is the exemplar distance problem between two genomes. Could I reduce from the min ...
1
vote
0answers
21 views
Turing machine that can read and write simultaneously equivalence proof
How would I go about proving that a TM that can both read and write at the same time is equivalent to a typical TM?
For constructing a read+write TM from normal TMs, my idea is to split the state of ...
2
votes
1answer
57 views
How undecidable is it whether a given Turing machine runs in polynomial time?
The proof of Theorem 1 that PTime is not semi-decidable in this recent preprint effectively shows that it is $\mathsf{R}\cup\mathsf{coR}$-hard. The proof itself is similar to undecidability proofs at ...
1
vote
0answers
24 views
Union of infinitely many recursive sets that is not recursive but recursively enumerable?
I am looking for an example such that the union of infinitely many recursive sets is not recursive but recursively enumerable.
I was thinking taking $S_i=\{i\}$ and then taking the union of these ...
1
vote
1answer
16 views
Turing machine with k-tape, tape of output
Consider a Turing machine with input alphabet $\{a,b\}$ that computes the following function:
$$
f(w, v) =
\begin{cases}
w & \text{if } \operatorname{length}(w) > \operatorname{length}(v), \\
...
0
votes
0answers
23 views
How to proof a function is not computale [duplicate]
I wish to undestand how to proof a function is/is not computable. I found this example online (without solution) beacuse I was thinking was easy to understand, but I am stuck in understanding how to ...
0
votes
1answer
21 views
On the computable function of a problem that halts
Let's say program $P$ with given input $i$ is found to halt (or doesn’t halt) by a Turing machine. Is it true that the same program $P$ with input $F(i)$ also halts (or not, respectively), where $F$ ...
0
votes
1answer
67 views
Deciding whether set of running times is infinite
I have a language $\mathrm{Count}(M)$, defined below, and a finite number $k$.
\begin{align}
\mathrm{Count}(M)= \{k \in \mathbb{N} \mid \text{there exists some input on which $M$ halts after exactly ...
1
vote
1answer
87 views
Is my formal definition of programming language correct?
I found this formal definition of a programming language in the 1973 paper Formal definition of programming languages by Terrence Pratt.
PL is a formal language endowed with two structures: a ...
0
votes
0answers
52 views
If base 2 looks like a square wave, and base 3 looks like this, what does base e look like?
In computing, base 2 is a 0 and a 1 / on and off in a transistor. Base 3 is -1, 0 and 1.
Electronically/in computing how would/could base e be represented visually?
0
votes
0answers
53 views
Why do intuitionists accept the nonconstructive proof that the halting problem is undecidable? [duplicate]
On the intuitionism page at Stanford Encyclopedia of Philosophy (SEP), it's said in Section 3.3 that
Because of the finiteness of a natural number in contrast to, for example, a real number, many ...
0
votes
1answer
26 views
Designing a PDA that keeps track of the stack size
Would it be possible/legal to design a PDA that can use the stack as a way to keep track of the number of inputs seen? (i.e the size of the stack would act as some sort of counter).
What I was ...
2
votes
1answer
45 views
Is this language Recursively Enumerable or Not RE?
$L = \{\langle M, k\rangle : M\;\text{is a Turing Machine and } |\{w \in L(M) : w \in a^*b^*\}|
\geq k \}$
My Interpretation of language is that $L$ is a language which contains Turing machine ...
0
votes
1answer
145 views
Turing Machine to return all prime numbers
My task is to design Turing Machine that ignores its input and returns all the prime numbers. I have some basic idea how to do that but I am not completely sure whether my approach is correct or not.
...
0
votes
1answer
55 views
Decidable questions of undecidable problems
Even if there is no general algorithm to decide if any program will halt, but there could be properties or meta-questions about the programs that is decidable. For example, given program $A$ and a ...
-3
votes
1answer
46 views
I want to solve this question for algorithm, please [closed]
Write an algorithm that calculates the monthly payment of a bank loan with
a fixed interest-rate. Given the principal amount, the fixed interest rate, the number of
years to pay the loan, you can ...
2
votes
1answer
36 views
Showing the following language is decidable
Let $BAL_{DFA} = \{<M> \mid M \text{ is a DFA that accepts some string containing an equal number of 0's and 1's } \}$ Show that $BAL_{DFA}$ is decidable.
Generally such questions seem to be ...
0
votes
0answers
47 views
Deciding whether $f(x) = f(y)$ is beyond RE and coRE
I would like to prove that the following subset is outside both RE and coRE:
$$A = \{ (p, (d_1, d_2,\dots, d_k)) \mid \text{for each } 1 \le i,j \le k, \; [p]d_i = [p]d_j \}, $$
where $p$ is a ...
0
votes
1answer
31 views
Are models of computation closed under composition?
It's common to ask whether a particular class of languages $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$, for some alphabet $\Sigma$, is closed under complement, or union, or intersection, or ...
0
votes
1answer
20 views
Busy-Beaver-like question for WHILE-Programs (Theoretical CS)
So this is exam-task is called "Busy WHILE-Programs"
In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following:
...
1
vote
1answer
25 views
Expressing partial decidability using existential quantification
def.
A predicate M(x,y) is partially decidable if the function f given by " f(x,y) = 1(if M(x,y) holds), f(x,y) = undefined(otherwise) " is computable.
Thm.
If M(x,y) is partially decidable, then so ...
1
vote
1answer
43 views
What Is the Complexity Class of Deciding Whether a Problem Is in NP? Is It Decidable?
Title says it all, but to clarify:
Define a problem, called $IsInNP$, as follows:
Given a Turing Machine $M$ that always halts, $IsInNP$ is the problem of deciding if the problem that $M$ ...
0
votes
0answers
27 views
What does B compute in Recursion theorem
I am reading Michael Sipser's book for this theorem
Recursion theorem Let T be a Turing machine that computes a function t
: Σ* × Σ* → Σ* . There is a Turing machine R that computes a function
...
1
vote
1answer
26 views
Does Types and Programming Languages use a recursive equation to define a recursive type or its generator?
In Types and Programming Languages by Pierce et al:
The recursive equation specifying the type of lists of numbers is similar to the equation specifying the recursive factorial function on page 52:
...
1
vote
1answer
16 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
49 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
29 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
20 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
32 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
69 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
35 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
18 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
23 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
75 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
28 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
89 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
158 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
111 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
44 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
34 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
61 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
83 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.
...
2
votes
1answer
83 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
27 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
26 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
30 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
44 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
41 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
48 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 ...
