Stack Exchange Network

Stack Exchange network consists of 175 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

2
votes
1answer
14 views

checking whether a language is turing recognizable

After reading about it in the textbook and in the web, i was wondering about the "turing recognizable" concept. so for instance, if i take a simple language like:"L = {< M > | M ACCEPTS < M >}",...
2
votes
1answer
29 views

Constructing a reduction between two languages about pairs of Turing machines

I'm curious about a potential relation between the following two languages. $L_1 := \{\langle M_1, M_2 \rangle : L(M_1) \cap L(M_2) \ne \emptyset \}$. $L_2 := \{\langle M_1, M_2 \rangle : L(M_1) \...
2
votes
0answers
52 views

Is it a bad idea to require a correctness proof as part of a computable real number?

At 30:42 of Norman Wildberger's Difficulties with real numbers as infinite decimals (II) lecture, he raises the question whether "certificates of boundedness" (of the runtime of the algorithm to ...
1
vote
1answer
49 views

Are there decision problems outside of NP?

Consider any problem in NP-hard, then it has a polynomial reduction from a problem in NP in polynomial time. Though, it isn't clear by this definition whether there are decision problems in NP-hard ...
0
votes
0answers
24 views

Analyzing the encoding of a DFA by a deterministic Turing machine [duplicate]

Define $L=\{\langle D,R \rangle \mid D$ is a DFA, $R$ is a regular expression, $L(D)=L(R) \}$ Is $L$ decidable? Is $L$ decidable in polynomial time ($L \in P$)? I am trying to ask: can a TM analyze ...
0
votes
1answer
37 views

How to judge the searching precision of Particle Swarm Optimization?

As the title mentioned, how can I judge the searching precision of PSO? Is this depending on the velocity of the particles? I would like to give an example to clarify my question: For a 2-D searching, ...
0
votes
1answer
61 views

Decide if a string is in a language without simulating the automata accepting the languge

Is it possible for a Turing machine with input of a DFA that accepts a finite language and a string to decide whether the string is in the language without "fully simulating" the DFA on the string? ...
1
vote
0answers
33 views

Is McCarthy Formalism first ever formalism for defining functions recursively in computer science?

McCarthy formalism is a formalism for defining functions recursively, first introduced in classic paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (1960). ...
2
votes
0answers
21 views

Is there a formal way of defining a Zeno Machine?

The idea of a Zeno machine is pretty interesting to me, but I can't seem to find a formal definition for how a Zeno machine would work. I can find a couple of definitions around but they are all ...
1
vote
1answer
37 views

Is this language is Context-free language or not?

Is anybody can help me please to determine is this language is Context-free language or not? L={wvw | w,v∈{a,b,c}+} for example: part of the language: acbac, abcab, bbcbb not part of the language:...
1
vote
1answer
55 views

Is it decidable whether a Turing machine M will reach state q on input s?

Given a turing machine $M$, one of its states $q$ and an input word $w$, will $M$ ever reach $q$ on $w$? As we are not given anything about the word length, I assume that we have a finite length word....
3
votes
2answers
46 views

Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time

In this proof of the Space Hierarchy Theorem the following langugae is defined $$ L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\...
1
vote
1answer
45 views

A language which is neither r.e. nor co-r.e

First, consider $$L_\exists=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts some input}\}$$ is RE. I tried to construct a Turing machine: ...
38
votes
9answers
7k views

Is C actually Turing-complete?

I was trying to explain to someone that C is Turing-complete, and realized that I don't actually know if it is, indeed, technically Turing-complete. (C as in the abstract semantics, not as in an ...
2
votes
1answer
42 views

Prove the languages |L<M>| = 2 and |L<M>| $\not=$ 2 to be non-Turing recognizable or non-recursively enumerable

