Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,867
questions
0
votes
1answer
20 views
Are turing machines & equivalents with infinite sized random programs still turing machines?
Are turing machines with an infinite program tape that is completely random, or another example is a Game of Life simulation on an infinite randomly initialized grid, still turing machines, so to ...
1
vote
0answers
14 views
Are there more efficient recognizers for the halting problem?
Define the halting problem as $\{\langle M, w\rangle: \text{$M$ is a TM that halts on $w$}\}$. It is undecidable, but recognizable, with a naive recognizer that simulates $M$ on $w$. In a certain ...
0
votes
0answers
11 views
Turing machine with polynomial complexity on Jflap
I would like to ask a question: I have this very simple Turing machine. Simply by subtracting the numbers A and B, given the input M (A, B, C, D) =.
Using the Step function on Jflap, complete the ...
1
vote
1answer
31 views
Computable Numbers and Cantor's Diagonal Method
We were given the following problem in our university:
We will call $x \in (0; 1)$ computable iff there exists an algorithm (e.g. a programme in Python) which would compute the $n^{th}$ digit of $x$ (...
0
votes
1answer
37 views
How to evaluate all the binary sequences, generated from $2^{100}$ for finding all the sequeces which contain minimum $10$ zeros?
Suppose I have a set of $2^{n}$ number of binary sequences. And I have to select only those sequences which contain a minimum ${P}$ number of $0$ in it. For example, please consider the below one
Eg.
...
-1
votes
0answers
16 views
Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$
Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$.
Hello, I have been trying to solve this problem, my intuition tells that ...
-2
votes
0answers
27 views
Prove by reduction that the language $L^♦ = \{N | N \text{ is a } TM \text{ and } L(N) \text{ is a recursive language}\}$ is not recursive
Prove by reduction that the language $L^♦ = \{N | N \text{ is a } TM \text{ and } L(N) \text{ is a recursive language}\}$ is not recursive.
Hi, I've been strugling with this problem since yesterday, ...
0
votes
1answer
35 views
How Universal Turing Machines can do something if a machine doesn't accept?
In our Computability & Complexity course, we wanted to show that $ALL_{TM}\notin RE$. To do that, we have seen the following claim (I'm summarizing it):
Denote the languages:
$ALL_{TM}=\{(M)|L(M)=\...
0
votes
0answers
7 views
In the Recursion Theorem, does obtaining a description of SELF increase the length of the program?
In the following video, he mentions that x <- <SELF> (x obtaining a description of itself) is a "legal" operation for a Turing Machine to make. https://youtu.be/5yO_l2w0wIA?t=93
My ...
-4
votes
1answer
25 views
Polynomial-time Computable $f \circ g$. What does this implies for $f$ and $g$
Suppose that $f$ and $g$ are functions and $f \circ g$ is polynomial computable.
a) is it true that $f$ is also polynomial computable
b) is it true that $g$ is also polynomial computable
c) if we ...
-1
votes
1answer
33 views
Turing machine to find maximum of an infinite set
Given a set that is infinite but still countable, does a TM exist that goes over every element in the set and finds the maximum?
Is this a computable function?
1
vote
1answer
30 views
Is the following function computable? is it total?
I have the following function:
$f : N \to N $ and $f(n)= \max_{i \leq w(n)} g_{i}(n)$
with $g_1, g_2,...g_{w(n)}$ being an enumeration of all computable functions $g_i$, and $w : N \to N$ being any ...
0
votes
0answers
21 views
How to show that the set of all turing machines that halt on a blank tape form a recursively enumerable set
I learned in my class that set of all Turing machines that halt on a blank tape form a recursively enumerable set. I was told that you can prove it using an argument similar to the diagonalization ...
0
votes
0answers
12 views
Simple examples of Recursive Enumerable Functions
My understanding of Recursively Enumerable Functions is that they're recursive functions, but for some values of the arguments you put into the function they will stop and give an answer, and for ...
2
votes
3answers
87 views
Proving that a class equals NP ∩ coNP
We say that a non-deterministic Turing machine is nice if for every input x the following holds:
• Every computation path returns either ’accept’, ’reject’ or ’quit’.
• There is at least one non-quit ...
0
votes
0answers
39 views
In-place Acceptance Problem
In-place Acceptance Problem (InAP)
Instance: A deterministic Turing Machine M and a w input for it.
Question: Does M accept the input w without going through cell (|w|+1)?
Show that InAP is PSPACE-...
0
votes
1answer
50 views
Proving there exists no algorithm that can solve a basic problem
Consider the following basic problem, for which the statement is "obvious," but I can't seem to find totally convincing proof.
Problem: Let $S$ be a set of $n$ elements, where $n\geq 2$ is ...
0
votes
1answer
20 views
Could you solve co-RE problems with a halting oracle?
The halting problem is $RE$ complete. With an oracle for the halting problem could you decide problems in $co RE$ with an oracle for RE?
0
votes
1answer
43 views
In a rigorous mathematical sense, what is the significance of Turing-completeness?
I know that Turing-completeness is the ability to simulate a Turing machine, and from what I've read, the reason why we should care about Turing-completeness is that it demonstrates that a machine can ...
0
votes
0answers
39 views
Finite Number of Turing Machines that stop after k steps?
For this question suppose Alphabet for input is {0,1}.
Given:
L={<M> | M stops on every input after maximum 1000 steps}
My professor claimed that there is a ...
0
votes
0answers
35 views
Why EQ(cfg) is undecidable language?
I was studying Theory of Computation and I learned that EQ(cfg)[where the input is G1 and G2 both are CFGs and L(G1) = L(G2)] is undecidable but didn't understand why? Can you please explain it to me?
2
votes
0answers
15 views
Recurring computations for 2-counter machines
It is known that reachability of 2-counter machines is undecidable. As far as I know, it is semi-decidable though.
Now let's focus instead on the problem of deciding if a 2-counter machine has a ...
2
votes
1answer
40 views
Is there a simplistic way of describing the proof to the undecidability of David Hilbert's 10th problem?
I recently have been reading a bunch about David Hilbert's famous 10th problem, and trying to understand its proof. I am currently in the process of reading through an explanation of the proof, given ...
1
vote
1answer
34 views
Showing Turing machines are more computationally powerful than Finite State Machines
I've been pondering on whether Finite State Machines, particularly Mealy machines, can describe any computable function as Turing machines do. However "Mealy-computability" does not seem to ...
0
votes
0answers
24 views
Turing Machine that accepts L(M1) = {x^n y^2n z^n | n ∈ N}
I'm trying to design a Turing machine that accepts all strings in the language $$\{x^{n}y^{2n}z^{n}|\ n\in N\}$$ but I'm having trouble getting it to accepts when n> 1, for some reason it rejects ...
1
vote
0answers
15 views
Proving set of register machines that halt before k steps for some input is non-recursive
Given an enumeration of register machines $R_n$ that take a single natural number as input, and a constant $k$, the function $f$ is defined as:
$$
f(n) = \begin{cases} 1 & \exists m \text{ such ...
0
votes
0answers
23 views
Intuition behind : recursive algorithm takes exponential time [duplicate]
So I am studying an introductory chapter to dynamic programming that suggests a general solution to an optimization problem that occurs straightforwardly from expressing the problem with a reccurence ...
0
votes
1answer
36 views
Are there complexity classes so that RE ⊂ C ⊂ ALL?
If so what are they? These are Computational Complexity Classes that are not in RE but are in ALL. What would a problem in one of these classes look like? Would any of these problems be decidable?
1
vote
1answer
52 views
Any PRC class is closed under a construction involving a function f such that f(x+1) < x+1
So I'm trying to solve this problem(problem 8 from section 3.4) of the book Computability, Complexity and languages by Martin Davis:
Let k be some fixed number, let ...
-2
votes
1answer
73 views
Halting problem is undecidable proof-:
Confused with this proof. I will point my confusions here.
what is R(M)? They say it is representation of turing machine but what is it exactly? Is it tuples of turing machine? How do we decide w is ...
0
votes
0answers
12 views
Is it possible to use a random seed in the form of an integer to uniformly sample items from an array in sublinear time?
For example, given an array of reservation IDs:
...
3
votes
3answers
55 views
Explicit form of Hofstadters bluediag in floop
In " Gödel, Escher, Bach" Hofstadter introduces the programming languages Bloop and Floop. Relevant here is mostly that Floop is Turing complete, while Bloop differs from Floop in one aspect:...
-1
votes
1answer
28 views
If two languages are polytime reducable, does that imply they are also turing reducable
Is it possible for a pair of languages where A ≤T B but not A ≤p B?
I am not sure if this could be the case since a turning reduction would imply we can use a decider for one language to decide ...
0
votes
1answer
30 views
Reduction: Does polytime reduction imply Turing reduction?
I am unsure if given $A \leqslant_p B$, does that imply that $A \leqslant_T B$.
If we can polytime reduce $A$ to $B$, that would imply there is a decider for $A$ that runs in polynomial time which can ...
1
vote
0answers
31 views
Lack of "Any" scan for Turing Machines
I was reading Charles Petzold's The Annotated Turing that walks through Turing's original proof out of curiosity and feel like I've missed something during the part where Turing is describing ...
2
votes
0answers
30 views
Is there a link between the "padding argument" and the "padding lemma"?
In computability theory here is what the padding lemma says :
Every partial recursive function $\phi_x$ has $\beth_0$ indices and for each $x$ we can find effectively an infinite set $C_x$ of indices ...
-1
votes
1answer
32 views
no-input Turing Machine which accepts in k or fewer steps
Can we prove by induction that $A_k$ is computable for every choice of $k \in \mathbb{N}$?
$A_k$ is the set of descriptions of a no-input Turing Machine which accepts in $k$ or fewer steps.
1
vote
1answer
32 views
Arithmetic hierarchy via oracles
My professor gave an introduction to the arithmetic hierarchy via Turing reductions, stating that, for instance, $\Sigma_2 = \text{r.e.}^\text{r.e.}$ (namely an $\text{r.e.}$ pseudocode with access to ...
1
vote
1answer
150 views
A computable language with a non-computable language that is prefix-free
We say that a language $L$ is prefix-free if for every word $s\in L$ there does not exist a nonempty string $w\in\Sigma^*$ such that $sw\in L$ (i.e. no word in the language is a prefix of some other ...
0
votes
0answers
28 views
Is it possible to build a linear bound automata that decides A(NFA)?
Is it possible to build a linear bound automata that decides A(NFA)?
A(NFA)=Accepting Non deterministic Automata - language that contains the encoding of all the NFAs together with the strings that ...
-1
votes
1answer
29 views
complement of concatenate languages equal to complements concatenated?
please help me with this one.
(a formal answer would be much appreciated)
∀L1, L2 ⊆ Σ:
(L1 · L2)^c = L1^c · L2^c
when · represents concatination and ^c the complement language.
do not know if ...
0
votes
1answer
51 views
Reduction of RE and Rec languages
Suppose $L_1$ is reduces to $L_2$ in polynomial time, $L_1\leq_p^\mathsf{}L_2.$ we know that if $L_2$ is RE then $L_1$ is also RE and $L_2$ is REC then $L_1$ is also REC.
And also I know that if $...
-1
votes
1answer
41 views
Does Turing machine move left on particular input?
We know that RE language is the collection of unrestricted grammar which is known as type-0 grammar that's why emptiness, finiteness of every RE languages is undecidable. My question is how I check ...
0
votes
1answer
43 views
Difference between Counter-machine and stack machine
I read from this question that counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol).
My question is counter machine means counter coexist ...
0
votes
0answers
12 views
Need literature on First order logic definibility through Automata
Actually I am in search of some good literature on defining First order logic through Automata. It will be very helpful if someone can give me some links.
1
vote
1answer
44 views
How to prove that the set of recursive primitive functions is closed under
the scheme of iteration ?
Here is the scheme of iteration : for $g : \mathbb{N}^p\to \mathbb{N}$ and $h:\mathbb{N}^{p+1}\to \mathbb{N}$ two primitive recursive functions we associate $f: \mathbb{N}^{p+...
1
vote
0answers
53 views
Why is this function primitive recursive?
Let $f:\mathbb{N}^{p+1} \to \mathbb{N}$ a primitive recursive function and $g:\mathbb{N}^{p+1} \to \mathbb{N}$ the bounded sum defined by : $g(\bar{a},x)=\sum\limits_{i=0}^x f(\bar a , i)$.
To show ...
0
votes
1answer
48 views
Is set of all RE languages $\subseteq\\$ $\Sigma^{*}?$ [closed]
We know that any languages $\subseteq\\\\$ $\Sigma^{*}.$ Because any language collection of string over alphabet. And we know that set of all languages is $2^{\Sigma^{*}}$ which doesn't $\subsetneq\\\\...
1
vote
1answer
52 views
$\Sigma_3$-completeness of REG
Show the the following language is $\Sigma_3$-complete:
$$ \mathrm{REG} = \{ \langle M \rangle \mid L(M) \text{ is regular}\}. $$
Using the quantifier method I figured out that REG is in $\Sigma_3$, ...
1
vote
1answer
20 views
The Turing Machine in the proof of Time Hierarchy Theorem
In the proof of the Time Hierarchy Theorem, Arora and Barak writes:
Consider the following Turing Machine $D$: “On input $x$, run for $|x|^{1.4}$ steps the Universal TM $U$ of Theorem 1.6 to simulate ...
