Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,969
questions
0
votes
1
answer
11
views
Prove that the problem MATCH is NP-complete
The problem MATCH is defined as follows: given a finite set S of strings of length n over the alphabet {0, 1, ∗}, determine if there exists a string w of length n over the alphabet {0, 1} such that ...
0
votes
1
answer
11
views
Confusion with Execution of NDFA
I do not understand the "execution graph" (I think that's what it's called) of the following Non-Deterministic Finite Automata, given on pg 48-49 of Sipser's Intro to TCS (3rd edition):
And ...
0
votes
1
answer
26
views
Let A, B two languages such that A=B does that implies that coA=coB
I'm getting to a problem while studying my computability and complexity exam.
If two languages A and B, such that A=B does that implies that coA=coB?
And in general if two language are describe by ...
- 1
0
votes
1
answer
42
views
ASCII invariant string for base64 Encoding
I know the basics about base64 encoding, but thinking about it abstractly I have a theoretical question.
If we consider base64 a mathematical function(in our case computable), Does there exists an ...
- 153
0
votes
0
answers
37
views
Can a computer demonstrate that a topological space is compact?
Since all admissible spaces are second-countable and $T_0$, along with Urysohn's metrization theorem, this gives the hierarchy of topological properties of admissible spaces as Hausdorff ⇐ metrizable ⇐...
- 241
0
votes
1
answer
53
views
Reddiag being a calculable function (Gödel, Escher, Bach)
In Gödel, Escher, Bach Chapter XIII: BlooP and FlooP and GlooP, Douglas Hofstadter states that:
This puts us in the uncomfortable position of asserting that people can calculate Reddiag[N] for any ...
- 103
14
votes
2
answers
3k
views
Ackermann Function without Recursion or Stack
I have been studying the necessity of a WHILE loop when defining the Ackermann Function.
I am looking to write a program to compute the Ackermann function in a high level language such as Python or ...
- 143
0
votes
1
answer
49
views
Is pumping lemma not applicable for every 'long enough' string in the language?
I recently learnt that a subset of a regular set may not be regular. This is causing me confusion as I imagined if a set is regular then every string longer than $p$ can be pumped in the language. So ...
- 15
0
votes
1
answer
30
views
If a language is undecidable, then its complementary language must also be undecidable?
Reference from here If a Language is Non-Recognizable then what about its complement?
There exist complementary languages of unrecognizable languages that are recognizable, and there exist ...
- 195
0
votes
1
answer
22
views
Unrecognizable languages must be undecidable?
A decidable language must be recognizable.
Unrecognizable languages must be undecidable?
I want to know more about the relation of undecidability and unrecognizability
- 195
0
votes
1
answer
32
views
If the complementary language of an recognizable language is a non-recognizable language, is the recognizable language a non-decidable language?
The complementary language of a recognizable undecidable language is not recognizable.
If the complementary language of an recognizable language is a non-recognizable language, is the recognizable ...
- 195
0
votes
0
answers
16
views
If $B \in RE$ then $A \in RE$ - Reduction
I know that if there is a Turing Reduction from $A$ to $B$, say $A \le_T B$, and $B \in R$ then $A \in R$.
I also know that Turing Reduction is for Decision, and not Recognition.
Is it possible to ...
- 37
0
votes
0
answers
59
views
If a Turing machine can compute any computable problem how can Turing completeness be achived?
To my knowledge a Turing machine is able to compute anything considered computable.
I got the definition of Turing completeness from this answer Explain the difference between Turing Complete and ...
0
votes
0
answers
25
views
How to think about blank symbol when Turing Machine used as a function?
Turing Machines can be used to compute functions.
For example f(x)=x-1.
0011 is on the tape. Turing Machine computes for some ...
- 299
1
vote
1
answer
55
views
Turing Machine, UNLIMITED number of steps left or right on the tape?
In the Church-Turing thesis Wiki page, there are a set of descriptions of the "behavior of a computor—`a human computing agent who proceeds mechanically'". I am content with all of them, ...
- 604
0
votes
0
answers
31
views
Equivalence for Turing Machines is not Recognizable - Reduction DOUBT
I have a big doubt on this video about $EQ_{TM}$, especially on minute 5:11.
Why is he saying that to reduce $ A_{TM}\lt_{m}\overline{EQ_{TM}} $ we need to create a machine M that rejects every input?
...
- 3
0
votes
1
answer
42
views
Is a problem in NP if it runs in P time on a NDTM, verifiable in P on a DTM, but solution doesn’t halt on a DTM?
Say there was a decision problem which was solved optimally in polynomial time on a non-deterministic Turing machine, and verifiable in polynomial time on a deterministic TM, but would not halt when ...
4
votes
1
answer
65
views
Self referential hash function possible?
Is there a hashing function $f$ that for each input $x$ if $f(x) = y$, then $f(x \, || \, y) = y$? In other words, if we concatenate its output with the input, the result will not change.
Furthermore, ...
- 93
0
votes
0
answers
19
views
Order of time complexity in computing $R\sin(2\alpha)$ VS $2R\sin(\alpha)\cos(\alpha)$
I was wondering, in terms of complexity and "precision", what are the differences, if any, netween the computation of
$$2R \sin(\alpha)\cos(\alpha) \qquad \qquad \text{and} \qquad \qquad R\...
- 101
0
votes
1
answer
41
views
Decidable or Not: Set of all Turing Machines M that on input w uses all states of M
Show that the following language or problem is not recursive:
$$
L=\{\langle M,w\rangle\mid \text{computation of TM } M \text{ on input } w \text{ uses all states of } M\}
$$
I was trying to prove it ...
- 3
0
votes
1
answer
87
views
Indices of Turing machine on different arity inputs
Let $\Sigma$ be an alphabet, and denote by $\mathrm{ind}(\varphi_M^{(k)})$ the index set (w.r.t some numbering) of the $k$-ary partial computable function $\varphi_M^{(k)} : (\Sigma^*)^k \rightarrow \...
0
votes
2
answers
56
views
Prove that if a language is in co-RE it doesn't mean that it's mapping reducible to another language
Prove/disprove: if $L\in \text{coRE}$ then $L$ is mapping-reducible to $\text{PAL}_{\text{TM}}$, where
$\text{PAL}_{\text{TM}} = \{~\langle M,w\rangle ~|~ M ~\text{is a TM and}~w~\text{is a palindrome}...
- 167
0
votes
1
answer
29
views
turing machine to add each number with the one next to it
im trying to make a turing machine that adds a number with the one next to it on the right. and after, it replaces that number with the result of the addition.
for example if input is 1012, 1+0=1 (...
- 1
0
votes
0
answers
40
views
$L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$
About the language $L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$
I want to determine if it is in RE / coRE or neither.
I think that I found a mapping reduction from $\overline{A_{TM}}$ to $L$, ...
- 37
-1
votes
1
answer
79
views
In computational creativity, how do you measure how creative something is?
In computational creativity, how do you measure how creative something is?
Let's say you have to compare a piece of music written by Bach and then compare it to Chopin, how would you evaluate how ...
- 1
0
votes
1
answer
50
views
Using hypercomputation for "impossible" problems?
In mathematics and philosophy there are some unsolvable problems like Russell's paradox or the liar's paradox that are usually said to be undecidable... There are also other "impossibilities"...
- 101
1
vote
1
answer
44
views
Instances of simulating lambda calculus?
There are a ton of resources on the web devoted to proving some esoteric language is Turing complete by simulating arbitrary turing machines. I have an esoteric language I want to prove is complete, ...
- 225
1
vote
1
answer
45
views
Mapping reduction - Bit Flip
Let $L=\{<M> | M$ is a TM, $L(M)\ne \emptyset$ and $\forall x\in L(M), \overline{x} \notin L(M) \}$
While $\overline{x}$ is the bit flip of $x$.
I want to show a mapping reduction to prove that ...
- 37
0
votes
2
answers
85
views
Is the function that computes the minimum of a countable set computable?
Given $A$ a countable set of numbers and $\min$ the function returning the minimum of a set (if exists).
Is $\min(A)$ computable? My first try is thinking $A$ as infinite list $A = [a_0, a_1, a_2,...]$...
- 13
1
vote
1
answer
39
views
Finding a decider
Let $L\in R, L_2\in RE$ and $n\in N$.
Define $L_n=${$w|w\in L \vee (w\in L_2 \wedge |w|\leq 𝑛)$}
Find a decider for $L_n$
For the right hand side, I thought I could check the length of 𝑤 and then ...
- 167
-4
votes
1
answer
81
views
can you find an algorithm for this function?
consider the following function
$$
\begin{align*}
f(m,n) &=
\begin{cases}
k & \text{if program $m$ halts on input $n$ after $k$ steps} \\
m & \text{if program $m$ loops on ...
- 75
0
votes
1
answer
112
views
Is infinite union of RE a RE?
Is an infinite set of RE languages create a language that is also RE?
I think it's true, and my first intuition is to try induction to prove this statement.
Am I on the right way?
Thanks!
- 37
-1
votes
1
answer
30
views
Prove that $L = \{ \langle M \rangle | \text{ M is a PDA, L(M) contains at least 1 string w that } |w| \leq n \}$ is recursive?
Description
Similar to the encoding of a Turing Machine, we can encode a Push-Down Automata. Denote $\langle M \rangle$ as the encoding of PDA M, and a natural number n, is language $L = \{ \langle M \...
- 3
0
votes
0
answers
21
views
Minimize the number of states of a Turing Machine [duplicate]
Is there a condition to decide whether a Turing Machine have an equivalent one with smaller number of states?
Thanks!
- 37
0
votes
1
answer
50
views
Prove that $L = \{a^rb^qc^q\}$ where $q > 0$, $r \geq 0$ is not a regular language
I've been working on this question for a few hours now and I've been trying to figure out the question above. My biggest problem is that I don't know what to do with the $>$ and $\geq$ symbols when ...
- 1
0
votes
1
answer
33
views
Show that Lu is m-reducible to the language L = {⟨M, x⟩ | M(x) terminates with an empty tape}
Question: Given a language L, L = {⟨M, x⟩ | M(x) terminates with an empty tape}, show that Lu is m-reducible to L by finding a computable function f: Σ* -> Σ*, where for every w, w ∈ Lu if and only ...
- 1
0
votes
0
answers
49
views
I would not be able to get my simulation in my life time
I am running a simulation on my computer. I tried to multiply two polynomials $g(x), h(x)\in GF(2)[x]$, with $degree(g(x))= 8165$, and $degree(h(x))=25$. This multiplication took almost $20$ minutes ...
- 101
0
votes
0
answers
48
views
How are enumerator programs formally defined?
Enumerator programs appear quite often in even an elementary computer science textbook without a formal definition. It does not seem to fit the standard definition of a computable function (through mu ...
0
votes
0
answers
25
views
Prove that a language does not many one reduce to its complement
I am trying to prove that an undecidable language $L$ is not many one reducible to its complement.
The problem goes as follows:
Formally prove that $L \not\leq_m \overline{L}$ for any undecidable $L$....
- 1
0
votes
1
answer
131
views
Does the halting problem belong to NP class of problems?
On the one hand it does not belong to NP problems because it simply is not solvable and is undecidable and on the other hand it is an NP problem because there are claims that it is NP-hard and ...
- 1
1
vote
1
answer
48
views
Is it possible to determine if a 0-arity function [a program with no input] will always terminate
The halting problem concerns programs which take input.
By framing the halting problem on the diagonal argument it is clear why this is so.
What about programs with no input, constant functions.
Can ...
- 143
0
votes
3
answers
83
views
Are there some programs for which the only proof of termination, is running of the program, and waiting to see if it stops, no matter how long?
The halting problem is semi-decidable, which means that if a program terminates then it will always be able to be determined.
Some programs can be proven to terminate without running them, with say:
...
- 143
0
votes
1
answer
43
views
How does one define transcendental numbers (such as Pi) in theory of general recursive functions
On a turing machine and in the lambda calculus one can define transcendental numbers such as Pi, the golden ratio, etc.
These are computatible functions with 0-arity that never terminate.
In the ...
- 143
0
votes
2
answers
65
views
What is the meaning of the term "computational process" in the book SICP?
I'm trying to read chapter one of the famous book : Structure and Interpretation of computer programs.
The chapter one starts with a mysterious paragraph:
We are about to study the idea of a ...
0
votes
1
answer
51
views
How to show that the following function $F$ is primitive recursive?
We want to show that the following function $F$ is primitive recursive (using the primitive recursion scheme) :
For all $x,p,a\in \mathbb N$,
$F(p,a,0)=g(\eta^{p}(a))$
$F(p,a,x+1)=h(\eta^{(p-(x+1))}(...
- 199
0
votes
1
answer
220
views
Are these functions computable?
consider $g$ and $f$ and $h$ as
$
\begin{align*}
g(m) &=
\begin{cases}
1 & if\;program\;m\;halts\;on\;input\;m \\
0 & otherwise \\
\end{cases}
\end{align*}
$
$
\begin{...
- 75
0
votes
1
answer
42
views
Infinite loops and the computability of mapping reductions
Consider the reduction $A_{TM} \le_m \overline{E}_{TM}$, where
$$A_{TM} = \{\langle M, w \rangle \mid \text{TM $M$ accepts $w$}\}\text{, and}$$
$$\overline{E}_{TM} = \{\langle M \rangle \mid \text{TM $...
- 105
0
votes
1
answer
70
views
Equivalence between Lambda Calculus [Church] and Computable Partial Functions [Godel]
In order to show that Lambda calculus and Turing machines are equivalent it is sufficient to show that you can simulate one in the other [both ways].
We can observe it in action. Can one do the same ...
- 143
1
vote
0
answers
30
views
"Reasonable" requirements for a computation model to be equivalent in power to a Turing machine
I was reading through Sipser's "Introduction to the Theory of Computation" and in it, he states that all computational models with unrestricted access to unlimited memory are "...
- 11
1
vote
1
answer
68
views
Is it computable to find the cardinality of intersection of two recursively enumerable sets?
I am well aware that recursively enumerable sets (which are subsets of $\mathbb N$) are closed under intersection. What is more interesting is whether or not the cardinality of the intersection is ...
- 121