Questions tagged [computability]

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

Filter by
Sorted by
Tagged with
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 ...
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 ⇐...
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 ...
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? ...
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 ...
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 (...
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 ...
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 \...
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 ...
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 "...
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

1
2 3 4 5
40