Questions tagged [computability]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
bruh's user avatar
  • 1
0 votes
0 answers
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 ...
Ski Mask's user avatar
  • 463
0 votes
0 answers
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 ...
River Uzoma's user avatar
0 votes
1 answer
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. ...
Arthur's user avatar
  • 3
-1 votes
0 answers
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?
someone's user avatar
1 vote
1 answer
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 ...
someone's user avatar
1 vote
1 answer
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 ...
SmallestUncomputableNumber's user avatar
0 votes
0 answers
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 ...
MathJunior's user avatar
0 votes
1 answer
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 ...
Ma Joad's user avatar
  • 101
1 vote
1 answer
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?
empty-search's user avatar
3 votes
1 answer
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 ...
CuriosityScream's user avatar
0 votes
1 answer
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 ...
CuriosityScream's user avatar
1 vote
1 answer
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 ...
Yannik Eik's user avatar
3 votes
1 answer
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'...
Vladislav Ihost's user avatar
1 vote
0 answers
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 ...
Aland Ameer's user avatar
-3 votes
1 answer
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 ...
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, ...
Jul Wac's user avatar
  • 191
-6 votes
1 answer
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 ...
Aland Ameer's user avatar
0 votes
3 answers
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 ...
Aland Ameer's user avatar
0 votes
2 answers
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 ...
boinka's user avatar
  • 1
0 votes
1 answer
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 ...
user1701057's user avatar
0 votes
1 answer
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 ...
HaferFlockenPengu's user avatar
-1 votes
2 answers
68 views

Finding asymptotically tight upper bound of a recursion relation

