Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computability]

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

0
votes
1answer
20 views

Why a TM with infinite states can decide the halting problem?

Assuming we have a model of TM with an infinite number of states. The domain and range of the transition function are also infinite. Given a description of a TM $M$ and a string $w$ how can we use the ...
-4
votes
0answers
14 views

#P=NP: All satisfying solutions are valid answers by programs for NP [on hold]

In fact, the implication looks like an equivalence too. All satisfying solutions to a boolean formula are valid answers by programs for NP is equivalent to saying the class #P equals the class NP. ...
0
votes
0answers
29 views

Decidablity of time complexity

Let $t:\mathbb{N}\rightarrow\mathbb{N}$ be a time constructible function with $t(n)\geq n + 100$. Show that there is no TM $T$ that given the gödel number of another TM $M$, decides wether or not M is ...
-1
votes
0answers
56 views

Undecidability of the “Single-Halting Problem”

I have to show for a turing machine S that is taking another TM T and a word x as input and only halt for one specific T and x, that it is not decidable. The idea is now to reduce it to the halting ...
4
votes
1answer
376 views

Busy Beaver problem - Proof by contradiction

I am trying to understand a proof regarding the Busy Beaver problem that uses a proof by contradiction approach to show $\sum(n)$ is Turing-uncomputable: Find $\sum(n) = max \{\sum(M) | M \in M(n) \...
5
votes
1answer
726 views

What is the complement of a language?

If given any language L, how do I find the complement of said language? I lack the basic understanding required to determine if a language is co-recognizable. I understand that a language, $L$, is co-...
2
votes
0answers
30 views

Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
1
vote
2answers
46 views

Recognizer for decidable language and words it doesn't halt on

Suppose we have a decidable language B (there exists some TM that decides it). Suppose we have another TM M which only ...
1
vote
2answers
91 views

Are the capabilities of programming languages the same?

Is the capability of every programming language the same since it is eventually translated into machine code. Python, Java etc. are all together instructions the CPU is going to process. So, you could ...
9
votes
2answers
2k views

Is it possible that the halting problem is solvable for all input except the machine's code?

This question occurred to me about the halting problem and I couldn't find a good answer online, wondering if someone can help. Is it possible that the halting problem is decidable for any TM on any ...
0
votes
1answer
22 views

Is the set of surjective recursive functions in RE/coRE?

Let L be a set of recursive funtions with $L = \{i\in \mathbb{N}|f_i\space is\space surjective\}$ where $i$ is a gödel number of f.Is $L\in RE,\space coRE$? I can't think of a way to show either of ...
0
votes
0answers
21 views

How strong is a FSM with long enough(but not infinite) tape?

Like turing machine, but your tape is finite. To make a program valid it should have a limit result when the length of tape tends to infinity. Whether the tape has two ends or is cyclic doesn't ...
0
votes
1answer
91 views

Prove that there exists a machine which decides an infinite subset of halting problem

We already know that $H:=\{\langle M,w\rangle | M$ halts on $w\}$ is undecidable, then how can there possibly be a machine that decides any infinite subset of $H$?
23
votes
4answers
10k views

Proof of the undecidability of the Halting Problem

I'm having trouble understanding the proof of the undecidability of the Halting Problem. If $H(a,b)$ returns whether or not the program $a$ halts on input $b$, why do we have to pass the code of $P$ ...
4
votes
1answer
53 views

Is Rice-Shapiro theorem bidirectional?

Rice-Shapiro theorem states that version A Let $\Gamma$ be a set of computably enumerable sets, and $I = \{e : W_e \in \Gamma\}$ its index set in some admissible enumeration of c.e sets. If $I$...
0
votes
3answers
111 views

Is a Turing machine too strong of a model to model physical computation?

I've heard many times people debate the possibility of a real world computation that is impossible for a Turing machine, especially in the context of a human mind. Implying that the Church-Turing ...
0
votes
0answers
41 views

Mathematical resource material accompanying TAPL

I'm currently reading Types and Programming Languages by Benjamin C. Pierce and just arrived at chapter 21 Metatheory of Recursive Types. Prior to this chapter I found the book challenging but ...
1
vote
1answer
24 views

Can the complement of an unrecognizable language be a recognizable language?

I know that complement of a language that is recursively enumerable, but not recursive, is definitely not recursively enumerable (or unrecognizable). So my question is what can be said about the ...
2
votes
1answer
37 views

Decidability of factoring algebraic equations

Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution: $$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$ And some arbitrary factorization constraints, say:...
1
vote
1answer
31 views

How to prove that a problem is undecidable by using the Halting problem?

I cannot understand how to reduce the halting problem to a property to show that is undecidable. For example, I have this property of a Turing Machine and I have to prove if it's recursive or not: "...
3
votes
1answer
194 views

Is the system of measuring length in the US Turing complete?

The author here writes: Little known fact, the system of measuring length in the US is Turing complete My question is: Is the system of measuring length in the US Turing complete?
2
votes
2answers
66 views

Is this system Turing complete?

I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries. I came up with the ...
3
votes
1answer
105 views

Complexity of the language of all TMs $M$ such that $L(M)$ is decidable

Let $$R = \{\langle M \rangle \mid L(M) \text{ is decidable}\}.$$ Is $R$ recursively enumerable or co-recursively enumerable?
1
vote
3answers
60 views

Proof Idea: There are irrational numbers whose decimal expansion cannot be computed

The online lecture I am watching stated a proof idea: The set of all possible programs is countably infinite, yet the set of irrational numbers is uncountably infinite. I don't think this is ...
0
votes
1answer
52 views

Halting problem with extra input

Can there be a function HALT(f, y) so that: There are some x such that f(x) halts iff there ...
0
votes
1answer
93 views

Can a PDA guess more than once? L = {aⁿ bⁱ aⁿ | i,n > 0 }

PDA = Pushdown Automata Let's assume I have this language: $L = \{a^nb^ma^n | m,n \ge 1\}$ Would the first approach with one node be enough - in that case it guess twice the $\lambda$. In the ...
1
vote
1answer
24 views

Is a set $B = \{y, \exists x \in A, f(x)=y\}$ recursive if A is a recursive set and f is a $N->N$ total computable function?

Obviously, B would be recursive if for every TCF f, there was an inverse fuction that would return all possible values, as we could just take these and then check if any of them is in A. However I ...
1
vote
1answer
29 views

Are physical laws uncomputable in any type of computation (according to this article)?

It seems that this article (https://arxiv.org/pdf/1312.4456.pdf) proposes that laws of physics are uncomputable (i.e., they could not be reproduced on a computer), but I'm not sure about it. In some ...
4
votes
3answers
386 views

Decidability of the TM's computing a non-empty subset of total functions

I have this HW problem: Let $F$ be the set of computable total functions, and let $\emptyset\subsetneq S\subseteq F$. Denote $$L_S=\{ \langle M \rangle | M \text{ is a TM that computes a function ...
0
votes
0answers
14 views

Is ${M :|L(M)| \leq 330}$ Recursively enumerable? [duplicate]

M is a Turing machine description, L(M) is the language recognized by M and |L(M)| is the size of this language.
2
votes
1answer
82 views

Which one of these two sets is computably enumerable?

M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language. {M : |L(M)| <= 330} {M : |L(M)| >= 330} I don't quite understand what this question is asking. ...
1
vote
1answer
34 views

Reduce ATM to REGULAR_TM

Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$. Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\...
0
votes
1answer
36 views

Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference

Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A). I know that ...
4
votes
1answer
132 views

Language that fulfills pumping lemma but is not in RE

I am supposed to find a language $$L\subseteq \Sigma ^*, \Sigma \subseteq \mathbb{N}$$ that fullfills the pumping lemma and is not in RE and not in coRE. I've never constructed a language with a given ...
0
votes
0answers
27 views

Witnessing for partial recursive functions

For all $f\colon \mathbb{N}^2 \rightarrow \mathbb{N}$ partial recursive there exists partial recursive $g\colon \mathbb{N} \rightarrow \mathbb{N}$ such that a) $x \in \operatorname{Dom}(g) \...
0
votes
1answer
29 views

Are non-regular languages decidable?

Given a language L, I've shown that L is not regular. Can I conclude that it is not decidable or are there non-regular languages that are decidable?
2
votes
2answers
34 views

Quotient in LOOP program [closed]

I want to construct a LOOP-computable program for the integer division (quotient): x = a DIV b The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP_(programming_language) I ...
4
votes
2answers
86 views

Converse of halting problem

It is well known that if some computing apparatus is Turing-complete, then the halting problem is undecidable for that computing apparatus. However, is it true that if the halting problem is ...
2
votes
0answers
56 views

What is the relationship between “model of computation” and “algorithm”?

Traditionally, the usual definition you find for model of computation is "an abstract description of how an output is computed given an input" (Wikipedia and my TCS course are my sources, but the ...
6
votes
2answers
1k views

Relation between Undecidable problems and NP-Hard

I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly. And then, I realized that it is not certain where undecidable problems should be placed. ...
58
votes
10answers
9k views

Human computing power: Can humans decide the halting problem on Turing Machines?

We know the halting problem (on Turing Machines) is undecidable for Turing Machines. Is there some research into how well the human mind can deal with this problem, possibly aided by Turing Machines ...
1
vote
1answer
58 views

Prove $L = \{M \mid L(M)\text{ is infinite}\}$ is not Turing-recognizable

I'm supposed to prove this through mapping reducibility. I think I'm supposed to show that $A_{\mathrm{TM}} \le_\mathrm{m}\overline{L}$, which means that $\overline{A_{\mathrm{TM}}}\le_\mathrm{m} L$ ...
2
votes
2answers
46 views

Can a RE language be reduced to a non-RE language?

In our lecture notes about many-one reduction we showed that the following statements hold: $$ L, L' \subseteq \mathbb{N}\space and \space L\leq L'$$ $$(I)\space L' \in RE \implies L\in RE$$ $$(II)\...
0
votes
0answers
17 views

Whether language of all turing machines is decidable or undecidable or semi-decidable?

I recently came across this language: $L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$ It was asked in the question to find out whether language L is decidable or undecidable. ...
1
vote
1answer
44 views

Give a Search Problem in co-NP

Ex.1. Give a Search Problem whose deciding Problem is in co-NP. Assuming 3SAT is in NP then asking wether a given Boolean formula has a Solution is a search problem in NP right? Then would asking ...
1
vote
1answer
101 views

Turing Reduction vs Karp Reduction [closed]

When do you use Turing- and when Karp Reduction? What are the advantages and disadvantages? I've read about Karp Reduction mainly used in the Context of reducing a Language: e.g. L1 $≤_p$ L2
1
vote
0answers
22 views

Can a CFG generate an accepting configuration? - or is there a turing-recognizable CFG language that is not decidable

I could not think of a way to concisely write down my question clearly, but I'd like to ask, from Sipser's book, $ALLCFG$ is an undecidable language (where $ALLCFG$ means that $G$ is a $CFG$ that ...
1
vote
1answer
64 views

Trying to prove semidecidability of an undecidable language

I have been having a hard time understanding whether the set $S = \{ M \mid |L(M)| = 5 \}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, ...
-1
votes
0answers
17 views

Understanding the computational power of neural networks

It is known that a recurrent neural network with rational weights is computationally equivalent to a Turing Machine (a proof can be found in this paper). I don't understand how is it possible, it ...
1
vote
0answers
39 views

Power of Turing machines that are not allowed to overwrite the input string [duplicate]

The question asks what kind of languages (regular, context free) can a Turing machine accept if you are not allowed to overwrite the input string. The initial configuration of the machine is start ...