Skip to main content

Questions tagged [computability]

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

Filter by
Sorted by
Tagged with
3 votes
0 answers
46 views

Is the definition of "computational problem" on Wikipedia correct?

In the https://en.wikipedia.org/wiki/Computational_problem, the first line states: "A computational problem is a problem that may be solved by an algorithm." However, I have doubts about the ...
pabloealvarez's user avatar
0 votes
0 answers
21 views

L in NP and L is coNP-hard=>NP = coNP

How can I prove this: given this 2 sentences 1 <=> 2: There exists a language L ∈ NP that is coNP-hard. NP=coNP. the direction from 2 to 1 I can prove using the concept of NP-cpmplete and etc. ...
user1701057's user avatar
-3 votes
0 answers
36 views

Polynomical reduction from language to NP language

Given a language $L$, if I can deduce that $L \le_p L'$, where $L'$ is in NP, can I conclude that $L$ is in NP too?
user1701057's user avatar
0 votes
0 answers
27 views

Proving that if semidecidable, then computable

Definition: The graph of an n-ary function F is the n+1-ary relation $G_F$ defined by $G_F(a_1,...,a_n,b) \Leftrightarrow F(a_1,...,a_n)=b$. Theorem: if $G_F$ is semidecidable, then $F$ is computable. ...
spacemonkey's user avatar
-1 votes
1 answer
26 views

Create a cfg for the language L = {w ∈ {a,b,c}* : |w| = 3na(w)}

All I know about this language is that it is equivalent to the following: $$L = \{w \in \{a,b,c\}^{∗} : n_b(w) + n_c(w) = 2 * n_a(w)\}$$ but I have absolutely no idea how to create a CFG for it.
AmirMohammad Shakeri's user avatar
0 votes
1 answer
129 views

Analog computers more powerful than turing machines?

Ignoring quantum mechanics for a moment, is it true that analog computers are more powerful than turing machines? for example an analog computer can add two irrational numbers together, but a turing ...
JobHunter69's user avatar
3 votes
1 answer
48 views

Computability- relationship between R, coRE and RE

I am trying to think of a question that discusses the relationship between RE, coRE and R. Namely- is it true that for all For every language 𝐿1∉ RE there exists a language 𝐿2∉ coRE such that 𝐿1∪𝐿...
IVRODB's user avatar
  • 31
0 votes
1 answer
51 views

Why Does Computable Analysis Use Type 2 Turing Machines Over Type 1 TM's?

I've been researching formal models for computing with real numbers and came across the field of computable analysis built on top of specifically the type 2 Turing machine, which allows for ...
KylerAce's user avatar
9 votes
14 answers
8k views

Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

According to the Bekenstein bound, Turing machines are not realizable in real life. So why are they accepted as the standard for effective computation? You may as well consider more powerful machines ...
JobHunter69's user avatar
2 votes
1 answer
41 views

Number of configurations, non-deterministic $LBA$ and $A_{LBA}$

The membership problem $A_{LBA}$ for a deterministic $LBA$ is decidable because the number of configurations that a $LBA$ can assume is finite. Since this number is also finite for a non-deterministic ...
Marcus's user avatar
  • 139
0 votes
0 answers
38 views

Why are languages fed as input into machines/automata as a stream and why do automata read one symbol at a time?