Find an asymptotic tight upper bound for the following recursion relation: $$T(n)=5T(\frac{n}{5})+\log^2(n)$$ I tried to solve it by applying iteration: $$T(n)=5T(\frac{n}{5})+\log^2(n)=5(5T(\frac{n}{...
GBA's user avatar
  • 99
0 votes
0 answers
59 views

Has a Multitape Machine like this been Studied?

Sometimes as a hobby I like to think about different possible "fundamental" abstract computing frameworks, akin for instance to Turing Machines and Lambda Calculus. In particular, I've been ...
user1609012's user avatar
-1 votes
1 answer
44 views

Need help with a proof: L is recursively enumerable if and only if L is Turing recognizable

I am unable to understand this proof L is recursively enumerable if and only if L is Turing recognizable If anyone can prove this, that would be great help
Henry's user avatar
  • 1
0 votes
0 answers
106 views

Turing machine for unary subtraction $m-n$. If $m<n$, the machine writes "$!$" $|m-n|$ times

I am trying to program a Turing machine that performs unary subtraction, $m-n$, but if $m<n$, the machine writes the $!$ symbol on the tape $|m-n|$ times. If $m=1$ and $n=3$, the machine would only ...
l0ner9's user avatar
  • 101
0 votes
0 answers
51 views

Is there a 4th barrier to computing?

I know there are three barriers of computation; the thermodynamic barrier, the light barrier and the quantum barrier. Let’s say we figure out how to send signals FTL, learn how to get rid of excess ...
Max's user avatar
  • 1
0 votes
1 answer
43 views

Is this function computable?

Given a function like: f(x) = x=y then 1 else 0 The number y is a natural number, other than that is unknown I had two approaches in mind: The function is computable since an algorithm exists, that ...
HaferFlockenPengu's user avatar
-2 votes
1 answer
57 views

Programs with feedback?

Suppose we have a program like this: ...
Volpina's user avatar
  • 97
2 votes
1 answer
59 views

State Machines as Functors

I'm looking for more examples of the following model of state machines: in David Spivak's book on category theory, he gives in section 3.1.2.10 and in application 4.3.1.9, a description of a finite ...
NathanLiitt's user avatar
3 votes
2 answers
145 views

Does this esoteric representation of integers have decidable equality?

Consider the following datatypes in Haskell: data Foo = Halt | Iter Foo newtype BigInt = BigInt {nthBit :: Foo -> Bool} Foo ...
Dannyu NDos's user avatar
1 vote
0 answers
126 views

if L is in NP-Complete and its complement is also in NP does that mean L is in P? (meaning that P=NP)

$L^\complement$ = the complement of L is it true that if $L\in NPComplete $ and $L\leq_p L^\complement \rightarrow P=NP$ basically asking if the following statements are correct $if (L\in NPComplete ) ...
Skynet's user avatar
  • 53
0 votes
0 answers
17 views

which phenomena got used to calculate a function that was never computed by digital hardware

or wich phenomena have behavior that can be measured and described as a function between natural numbers but seem to be hard to simulate with digital hardware when the starting conditions are given.
user161149's user avatar
2 votes
1 answer
76 views

How to provide a reduction from 3SAT to domatic number problem

How to provide a reduction from 3SAT to domatic number problem. Domatic number problem: Given a graph $G = (V, E)$ and an integer $k$, can we partition $V $ into at least k disjoint sets of vertices, ...
Hughson's user avatar
  • 21
1 vote
1 answer
41 views

P NP R RE closures

I wrote the following table for all the closures in those classes. is anything there incorrect? also, would appreciate help with coNP and coRE closures. couldn't find much information about it online.
Skynet's user avatar
  • 53
1 vote
1 answer
155 views

is the class NP closed under set difference?

I know P is closed under all Boolean operations, but what about NP? is NP closed under set difference and symmetric difference? is this table accurate? Edit: updated table:
Skynet's user avatar
  • 53
0 votes
0 answers
23 views

Question regarding rice theorem

this is a question I got from a test that we had before Let there be X, a subgroup of languages above $\Sigma $ such that X isn't empty nor all of the langauges in $\Sigma $ we need to say if the ...
elay dadnon's user avatar
8 votes
1 answer
2k views

Are "computable problem" and "computable function" the same thing?

I'm confused by the use of the expressions "computable problem" and "computable function" in the context of computability theory. Are they refer to the same thing or are there ...
Sanyo Mn's user avatar
  • 183
-1 votes
1 answer
89 views

Understanding reductions and notation

I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
talon23's user avatar
2 votes
1 answer
104 views

Is the following binary quadratic integer programming NP-Hard?

I'am trying to prove the following binary quadratic integer programming problem NP hard. $$ \min \frac{\sum\limits_{i=1}^m(u_i-\bar u)^2}{m}\text{ , where }u=Q x,Q\in\mathbb{R}^{m\times n}\\ s.t. \...
OvinaSun's user avatar
0 votes
1 answer
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,...
wang kai's user avatar
  • 121
1 vote
1 answer
34 views

Concrete example of a set with a lower degree of unsolvability

Post's problem, posed in 1944 by Post, was to know if there is a recursively enumerable set, which, being undecidable, was not equivalent to the Halting problem under Turing reducibility. While I've ...
user6767509's user avatar
0 votes
0 answers
37 views

Is PrefixFreeNP=P?

I was given the following definition of a verifier: Verifier $V$ is called $PrefixFree$ if for every $x,y$ such that $V(x,y)=1$, then for every $y'$ (which is not an empty string, $y'\ne\epsilon$) $V(...
MiddleEasternPrince's user avatar
1 vote
0 answers
43 views

Seeking Intuitions about Recursion, Y Combinator and System F

So, as I understand things, System F (polymorphic lambda calculus) doesn't have the Y Combinator and isn't Turing Complete, but it is very expressive. This answer (https://cstheory.stackexchange.com/...
Noam Hudson's user avatar
4 votes
1 answer
69 views

Simple, intuitive example of non recursively enumerable languages

This question is a bit of a shot in the dark. I am asking here, though I am not convinced that such an example exists. I'd like a quick, highly intuitive example that I can throw out to my students ...
Ben I.'s user avatar
  • 1,682
1 vote
1 answer
42 views

What do people mean they say "set of all programs" in computability theory?

I am going through notes on Computability theory and Galosis Theory by Russel Miller. In it, many times the phrase "set of all programs" is used. Could someone give a formal definition of ...
tryst with freedom's user avatar
0 votes
0 answers
47 views

Undecidability of syntactic properties

Rice's theorem comments on the undesirability of non-trivial semantic properties, however there are syntactic properties that are undecidable as well, such as the "useless" states problem ...
Alan Whitteaker's user avatar
3 votes
2 answers
2k views

Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form

Here's what Wiki says: And here's what Mike Sipser says in his Introduction to Theory of Computation: The problem arises when you try to read the two definitions - Mike Sipser seems to be suggesting ...
Sbeve's user avatar
  • 51
0 votes
1 answer
49 views

Converting P = NP into an effective equivalence algorithm

If P = NP, then is it the case that there exists a total recursive function from the set of polynomial-time nondeterministic Turing machines to the set of polynomial-time deterministic Turing machines ...
A. P. Pille's user avatar
1 vote
3 answers
148 views

Halting problem unsolvability leads to a contradiction - where's the mistake?

You are all familiar with the halting problem so I won't repeat it. Suppose $H$ is a Turing machine which takes as input an encoding of another Turing machine $M$, then searches all possible proof ...
user253751's user avatar
  • 1,720

1
2 3 4 5
41