Questions tagged [computability]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
32 views

Proof with induction even number of letter

I have to proof that in a word $w$ the number of the letter d is always even. Let $L \subsetneq \Sigma^*$ be a language over the alphabet $\Sigma = \{a,b,c,d\}$ such that a word $w$ is in $L$ if and ...
0
votes
1answer
38 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
41 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
29 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
45 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
29 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
17 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
41 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
25 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
13 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
28 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
17 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
29 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
27 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
73 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
25 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
88 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
156 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
106 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
42 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
57 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
77 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
78 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
25 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
28 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
43 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
37 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
45 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
134 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
44 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
41 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
74 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
22 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
77 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
14 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
46 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 ...