I am trying to prove the non-recursively enumerable property of two languages. $L_2 = \{\langle M \rangle: |L\langle M \rangle| = 2\}$ and $L_{\not=2} = \{\langle M \rangle: |L\langle M \rangle| \not=...
1
vote
1answer
24 views

Reading elements of a countable set with Turing machine

I have a basic question about the behavior of a potential Turing machine. Suppose that $S$ is a countable set of binary strings, so that we can enumerate $S$ as $(s_i)_{n\in \mathbb{N}}$. Suppose ...
4
votes
2answers
352 views

Definition of an immune set

I'm reading a theorem about existence of a simple set. The definition of an immune set can be found from here A set ${\displaystyle I\subseteq \mathbb {N} }$ is called immune if ${\displaystyle I}$ ...
0
votes
0answers
33 views

Can we see all of mathematics as an attempt to simplify computations?

This is a rather strong claim, and therefore likely to be incorrect, but hear me out. Firstly, when I talk of “computations”, I mean this in a broader sense than normally used, because I am including ...
3
votes
2answers
184 views

Is the set of language decidable by some Turing machine computing in some given computable time bound decidable

Let $T : \mathbb N \to \mathbb N$ be some computable function. Then by $\mathcal C_T$ we denote the class of languages decidable by a deterministic Turing machine in at most $T(|w|)$ steps for an ...
6
votes
1answer
1k views

Why is deciding regularity of a context-free language undecidable?

As I have studied, deciding regularity of context-free languages is undecidable. However, we can test for regularity using the Myhill–Nerode theorem which provides a necessary and sufficient ...
16
votes
1answer
2k views

Is it decidable whether a pushdown automaton recognizes a given regular language?

The problem whether two pushdown automaton recognize the same language is undecidable. The problem whether a pushdown automaton recognizes the empty language is decidable, hence it is also decidable ...
4
votes
1answer
274 views

What's after EXPSPACE?

As far as I'm aware, EXPSPACE is the most inclusive computational complexity class. I was wondering if/how people conceptualize supersets of EXPSPACE. Thinking about this question, I came up with a ...
4
votes
1answer
290 views

Given a total recursive function, can you always compute its fixed-point?

We know from Kleene's recursion theorem that if $f$ is total recursive, there must be an integer $n$ for which $\varphi_n=\varphi_{f(n)}$. My question is: for every $f$ total recursive, is there a ...
2
votes
1answer
40 views

How do you prove that $A = \{ x \in \mathbb{N} | W_{x} = [0..x]\}$ is a productive set through functional reduction?

As the title states, how do you prove that $A$ is productive? With $W_{x}$ I mean the set of points in which the turing machine with index $x$ halts. The standard approach that I follow is functional ...
7
votes
6answers
965 views

How is Turing's Solution to the Halting Problem Not Simply “Failure By Design”?

I'm having a hard time viewing Turing's solution to the Halting Problem as a logician, rather than as an engineer. Here is my understanding of the Halting Problem: Let $M$ be the set of all ...
1
vote
2answers
57 views

Would any continuous model of the universe have/be based on hypercomputational laws?

I've read that when Turing-Church thesis is applied to the universe and physics, one of the three interpretations that we can use and is defended by some important physicists is that: "The universe ...
0
votes
2answers
66 views

Proving a language as undecidable without using reductions

Let's say our Σ is 0 and 1. I want to disprove the following: There can be Turing Machines that accept only 1's, i.e. 1, 11, 111, etc. Therefore, all languages that have strings of 1's are ...
1
vote
1answer
45 views

How does one use the Nerode-Myhill theorem to prove that a language is regular?

Showing that a language is not regular is straight-forward, because all one needs to do is find an infinite set of inputs which has an injective mapping to the set of equivalence classes which compose ...
36
votes
1answer
25k views

Is a push-down automaton with two stacks equivalent to a turing machine?

In this answer it is mentioned A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is ...
1
vote
1answer
31 views

Recognizer to check if the language of a Turing machine contains a finite subset

Let $B = \{ 123 \}$. Note that $B$ is finite. Let $L = \left \{ \left\langle M \right\rangle | M \text{ is a Turing machine such that } B \subseteq L(M) \right\}$. Is it sufficient to show that $...
2
votes
2answers
65 views

Is determining if a Turing machine runs in constant time decidable if one assumes it halts?

As the title states, is determining if a Turing machine runs in constant time decidable if one assumes it halts? The decision problem, more formally: Given a Turing machine $M$ where it is assumed ...
2
votes
1answer
49 views

Can generalized Turing machines compute all reals?

Super-recursive algorithms are theoretical super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines. In this entry it ...
6
votes
1answer
40 views

Proving a set is at a certain level of the arithmetical hierarchy

I'm interested in methods for proving a set is at some level $\Sigma^0_n$ (or $\Pi^0_n$) in the arithmetical hierarchy, and in particular, proving it is at the level with the smallest $n$ possible. I ...
0
votes
0answers
31 views

Church-Turing thesis and hypercomputation?

The Church-Turing is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being following an algorithm, ignoring resource ...
0
votes
1answer
107 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$?
7
votes
1answer
6k views

What is the difference between decidability and computability?

If they are different, what are the typical problems in each that do not fall on the other category? Or are the mutually exclusive or does one completely capture the other?
1
vote
1answer
43 views

Prove Halting on all Inputs is not in RE simulation

I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine ...
1
vote
1answer
44 views

Reduction between these two languages

I'm given $L_\cap=\{\langle M_1\rangle\#\langle M_2\rangle\mid L(M_1)\cap L(M_2)\neq\emptyset\}$ and $L_U=\{\langle M\rangle\#w|M \text{ accepts } w\}$. How can I reduce the former to the latter: $L_\...
2
votes
1answer
47 views

Can one get Turing-completeness without nontermination?

As I'm reading the movfuscator paper by Stephen Dolan, I encounter this claim: In order to have Turing-completeness, we must allow for nontermination. This seems like a reasonable statement. But I'...
0
votes
1answer
29 views

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

Let $L$ be recursively enumerable and $U$ be non-recursively-enumerable. Is it possible to reduce $U$ to $L$ recursively, $U\leq_R L$? Personally, I do not think this is possible. If we can reduce $U$ ...
1
vote
2answers
49 views

Pumping Lemma. Why is there a word w in L for infinite languages with n≤|w|≤2n

The following comment on an other question says that if we have an infinite language L that satisfies the pumping lemma for regular languages then we have a word with n≤|w|≤2n which is in L. (n is the ...
1
vote
2answers
43 views

Are all countable partial functions computable?

I know all computable partial functions are countable. Wondering if it is the the other way around as well.
3
votes
1answer
127 views

Mathematical Problem Solving

Will a study of the mathematical proof of a (data structure and algorithm based) problem, when posed as a proposition, highlight peculiar properties of the problem which may help in designing an ...
1
vote
5answers
1k views

Whether TM accepts epsilon?

L = {< M > $\mid$ L(M) is $\epsilon$ } Why is the above problem undecidable and not decidable? Can't we just check whether initial state is itself final state and say TM accepts epsilon if initial ...
1
vote
1answer
35 views

Rice's theorem applicable to the following language?

Let $L= \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle \} $ be a language where $\langle M \rangle$ is the Code of the TM $M$. $L$ is undecidable. I've heard that I can't use Rice's ...
2
votes
1answer
38 views

Is there a relation between the size of the domain/range of a function and its computability?

This was a question given in a course, without answer. The referenced literature (just a few books) do not cover it, unfortunately. I think there is no relation with the range as the range of the ...
3
votes
3answers
349 views

What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute

If I were to pose the question: "Given a program $P$ containing statement $X$, will $X$ be executed (given enough runs with all possible inputs)?" This strikes me of being a relative of the Halting ...
1
vote
1answer
39 views

REC and RE under intersection

Would the intersection of a recursive language and a recursively enumarable language be recursive or recurisvely enumbarable or neither? Assume $L_{3}$ is the intersection of some language $L_{1}$ $\...
2
votes
3answers
1k views

Halting problem without input?

I'm only a layman therefore only discuss stuff naïvely. I read some introductory articles about halting problems with a scenario that if there were such a decider accessible to us, we should be able ...
1
vote
2answers
61 views

Relation between semi decidable, undecidable and countable sets

I know that decidable problem: has both counting (bijection with $\mathbb N $) and membership algorithm (TM halts for both member and non member strings ) semidecidable problem: has counting ...