Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,526
questions
0
votes
1answer
10 views
Can a computable program have an infinite output?
Can a computable program produce an infinite output from its (presumably finite) input?
*I wouldn't think so for similar argument as to why it can't compute over an infinite input.
A follow on (...
-1
votes
1answer
20 views
if there is no reduction from A to B
I'm facing the following question :
If there is no $𝐴\leq_𝑚𝐵$ reduction,
does this necessarily mean that A is not decidable?
for any choice of B.
thanks in advance.
3
votes
0answers
61 views
Undecidability of language involving two TMs
I am currently browsing the lecture notes on computability/decidability and I have encountered the following exercise I am unable to solve.
Given $M_1$, $M_2$ Turing machines, is it true that for ...
0
votes
0answers
21 views
Use the Rice's theorem to prove that the following property of a Recursive Enumerable language L is undecidable
This exercise was taken from the book "Languages and Machines: An Introduction to the Theory of Computation" by Thomas Sudkamp. It refers to exercise 12 (b) chapter 12. Given a language L which is ...
3
votes
1answer
93 views
Compare two complexity functions having the same asymptotic complexity
For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found:
$A1: T_{A1}(n)=4n^2 +7log(n^2)$
$A2: T_{A2}(n) = 4T(n/2) + log(n)$
Say, technically ...
0
votes
0answers
16 views
Proof by reduction that the Universal Language is not recursive using the complement of the Diagonalization language
I have the following proof which I don't fully understand.
L D/ is the complement of the Diagonalizaton Language.
L U is the Universal language.
Assume U* is a TM for Lu which always halts. ...
0
votes
1answer
35 views
Are Turing unrecognizable and undecidable languages, recognized and decided by hyper computation?
Do the hyper computing machines/models that are supposed to be more powerful than Turing machines, capable of recognizing and deciding the languages that are not recognizable/decidable by Turing ...
0
votes
1answer
25 views
In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?
Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction ...
0
votes
0answers
11 views
Do $PR/Poly$ solve the halting problem of Turing Machine?
I know that $R/Poly$ solves the halting problem, as we can have the program that runs for longest time as advice and check which halts earlier. But what if we weaken the $R$ into something, like $PR$?
0
votes
1answer
28 views
Would models of computation in other conceivable universes be Turing complete?
I'm interested in gathering some references that discuss the topic of the relationship between computation and physics.
Specifically, I'm interested in investigating two points of view:
our current ...
1
vote
1answer
65 views
Can a subset of indexes of a partial recursive function be recursively enumerable but not recursive?
Consider a Gödelian numbering of partial recursive functions. Consider the set of indexes corresponding to some function $\phi$. It may be seen that this set is not recursively enumerable. Does this ...
2
votes
2answers
88 views
Grammar with fewest variables
I am looking over a past exam for a theory of computation class I am taking, and unfortunately no solutions are provided. I am stuck on this question, and would greatly appreciate any help or hints.
...
1
vote
1answer
14 views
Is checking if the length of a C program that can generate a string is less than a given number decidable?
I was given this question:
Komplexity(S) is the length of the smallest C program that generates the string S as an output. Is the question "Komplexity(S) < K" decidable?
With respect to ...
0
votes
0answers
58 views
Restriction: polynomial time decision of instance is why needed to “decision Problem”?
I am reading book "combinatorial optimization 3rd edition(Bernhard Korte、 Jens Vygen)".
(latest version is sixth.)
There are some discriptions in this book that I don't understand
Not all binary ...
0
votes
0answers
16 views
Proving the existence of a $\Pi_1$-sentence in True Arithmetic that is independent of Peano Arithmetic
I am trying to wrap my head around how to prove the following statement:
There exists some $\Pi_1$-sentence $A$ such that $A \in \textbf{TA}$ but $\{A, \neg A\} \cap \textbf{PA} = \emptyset$.
$\...
1
vote
2answers
42 views
Why can't we prove decidability of $L= \{ \langle M \rangle : M$ accepts $ \epsilon \}$ with a configurations graph?
Since every deterministic Turing Machine can be translated to a graph of configurations such that $M$ accepts a word $w$ iff there is a path from the initial configuration that matches $w$ to an ...
4
votes
1answer
69 views
Is there a model of ZF¬C where some program always terminates but has no loop variant?
Wikipedia has a proof that every loop that terminates has a loop variant—a well-founded relation on the state space such that each iteration of the loop results in a state that is less than the ...
5
votes
0answers
47 views
Analogue of the topology-computability correspondence for computational complexity
There is an interesting correspondence between notions of topology and notions of computability theory originating from the ingenious idea of Dana Scott to identify computable functions with ...
2
votes
3answers
73 views
Are there any problems that reduce to the halting problem?
I'm reading through sipser and there is a lot of computability problems that the halting problem reduces to, i.e. if $A_{TM} = \{\langle M,w\rangle : M$ accepts input $w\}$ then $A_{TM} \leq P$ where ...
0
votes
0answers
32 views
Why does such reductions work [duplicate]
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
26 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
23 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
80 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
28 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
18 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
27 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
27 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
72 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
94 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
53 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
54 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
28 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
53 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
313 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
61 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
47 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
45 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
50 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
37 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
21 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
30 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
46 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
29 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
30 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
24 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
50 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
21 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
33 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
70 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 ...
