Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [computability]

Questions related to computability theory, a.k.a. recursion theory

Filter by
Sorted by
Tagged with
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 ...