Questions tagged [computability]

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

Filter by
Sorted by
Tagged with
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 ...
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 ...

1
2 3 4 5
38