Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
-1
votes
1answer
39 views
Does solving all Halting problem instances 'in the limit' imply we solve an undecidable problem?
The recent Arxiv paper "Learning the undecidable from networked systems" attempts to construct a network of $N$ Turing machines$^1$ that can solve the Halting problem for any program of size $O(\log N)...
1
vote
1answer
37 views
Can the notation for polynomial reduction, A ≤p B be reversed in computability theory?
I don't know this is a proper question on this forum but I was reading about computability theory and I saw the reduction concept and its notation like this: $A \le_pB$. I just wanted to know is this ...
20
votes
4answers
3k views
What does Turing mean by this statement?
I encountered below statement by Alan M. Turing at here:
"The view that machines cannot give rise to surprises is due, I
believe, to a fallacy to which philosophers and mathematicians are
...
-2
votes
0answers
42 views
Turing Machine the undecidable language
Consider the undecidable language
$$\mathrm{ALLTM} = \{\langle M\rangle \mid M\text{ is a Turing machine with }L(M) = \Sigma^*\}.$$
Suppose you had an oracle for the halting problem (that is, you have ...
0
votes
0answers
14 views
Question regarding A/D Converters and calculating voltage [on hold]
You are comparing different A/D converters that will have 3.2 V and -3.2 V as their positive and negative reference voltages, respectively. Out of the following, __(List below)____ converter can ...
1
vote
1answer
47 views
Proving $L = \{\langle M, w, n \rangle$ : $M$ accepts $w$ within $n$ steps $\}$ is decidable
Show the following problem is decidable: Given $w\in \Sigma^{*}$, $n\in \mathbb{N}$, and a Turing machine $M$, does $M$ on $w$ halt within $n$ steps.
My Thoughts:
I am new to proving results like ...
0
votes
0answers
51 views
Can hypercomputation compute the impossible? [on hold]
There are things which are illogical/logically impossible (like saying that 2+2=4 and 2+2=5. Without changing anything in the axioms of mathematics or logic, this would be a contradiction and would be ...
2
votes
1answer
31 views
Construct a decidable set $B$ such that $B \neq A_w$ for any $w \in \Sigma^\star$
I've been stuck on this problem for a while. Any hints would be appreciated!
Let $A \subseteq \Sigma^\star$ be decidable. Given $w \in \Sigma^\star$, define $$A_w = \{x \in \Sigma^\star\:|\: \langle ...
0
votes
0answers
45 views
Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times
I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation").
Can i just use ...
0
votes
1answer
32 views
Finding a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$
I am trying to find a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$, but I can't seem to find one.
Definitions:
$$\begin{align*}
CF_{TM} &= \left\{ \langle M \rangle \mid \text{$M$ is a ...
1
vote
2answers
236 views
Is the language {<p,n> | p and n are natural numbers and there's no prime number in [p,p+n]} belongs to NP class?
I was wondering if the following language belongs to NP class and if its complimentary belongs to NP class:
\begin{align}
C=\left\{\langle p,n\rangle\mid\right.&\ \left. p \text{ and $n$ are ...
0
votes
1answer
19 views
Does $E_{TM}$ accpets the empty word $\varepsilon$?
Let $L = E_{TM} = \left\{ \left<M \right> | M \text{ is a TM and L(M)} = \emptyset \right\}$.
Does $L$ accepts the empty word $\varepsilon$?
In other words, is $$\varepsilon \in L$$
I'm ...
0
votes
0answers
24 views
Is the proof for the undecidability of $A_{TM}$ still valid if we change certain parts?
i have a question based on a question i saw exists on the site, but with wrong information in it and no answer there, so i am reposting it with valid information(cited wrong from the book).
on page ...
1
vote
1answer
29 views
Language decidable or not?
I have just began with my course of complexity and computability and I need your experience to help me progress !!
Something is not clear for me:
It is asked to determine if L1 is decidable or not, ...
2
votes
2answers
90 views
Can a TM recognize whether another TM recognizes a non-empty language?
Let $$L_1 = \{\langle M\rangle\mid M \text{ is a Turing Machine and }L(M)\ne\emptyset\}.$$
Is $L_1$ recognizable? If so, can you give me a pseudo-algorithm?
My attempt:
I wanted to study ...
0
votes
1answer
18 views
Enumerators and recognizers
I got confused by this a bit... the words of any recursively enumerable language $\mathcal{L}_{RE}$ can be enumerated by an enumerator $E$, i.e. there is an effective procedure (using lexicographic ...
1
vote
2answers
41 views
Rice's Theorem - usage on $DFA$ or $LBA$
I have read about Rice's Theorem on Sipser's book, and I think I understand it quite well. I understand that it can be used to show that a language is not decidable.
However I am not sure about one ...
2
votes
3answers
78 views
Are $CF_{TM}$, $\space $ $\overline{CF_{TM}}$ Turing-recognizable?
I have searched the site well through, and also using Google and notes and couldn't find an answer to a question I am wondering about.
Given:
$$CF_{TM} =\{ \langle M \rangle \mid \text{$M$ is a TM ...
1
vote
1answer
52 views
is it possible to reduce $HALT_{TM}$ to $E_{TM}$?
I am wondering, if it is even possible: is it possible to reduce $HALT_{\text{TM}}$ to $E_{\text{TM}}$?
$HALT_{\text{TM}}=\{\langle M,w\rangle\mid M\text{ is a }TM\text{ and }M\text{ halts on input }...
0
votes
0answers
52 views
Proving language K is undecidable using the diagonalization method
I have a problem proving the following properties of given language K:
$K = \{< M > | M\ accepts < M >\}$
I am trying to prove that language K is Turing-recognizable but undecidable ...
3
votes
2answers
72 views
One counter automaton as a function
We can associate a one counter finite automaton with a function $f:\Sigma^* \to \mathbb{N} \times \{0,1\}$, where $f(x)=(n,b)$ describes the state where the automaton terminates when fed an input word ...
0
votes
1answer
78 views
Finding two languages satisfying conditions
Let $$E_{TM} = \left \{ \langle M\rangle \mid L(M) = \emptyset \right\}$$
Prove that there are two languages $L_1, L_2$ such that
$L_1, L_2 $ are infinite.
$L_1 \cup L_2 = E_{TM}$
$...
2
votes
1answer
59 views
What doest it mean: “computer is an intelligence amplifier”?
There is one example in Kolmogorov complexity books and related articles:
Consider we have a monkey at a typewriter and a monkey at a computer keyboard.
If the monkey types at random on a typewriter,...
1
vote
1answer
28 views
Do all DFA's containing an “accepting path containing a cycle” accept infinite languages?
So I've seen this claim being made on different questions:
Do self-loops in DFA cause infinite languages?
I'd like to find formal proof for this.
I think I should also note that an "accepting path ...
0
votes
0answers
31 views
Effects of changes in the proof that $A_{\text{TM}}$ is undecidable
In the proof that $A_{\text{TM}}$ undecidable we use the following machine:
$D =$ On input $\langle M, w \rangle$:
Simulate $M$ on input $w$.
If $M$ ever enters its accept state, accept. ...
-2
votes
0answers
46 views
Is the set of NFAs that recognize a finite language decidable? [duplicate]
Question: Let $L$ be the set of NFAs that recognize a finite language, is $L$ decidable?
1
vote
2answers
74 views
What are the other language models of computation similar to lambda calculus?
I hope this question makes sense, but I was wondering if there are other models of computation similar to lambda calculus that you can use to build up axiomatic mathematical and logical fundamentals ...
-1
votes
1answer
68 views
What makes a function computable?
It seems to me, at the moment, that I don't understand where the line is drawn between "computability" and being incomputable. The main question is, is it the ability to be "solved" only by trying out ...
2
votes
1answer
25 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
33 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
56 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
52 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
25 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
40 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
70 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?
...
2
votes
0answers
22 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
0answers
34 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).
...
1
vote
1answer
101 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....
2
votes
1answer
51 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 ...
0
votes
0answers
35 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
54 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(|\...
3
votes
2answers
202 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 ...
4
votes
1answer
277 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
307 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
42 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 ...
0
votes
2answers
86 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
53 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 ...
1
vote
2answers
59 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 ...
