# Questions tagged [computability]

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

2,018 questions
Filter by
Sorted by
Tagged with
17 views

### Turring Machine Equivalence Proof [closed]

Turing Machine where instead of having a set of final states F it has: A designated final state qaccept which exists in Q set of states. Upon being in this state, it halts, and accepts the input. A ...
26 views

### Which of the following statements about computable functions is true? [closed]

Assume that $f: \mathbb{N} \to \mathbb{N}$ is total and $g: \mathbb{N} \to \mathbb{N}$ is primitive recursive and $h: \mathbb{N} \to \mathbb{N}$ is Turing computable. Which of the following statements ...
19 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 ...
28 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. ...
32 views

### Is it possible to compute the differentiation of any differentiable function on an interval?

It seems not because of the existence of irrational numbers in any interval, irrational numbers that have an infinite number of decimal digits that a computer is not able to manage?
1 vote
52 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 ...
1 vote
35 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 ...
32 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 ...
39 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 ...
1 vote
33 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?
109 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 ...
89 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 ...
1 vote
42 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 ...
95 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'...
1 vote
20 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 ...
78 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 ...
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, ...
55 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 ...
92 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 ...
62 views

### Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof

all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct? TLDR: Halting problem is undecidable because it leads to infinite recursion and never ...
43 views

### is Reduction from RE to coRE possible?

I'm trying to figure out if it something that I can say for every 2 languages: is Reduction from RE\R to coRE\R always not possible, and why? (some thoughts about it: this reduction might be possible ...
448 views

### TMs can decide whether or not a string is a Palindrome, yet, the language called PALINDROMES is undecidable - why?

I came across this language, where M denotes a Turing Machine: PALINDROMES $:= \{M \mid M \text{ accepts strings which are palindromes}\}.$ It is proven to undecidable. And, I know one can construct a ...
68 views

61 views

### What is lambda caculus's "fix point combinators" corresponding to Turing Machine?

The lambda caculus equals to Turing Machine,so What is lambda caculus's "fix point combinators" corresponding to Turing Machine? according to the paper <Primitive Rec, Ackerman's Function,...
1 vote