Questions tagged [computability]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
37 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
  • 111
-4 votes
0 answers
51 views

Proof that strong AI exists?

If turing machines are capable of simulating physics, then they should be able to simulate a human brain. Isn't that enough to prove the existence of strong AI?
JobHunter69's user avatar
3 votes
1 answer
583 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
319 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
1 vote
1 answer
53 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
  • 219
-2 votes
2 answers
67 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
-1 votes
0 answers
19 views

Recognizability of PFTM

I encountered this problem here: https://theory.stanford.edu/~trevisan/cs172/ps05.pdf Consider the language $$PFTM := \{\langle M \rangle : \text{$M$ is a Turing machine and $L(M)$ is prefix free} \}$$...
redrobinyum's user avatar
3 votes
1 answer
42 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
  • 353
4 votes
1 answer
695 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
69 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
58 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
34 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
75 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
37 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
78 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
53 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
86 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
50 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
41 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
63 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
355 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
102 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
80 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
61 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
92 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
74 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
71 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
169 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
273 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,096
2 votes
1 answer
52 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
172 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
125 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
87 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 vote
1 answer
46 views

Complexity of simulations in simulations

This video of a group, who simulated (a very simple version of) Minecraft inside Minecraft itself got me thinking about the performance of such setups. Another example to what I'm referring to, would ...
SmallestUncomputableNumber's user avatar
0 votes
1 answer
61 views

recursively enumerable and linear bounded automaton

I have a question about linear bounded automaton. Is it false that every recursively enumerable language is recognized by a LBA ? Because LBA has limited tape size so not all recursively enumerable ...
MathJunior's user avatar
0 votes
1 answer
44 views

Computability = Enumerating a sequence in the particular order?

In the paper "Computability by Probabilistic Machines" by K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro (in Claude E. Shannon: Collected Papers , IEEE, 1993, pp.742-771), a ...
Ma Joad's user avatar
  • 119
1 vote
1 answer
75 views

function is computable iff its graph is recursively enumerable?

How do I show that a (possibly partial) function is computable iff its graph is recursively enumerable?
empty-search's user avatar
3 votes
1 answer
118 views

For which values of $k$ is a $k$-state-bounded version of the halting problem decidable?

This is related to my previous question: Do proofs of $HALT$'s undecidability make it clear that it's practically relevant? I made a mistake of leaving something implicit when I asked it; namely that ...
CuriosityScream's user avatar
0 votes
1 answer
94 views

Do proofs of $HALT$'s undecidability make it clear that it's practically relevant?

The proof of $HALT$'s undecidability usually goes like this: we assume the existence of a halting decider and incorporate it into a machine $D$ that takes a TM as input, runs it on its own encoding ...
CuriosityScream's user avatar
1 vote
1 answer
45 views

How to formally show computational equivalence or universality using encodings?

I want to formally show that a computational system $\mathcal M$ is computationally universal by showing it is computationally equivalent to some already known universal system, i.e. some UTM. To show ...
Yannik Eik's user avatar
3 votes
1 answer
116 views

Expression with fastest growth in lambda-calculus

Well-known example of divergent expression in lambda calculus is big-Omega combinator, defined as (λf. f f)(λf. f f). Although big-Omega is divergent expression, it'...
Vladislav Ihost's user avatar
1 vote
0 answers
28 views

Is it possible for a Linear bounded automaton to be a recognizer but not a decider?

So we know that LBAs have a finite number of configurations, which makes the task of detecting loops much easier. My proposition is that if a given LBA is constructed to recognize a language, it also ...
Aland Ameer's user avatar
-3 votes
1 answer
88 views

Can a decider return "Undecidable" on the Halting Problem? [closed]

So, I know there is no general algorithm for the halting problem, but I was curious if a three output decider could at least give us "an" output {0 if doesn't halt, 1 if halts, U if ...
Daniel Stilman's user avatar
19 votes
2 answers
4k views

Why are computability problems always written in full caps?

Maybe this is an odd question. It has always bugged me that computability problems are written in all caps, and in such an "awkward" way. SAT, 3-SAT, COLORING, 3-COLORING, PARTITION, CLIQUE, ...
Julian W.'s user avatar
  • 191
-6 votes
1 answer
70 views

Is ChatGPT wrong about the definition of unrecognizable and undecidable languages?

I asked ChatGPT to give me the difference between unrecognizable and undecidable languages, and this what it gave me: Unrecognizable languages can be accepted by a Turing machine, but the machine may ...
Aland Ameer's user avatar
0 votes
3 answers
108 views

Why can't we use computation history to detect looping of a Turing machine on a given input?

First of all, obviously there is a flaw in my logic and I just want to know what it is. So here is my idea: Given a TM M and an input string ω, simulate M on ω on another TM S. For every change of ...
Aland Ameer's user avatar

1
2 3 4 5
41