Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1
vote
1answer
22 views
Recognizer to check if the language of a Turing machine contains a finite subset
Let $B = \{ 123 \}$.
Note that $B$ is finite.
Let $L = \left \{ \left\langle M \right\rangle | M \text{ is a Turing machine such that } B \subseteq L(M) \right\}$.
Is it sufficient to show that $...
-2
votes
0answers
15 views
POS SYSTEM UNABLE TO DETECT THE MASTER COMPUTER [on hold]
A pharmacy has 1Gbps network with 4 computers.
The network has Internet access via an ADSL/2 router/modem.
The LAN is configured on the 192.168.4 subnet.
DCHP/DNS is provided by ADSL router.
The ...
2
votes
2answers
55 views
Is determining if a Turing machine runs in constant time decidable if one assumes it halts?
As the title states, is determining if a Turing machine runs in constant time decidable if one assumes it halts?
The decision problem, more formally:
Given a Turing machine $M$ where it is assumed ...
2
votes
1answer
42 views
Can generalized Turing machines compute all reals?
Super-recursive algorithms are theoretical super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines.
In this entry it ...
5
votes
1answer
31 views
Proving a set is at a certain level of the arithmetical hierarchy
I'm interested in methods for proving a set is at some level $\Sigma^0_n$ (or $\Pi^0_n$) in the arithmetical hierarchy, and in particular, proving it is at the level with the smallest $n$ possible.
I ...
0
votes
0answers
11 views
Denset-k-subgraph to ILP reduction [closed]
I have exercise:
Show reduction Denset-k-subgraph to ILP (Integer Linear Porgramming).
(Denset-k-subgraph is problem where there is graph G = (V, E) and two
natural numbers k and t. We are ...
0
votes
0answers
20 views
Church-Turing thesis and hypercomputation?
The Church-Turing is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being following an algorithm, ignoring resource ...
1
vote
1answer
33 views
A language which is neither r.e. nor co-r.e
First, consider $$L_\exists=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts some input}\}$$
is RE. I tried to construct a Turing machine:
...
1
vote
1answer
36 views
Prove Halting on all Inputs is not in RE simulation
I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine ...
0
votes
1answer
29 views
Can a non-RE language be reduced to an RE language?
Let $L$ be recursively enumerable and $U$ be non-recursively-enumerable. Is it possible to reduce $U$ to $L$ recursively, $U\leq_R L$? Personally, I do not think this is possible. If we can reduce $U$ ...
1
vote
1answer
43 views
Reduction between these two languages
I'm given $L_\cap=\{\langle M_1\rangle\#\langle M_2\rangle\mid L(M_1)\cap L(M_2)\neq\emptyset\}$ and $L_U=\{\langle M\rangle\#w|M \text{ accepts } w\}$.
How can I reduce the former to the latter: $L_\...
1
vote
2answers
44 views
Pumping Lemma. Why is there a word w in L for infinite languages with n≤|w|≤2n
The following comment on an other question says that if we have an infinite language L that satisfies the pumping lemma for regular languages then we have a word with n≤|w|≤2n which is in L. (n is the ...
2
votes
1answer
46 views
Can one get Turing-completeness without nontermination?
As I'm reading the movfuscator paper by Stephen Dolan, I encounter this claim:
In order to have Turing-completeness, we must allow for nontermination.
This seems like a reasonable statement. But I'...
2
votes
1answer
121 views
Mathematical Problem Solving
Will a study of the mathematical proof of a (data structure and algorithm based) problem, when posed as a proposition, highlight peculiar properties of the problem which may help in designing an ...
1
vote
2answers
39 views
Are all countable partial functions computable?
I know all computable partial functions are countable. Wondering if it is the the other way around as well.
1
vote
1answer
30 views
Rice's theorem applicable to the following language?
Let $L= \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle \} $
be a language where $\langle M \rangle$ is the Code of the TM $M$. $L$ is undecidable.
I've heard that I can't use Rice's ...
1
vote
1answer
37 views
REC and RE under intersection
Would the intersection of a recursive language and a recursively enumarable language be recursive or recurisvely enumbarable or neither?
Assume $L_{3}$ is the intersection of some language $L_{1}$ $\...
2
votes
1answer
38 views
Is there a relation between the size of the domain/range of a function and its computability?
This was a question given in a course, without answer. The referenced literature (just a few books) do not cover it, unfortunately.
I think there is no relation with the range as the range of the ...
1
vote
1answer
56 views
proof of the rice's theorem
Let $P$ be any nontrivial property of the language of a Turing machine. Prove
that the problem of determining whether a given TM’s language has property $P$ is undecidable.
Proof:(This is from sipser'...
1
vote
2answers
58 views
Relation between semi decidable, undecidable and countable sets
I know that
decidable problem: has both counting (bijection with $\mathbb N $) and membership algorithm (TM halts for both member and non member strings )
semidecidable problem: has counting ...
3
votes
3answers
343 views
What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute
If I were to pose the question: "Given a program $P$ containing statement $X$, will $X$ be executed (given enough runs with all possible inputs)?"
This strikes me of being a relative of the Halting ...
0
votes
1answer
57 views
Why a TM with infinite states can decide the halting problem?
Assuming we have a model of TM with an infinite number of states.
The domain and range of the transition function are also infinite.
Given a description of a TM $M$ and a string $w$ how can we use the ...
0
votes
0answers
34 views
Decidablity of time complexity
Let $t:\mathbb{N}\rightarrow\mathbb{N}$ be a time constructible function with $t(n)\geq n + 100$. Show that there is no TM $T$ that given the gödel number of another TM $M$, decides wether or not M is ...
5
votes
1answer
759 views
What is the complement of a language?
If given any language L, how do I find the complement of said language?
I lack the basic understanding required to determine if a language is co-recognizable. I understand that a language, $L$, is co-...
2
votes
0answers
32 views
Is the language $L$ of coded CFG's Turing decidable?
Consider the following language
$L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$}
Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
1
vote
2answers
51 views
Recognizer for decidable language and words it doesn't halt on
Suppose we have a decidable language B (there exists some TM that decides it). Suppose we have another TM M which only ...
0
votes
1answer
26 views
Is the set of surjective recursive functions in RE/coRE?
Let L be a set of recursive funtions with $L = \{i\in \mathbb{N}|f_i\space is\space surjective\}$ where $i$ is a gödel number of f.Is $L\in RE,\space coRE$?
I can't think of a way to show either of ...
1
vote
2answers
100 views
Are the capabilities of programming languages the same?
Is the capability of every programming language the same since it is eventually translated into machine code. Python, Java etc. are all together instructions the CPU is going to process. So, you could ...
0
votes
0answers
21 views
How strong is a FSM with long enough(but not infinite) tape?
Like turing machine, but your tape is finite. To make a program valid it should have a limit result when the length of tape tends to infinity.
Whether the tape has two ends or is cyclic doesn't ...
0
votes
0answers
41 views
Mathematical resource material accompanying TAPL
I'm currently reading Types and Programming Languages by Benjamin C. Pierce and just arrived at chapter 21 Metatheory of Recursive Types.
Prior to this chapter I found the book challenging but ...
4
votes
1answer
56 views
Is Rice-Shapiro theorem bidirectional?
Rice-Shapiro theorem states that
version A
Let $\Gamma$ be a set of computably enumerable sets, and $I = \{e : W_e \in \Gamma\}$ its index set in some admissible enumeration of c.e sets. If $I$...
1
vote
1answer
25 views
Can the complement of an unrecognizable language be a recognizable language?
I know that complement of a language that is recursively enumerable, but not recursive, is definitely not recursively enumerable (or unrecognizable). So my question is what can be said about the ...
1
vote
1answer
32 views
How to prove that a problem is undecidable by using the Halting problem?
I cannot understand how to reduce the halting problem to a property to show that is undecidable.
For example, I have this property of a Turing Machine and I have to prove if it's recursive or not:
"...
1
vote
3answers
61 views
Proof Idea: There are irrational numbers whose decimal expansion cannot be computed
The online lecture I am watching stated a proof idea:
The set of all possible programs is countably infinite, yet
the set of irrational numbers is uncountably infinite.
I don't think this is ...
0
votes
1answer
52 views
Halting problem with extra input
Can there be a function HALT(f, y) so that:
There are some x such that f(x) halts iff there ...
1
vote
1answer
24 views
Is a set $B = \{y, \exists x \in A, f(x)=y\}$ recursive if A is a recursive set and f is a $N->N$ total computable function?
Obviously, B would be recursive if for every TCF f, there was an inverse fuction that would return all possible values, as we could just take these and then check if any of them is in A. However I ...
1
vote
1answer
32 views
Are physical laws uncomputable in any type of computation (according to this article)?
It seems that this article (https://arxiv.org/pdf/1312.4456.pdf) proposes that laws of physics are uncomputable (i.e., they could not be reproduced on a computer), but I'm not sure about it.
In some ...
0
votes
0answers
14 views
Is ${M :|L(M)| \leq 330}$ Recursively enumerable? [duplicate]
M is a Turing machine description, L(M) is the language recognized by M and |L(M)| is the size of this language.
2
votes
1answer
86 views
Which one of these two sets is computably enumerable?
M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language.
{M : |L(M)| <= 330}
{M : |L(M)| >= 330}
I don't quite understand what this question is asking. ...
1
vote
1answer
37 views
Reduce ATM to REGULAR_TM
Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$.
Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\...
4
votes
1answer
137 views
Language that fulfills pumping lemma but is not in RE
I am supposed to find a language $$L\subseteq \Sigma ^*, \Sigma \subseteq \mathbb{N}$$ that fullfills the pumping lemma and is not in RE and not in coRE. I've never constructed a language with a given ...
0
votes
1answer
31 views
Are non-regular languages decidable?
Given a language L, I've shown that L is not regular. Can I conclude that it is not decidable or are there non-regular languages that are decidable?
2
votes
2answers
35 views
Quotient in LOOP program [closed]
I want to construct a LOOP-computable program for the integer division (quotient):
x = a DIV b
The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP_(programming_language)
I ...
2
votes
0answers
66 views
What is the relationship between “model of computation” and “algorithm”?
Traditionally, the usual definition you find for model of computation is "an abstract description of how an output is computed given an input" (Wikipedia and my TCS course are my sources, but the ...
6
votes
2answers
1k views
Relation between Undecidable problems and NP-Hard
I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.
And then, I realized that it is not certain where undecidable problems should be placed.
...
2
votes
1answer
39 views
Decidability of factoring algebraic equations
Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution:
$$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$
And some arbitrary factorization constraints, say:...
2
votes
2answers
47 views
Can a RE language be reduced to a non-RE language?
In our lecture notes about many-one reduction we showed that the following statements hold:
$$ L, L' \subseteq \mathbb{N}\space and \space L\leq L'$$
$$(I)\space L' \in RE \implies L\in RE$$
$$(II)\...
0
votes
1answer
30 views
Whether language of all turing machines is decidable or undecidable or semi-decidable?
I recently came across this language:
$L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$
It was asked in the question to find out whether language L is decidable or undecidable.
...
1
vote
0answers
22 views
Can a CFG generate an accepting configuration? - or is there a turing-recognizable CFG language that is not decidable
I could not think of a way to concisely write down my question clearly, but I'd like to ask, from Sipser's book, $ALLCFG$ is an undecidable language (where $ALLCFG$ means that $G$ is a $CFG$ that ...
1
vote
1answer
64 views
Trying to prove semidecidability of an undecidable language
I have been having a hard time understanding whether the set $S = \{ M \mid |L(M)| = 5 \}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, ...