Consider an FSM augmented with a camera. The input is a book. First, the book is already stored without the FSM needing to have states to memorize the input. (The memory used to record the input is no ...
JobHunter69's user avatar
1 vote
1 answer
30 views

Computable function $F$ such that $F(e, x) = f(x), \forall x \in \mathbb N_0$

Is there a computable function $F: \mathbb N_0^2 \rightarrow \mathbb N_0$, such that for every computable function $f: \mathbb N_0 \rightarrow \mathbb N_0$, there exists an $e \in \mathbb N_0$, such ...
Minerva's user avatar
  • 113
0 votes
1 answer
22 views

Are there any example of practical application of counter machines?

I am currently working on a presentation over how counter machines are as effective as Turing machines. During my research, I found out that random access machines are an improved version of counter ...
Nerincet Vonwthaud's user avatar
1 vote
2 answers
66 views

Gödel's theorem and machines' power

I was studying AI and when a question came to my mind. I know that one of the objections to the possibility of a thinking machine examined by Turing is the so called mathematical objection, ...
Amanda Wealth's user avatar
0 votes
0 answers
21 views

Issues in the proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$

I'm studying reducidability in Sipser Book and watching his videos, but I couldn't fully understand his proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$ (p. 218, 3rd ed). Consider this extract: M1 = “...
user169972's user avatar
3 votes
1 answer
101 views

Can remainder mod 2 be efficiently computed from addition and equality?

Suppose I have a programming language all of whose variables have natural number type. (So I cannot form higher-type objects, e.g., lists or trees, of natural numbers.) The only atomic commands I am ...
Siddharth's user avatar
  • 131
3 votes
1 answer
608 views

Can the minimisation operation be seen from a programming language perspective?

If $f$ is a total function $\mathbb N^k\to\mathbb N$, and $g$ is a total function $\mathbb N^{k+2}\to\mathbb N$, then we say that $h:\mathbb N^{k+1}\to\mathbb N$ is definable by primitive recursion ...
Joe's user avatar
  • 133
5 votes
1 answer
329 views

Is every non-recursively-enumerable language RE-hard?

Is every language $L \notin RE$ is $RE$-hard? Similarly, is every language $L \notin RE \cup coRE$ is $RE$-hard and $coRE$-hard? It seems like a simple question but I can't find an answer. I tried to ...
Amit Keinan's user avatar
0 votes
1 answer
57 views

Why is $RP \subseteq BPP$?

Lets define $P_M(x)$ as the probability that machine M accepts x. Let $L \in RP$. Then, if $x \notin L$, we get that $P_M(x)=0$, which is less than $\frac{1}{3}$, so all good here. But if $x \in L$, ...
sadcat_1's user avatar
  • 191
-2 votes
2 answers
79 views

Is there a well-defined bijection between an undecidable language and the set of natural numbers?

The common belief is that every formal language is countable, based on the claim that "every subset of the natural numbers is countable." In the article https://homepage.divms.uiowa.edu/~...
Mofun's user avatar
  • 1
3 votes
1 answer
72 views

Are Primitive recursive functions (with bounded $\mu$ operator) equivalent to other known computational model?

There is a famous equivalence between types of grammars and automatons. However when discussing recursive functions, we only consider equivalence of General Recursive functions with Turing machines. ...
math boy's user avatar
  • 359
4 votes
1 answer
788 views

Are there infinite state machines, and how do their computational power relate to turing machines?

From the internet: ...
JobHunter69's user avatar
0 votes
3 answers
71 views

What is the name of the theory that says that Turing equivalence is universal, and Turing machines are maximally computationally powerful?

In the Chomsky hierarchy, level 0 grammars include all languages that can be recognized by a Turing machine. There is no level -1 (which would represent the class of languages that cannot be ...
Luke Hutchison's user avatar
0 votes
5 answers
2k views

If the set of Turing machines is countably infinite, how can a Turing machine always have a finite set of states?

I have only begun studying this subject and have only completed the first few chapters of the Elements of the Theory of Computation. I have seen the answers (on this site and elsewhere) saying that ...
Wisdom Iwueze's user avatar
1 vote
1 answer
137 views

Draw a finite automation for {w ∈ Σ ∗ | w does not contain the substring 10}

So I am trying to draw a finite automation that has no limits on the length, but cannot have the substring of 10 I created a DFA that could satisfy this requirement,...
cool cat's user avatar
-1 votes
1 answer
83 views

What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?

I originally thought it was 0(01)*(01)0 U 1(01)(01)1 where: two versions: one that starts and ends with 0, the other that starts and ends with 1 connected by plus, which does not mean union of both ...
cool cat's user avatar
0 votes
1 answer
107 views

Decidability of whether a Turing machine accepts all even-length words

In my quest to understand computability theory, I came across this question, and it made me think that I don't fully understand the theory. Is this language decidable? Is it semi-decidable, co-semi-...
maya cohen's user avatar
1 vote
1 answer
59 views

Is $L = \{ \langle G,k\rangle \mid G $ has a simple cycle at length $k \}$ in P or in NP

$ L = \{ <G,k> |\ G \ has \ a \ simple \ cycle \ at \ length \ k \} $ I think this language is in NP but my friend thinks this language is in P. NP proof: if a graph has a simple cycle of a ...
maya cohen's user avatar
0 votes
1 answer
125 views

Mapping Reduction from HALT?

I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would ...
Diode's user avatar
  • 1
0 votes
1 answer
55 views

Are there some additions that a Turing machine cannot perform

The total number of Turing machines is the cardinality of the set of natural numbers. Now consider the following functions f1(x) = x + 1 f2(x) = x + 2 f3(x) = x + 3 and so on Since the total number ...
zokina's user avatar
  • 1
-4 votes
2 answers
90 views

PSPACE and Polynomial reduction

thanks for your help. This is my first question, so I am very sorry for the bad presentation of the question. I am studying computer science and this is the question I have been asked for the course ...
Lior klunover's user avatar
1 vote
0 answers
52 views

Is it known, whether the complement of NP-hard problems is necessarily again NP-hard?

Neither could I find any counterexamples, nor could I show that if indeed the complement of NP-hard problems was NP-hard, one could deduce some unknown results from it, which would imply that it is ...
LostBetweenTheLines's user avatar
1 vote
1 answer
45 views

Is the Language of all encodings of Turing Machine that at least halts on one input and outputs 0 semi-decidable?

I need to prove if the following Language is or is not semi-decidable. A := {w ∈ {0,1}^* | there exists an input x on which M_w produces the output 0} Where A is the language of all the encoding w ∈ {...
sergio ospina's user avatar
2 votes
1 answer
75 views

Reducing from the complement of the Halting Problem

Consider the halting problem $HALT_{TM} = \{\langle M, w\rangle: M \text{ is a TM that halts on input } w\}$, and some undecidable Language $L$ of the form $L = \{\langle M\rangle: M \text{ does a ...
cassnx's user avatar
  • 21
3 votes
0 answers
47 views

Decide whether a given string appears in the binary expansion of π [duplicate]

Is it known whether the language $L_π = \{w\in\{0,1\}^* : w\text{ appears in the binary expansion of }π\}$ is decidable? $L_π$ is easily recognizable (a.k.a. computably enumerable). A trivially ...
Bruno's user avatar
  • 336
3 votes
1 answer
373 views

Turing degree of some functions related to Rice's theorem

Rice's theorem asserts that as soon as $f$ is non-trivial (i.e., non-constant), and extensional (i.e., $f(M) = f(M')$ as soon as $M$ and $M'$ are codes of Turing machines with the same behavior, in ...
Jean Abou Samra's user avatar
3 votes
1 answer
125 views

Can I reduce a non semi decidable and undecidable language to a semi decidable and undecidable langauge? many-one reduction

Let's say a Language L is NON-semi decidable and undecidable. Let's also take the Halting problem H, which is a semi decidable and undecidable language. Is it possible to reduce L to H in a many-one ...
sergio ospina's user avatar
3 votes
1 answer
90 views

Useful algorithm not primitive recursive

The Ackermann function is the textbook example of a function which is total recursive but not primitive recursive. If we want to implement it in some programming language we will need to use a priori ...
Weier's user avatar
  • 231
0 votes
1 answer
73 views

Is the function $f: \mathbb{N} \rightarrow \mathbb{N}$ where $f(n) = 2^n$ computable in polynomial time using TM?

Assuming that the input $n$ is given as a decimal number. I was asked to prove whether the function $f: \mathbb{N} \rightarrow \mathbb{N}$ where $f(n) = 2^n$ is computable in polynomial time using TM ...
Yarin's user avatar
  • 275
1 vote
1 answer
120 views

Understanding Whether a Set is an Index Set

I'm struggling to grasp the intuition behind the concept of an index set. By definition, a set $I$ is called an index set if $\forall i,j: i \in I$, $\phi_i = \phi_j \implies j \in I$. This implies ...
PPP Legend's user avatar
0 votes
4 answers
78 views

If a problem A in NP is reducible in polyomial time to a problem B, can one say that B must also be in NP?

In other words: If $A \leq_{p} B$ and $A \in NP \Rightarrow B \in NP$ From my deduction this is has to be false. We know that if $A$ is NP Complete $\Rightarrow A$ NP-Hard and $A \in NP$, then $B$ is ...
me5ng3's user avatar
  • 5
0 votes
2 answers
77 views

If all problems in NP are polynomially reducible to SAT (Cook & Levin) can one also assume that all to SAT polynomially reducible problems are in NP?

From Cook & Levin's theorem we know that all Problems in NP are polynomially reducible to SAT: $ \forall_{L\in NP}: L \leq_{p}SAT$. Is the opposite also true? That is if we know that a language L ...
me5ng3's user avatar
  • 5
1 vote
1 answer
170 views

Is the problem of "finding the output given the algorithm halts" not computable?

For simplicity, let's assume all Turing machines print 0 or 1 on the tape. Consider an algorithm $A$, which, given any Turing machine $T$ as the input, outputs $x\in \{0,1\}$, satisfying the condition ...
Ma Joad's user avatar
  • 119
6 votes
1 answer
281 views

Are any "standard" complexity classes uncountably infinite?

(This is a somewhat fuzzy question.) I believe that most of the "standard" complexity classes that one comes across in complexity theory are countably infinite, because they are defined in ...
tparker's user avatar
  • 1,116
2 votes
1 answer
53 views

Upper bound on output of halting transducer

My question is simply this: is it possible to upper bound the output length of a halting turing machine? I.e., is there a function $f$ such that for every halting machine $M$ and every input $x$ we ...
Edwin Agnew's user avatar
2 votes
2 answers
448 views

Help understanding the proof that $L = \{ \langle M \rangle \mid M \text{ is a TM that accepts the input string } 101\}$ is undecidable

I understand of the existence of Rice's Theorem, however, I want to understand better how this reduction is formed. My professor gives the answer as follows: "By contradiction, assume that $L$ is ...
codeing_monkey's user avatar
0 votes
1 answer
135 views

Why can't humans translate all of their abilities into an algorithm? Will that hold true in the future?

I know that an algorithm can't decide whether another algorithm halts on an input or not (a Turing machine can't decide whether another Turing machine will halt on an input). But I, as an human, can: ...
lilsm's user avatar
  • 3
0 votes
0 answers
21 views

Does valid value in L2 have to be gotten from L1 when we have a Many-One Reduction from L1 to L2

If I am doing a many-one reduction from L1 to L2, since it is described as a total function, does that mean that every possible encoding in L2 should have been achieved from L1 or is it possible that ...
River Uzoma's user avatar
0 votes
1 answer
36 views

Can an unreocognizable language be Turing-reducible to a recognizable language?

Suppose $L_1\preccurlyeq_T L_2$, and $L_1$ is unrecognizable, can $L_2$ be recognizable? With decidability, if $L_1$ is undecidable, then $L_2$ is undecidable, because $L_1$ is the “easier” question. ...
Arthur's user avatar
  • 3
1 vote
1 answer
105 views

If the Navier-Stokes equations problem is a computable problem, for example a set/language called "L", what are the elements of L?

First, can the Navier-Stokes problem be a formal computable one? like a P problem? Then, how to define the corresponding language? Would it only be the set of equations, or something else? Then, could ...
someone's user avatar
  • 11

1
2 3 4 5
…
42