Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
1,829
questions
1
vote
1answer
27 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
11 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.
0
votes
1answer
39 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+...
0
votes
0answers
44 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
41 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
44 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
13 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 ...
0
votes
1answer
34 views
Reasoning given with explanation of Halting Problem
I have read (and re-read) the informal proof of The Halting Problem. Can we not make the same argument using only the Program, without the Input {e.g. H(P) rather than H(P, I)}? I am confused by the ...
0
votes
2answers
55 views
Checking whether given measures qualify as computational resources
Do the following measures qualify as computational resources?
number of even-numbered states that the machine $M$ visits on input $x$
number of times that the machine $M$, when run on input $x$, ...
3
votes
1answer
45 views
Reduction of $RE$ language
Suppose that the language
$L_1$ reduces to the language $L_2$ in polynomial time, $L_1\leq_p L_2$. If $L_2$ is recursive enumerable then so is $L_1$, but why isn't $L_1$ recursive? Because $L_2$ is at ...
0
votes
1answer
17 views
Can an instance of the post correspondence problem have exactly one solution?
Can an instance of the Post Correspondence Problem (PCP) have exactly one solution?
-1
votes
0answers
19 views
Would a computable universe imply computable physical constants?
Suppose it does turn out that the universe consists entire of deterministic computation, that it could be running on a Turing machine in principle. Physicists in particular don't seem to think that's ...
1
vote
1answer
45 views
Reduction from recursive language to recursive enumerable
If any language
$L_1$ reduces $L_2$ in polynomial time $L_1\leq_p^\mathsf{}L_2.$ If $L_1$ is recursive then $L_2$ is recursive and recursively enumerable, is it true? Because $L_2$ is at least as ...
1
vote
0answers
65 views
Rogers (Kleene)'s fixed-point theorem and the Y combinator
In the Wikipedia article on Rogers' theorem, it is stated that the proof given by Rogers is a construction of a partial recursive function which implements the Y combinator.
I've just a basic ...
0
votes
0answers
23 views
Can we combine two non-terminals and use this as one non-terminal in CFG?
Let's consider this CFG-
S->AB [Here, **S** is the starting variable]
A->C
CB->Cb
C->a
Now, the question is- Check if ab is a valid string for the ...
-1
votes
2answers
60 views
What is the the greatest thing a computer has trouble doing?
If we have all these optimized programs for very specific tasks, what would be the antithesis of them?
I've asked a programmer friend of mine, and they thought a good answer had to do with multi-...
1
vote
1answer
15 views
How is it possible that for infinite L in R exists subset L' which is not in Re?
Proove that for every infinite $L \in R$ there is a $L' \subseteq L$ s.t $L' \notin RE$.
How can I proove it? if sketched on venn diagram it doesn't make sense...
From my point of view everything ...
0
votes
1answer
39 views
How does primitive recursion handle mutual recursion?
My intuition is that you can't call a function that has not yet been defined, although I have yet to find a source confirming this.
Is this true?
Thanks, friends :)
1
vote
1answer
29 views
What does it mean for an integer to belong to the halting problem?
I have come across the description of a function $F: \mathbb{N} \to \mathbb{N}$ where the function is defined one way for $n \in \mathcal{H}$ and another way for $n \notin \mathcal{H}.$ In this ...
2
votes
1answer
45 views
Does $L_1L_2 \notin RE$ imply $L_2L_1 \notin RE$?
Given two languages $L_1, L_2$ such that $L_1L_2\notin RE$,
is it always true that $L_2L_1 \notin RE$?
I wasn't able to prove it or find a valid counterexample.
-2
votes
1answer
217 views
Must a partial halt decider be a pure function of its inputs?
Must a partial halt decider be a pure function of its inputs?
A partial halt decider correctly decides the halt status of some of its inputs.
I am trying to write C code that would be acceptable to ...
1
vote
1answer
101 views
What is the regular expression for the language, {w | w does not contain the substring 11}
{w | w does not contain the substring 11}
What I am thinking: $(0^* 1 0^* )^*$
Is anything wrong with my expression?
Thanks in advance for your help!
0
votes
1answer
47 views
What is the sequence that is computed by a Turing machine?
so I was wondering how to know the sequence a Turing machine T computes?
We are reading The Annotated Turing by Charles Petzold at the moment which includes Turing's original paper "On Computable ...
2
votes
1answer
53 views
Turing machines which halt after updating a cell for the second or third time
We say that a Turing machine is fragile, if it halts after changing the symbol of one of the tape cells for the third time. Is it true that every language that is solvable on a Turing machine will be ...
2
votes
0answers
31 views
Equivalence between $\lambda$-calculus and recursive functions
I have two related questions:
Do you know of any good reference to the recursive function / lambda-calculus equivalence in terms of computability, including proofs?
Do you know of any reference to ...
3
votes
1answer
60 views
Can you diagonalize a language out of CSL?
In recursion theory, it is possible to diagonalize a computable function out of the class of primitive recursive functions. Can you do the same with context-sensitive languages? I was thinking we ...
0
votes
1answer
23 views
Recursive Bijections Between Countably Infinite Sets
The textbook I am currently studying (Introduction to Kolmogorov Complexity and Its Applications by Li and Vitanyi) uses the term 'recursive bijection'. In this context I believe that recursive refers ...
1
vote
1answer
36 views
Language classification
I am currently taking a computational course as part of my degree in Computer Science, and I would like to understand in depth the differences between these languages and if their belonging to R.
The ...
-1
votes
1answer
43 views
How to encode a Universal Turing machine to an Integer $\in\mathbb{N}^+$?
The proof of Hierarchy Theorems (including space hierarchy theorem, deterministic time hierarchy theorem, nondeterministic time hierarchy theorem) depend on constructing a Universal Turing machine ...
0
votes
1answer
28 views
Computation branches on NTM
I would like to run the following string $w=011101$ on the following NTM and figure out the respective computation branches and whether it accepts or rejects that string.
$\text{Start: }(q_0) 011101 $
...
0
votes
0answers
28 views
Is this language in RE?
Given the following language:
$$L=\left \{ <M> | \exists L \in R \quad s.t \quad L(M)\subseteq L \right \}$$
I need to determine it's compuation class(R or RE).
I used Rice Theorem as follows to ...
1
vote
0answers
39 views
What if have a algorithm that could generate a NFA of 42 states of any binary string of 2^32 length?
For example, if we have a true algorithm that could generate any NFA of at most 42 states from any binary string of 2^32 length. So, this algorithm can not just recognize the string but just recreate ...
4
votes
0answers
85 views
Necessity of encoding for certain models of computation
Consider the following model of computation (from here).
Although Fractran is Turing-complete, it assumes that the "user" is able to perform the steps of encoding the input ($2^{n + 1}$) ...
1
vote
1answer
49 views
If a computer can demonstrate singleton sets are closed, is the space Hausdorff?
In Haskell, I made a class of admissible (that is, second-countable and $T_0$) spaces:
...
2
votes
1answer
54 views
Given a string which was produced by mixing up a string of digits, find the original digits
I encountered the following problem:
Given a string which was produced by mixing up a string of digits (0-9), for example:
"otetwonhree" was produced by "onetwothree"~123, find ...
0
votes
1answer
45 views
Uncomputability of least member selection
I want to show that there is no TM $f$ such that whenever $W_x$ is nonempty then $f(x)$ is defined and is the least member of $W_x$, Where $W_x=\{w:w \in \Sigma^{*}\text{ and } M_x \text{ on }w \text{ ...
1
vote
0answers
30 views
Computability of base-conversion for streams
With regular numbers it is always possible to convert them from one (integer) base to another. But what happens if we consider numbers for which their magnitude is not known in advance, or in other ...
0
votes
0answers
50 views
is there a theory consider on infinitely many recursion?
of course there is a theory that how many recursive calling the same system to solve problems, this theory is "recursion theory", If i know correctly.
and recursion theory is computability ...
0
votes
0answers
24 views
Polynomial time function vs polynomial time algorithm
In the book Proof Complexity By Jan Krajicek, the definition of a functional propositional proof system is given as:
Definition 1: A functional propositional proof system is any
polynomial time ...
0
votes
0answers
29 views
Logarithmic space and time computable function for sequences over $\{0,1\}$
Given $\sigma_1 \dots \sigma_n$ a sequence or word of length $n$ over $\{0,1\}$ I was wondering if there is a computable function to calculate $\sigma_m$ in $\log(P(n))$ time where $P(n)$ is some ...
1
vote
1answer
38 views
Determine if for given some $L$, $S_L={L(M) : <M>\in L}$ then for any $L$, if $S_L=RE$ then $L\in R$ is True or False and explain
Determine if for given some $L$, $S_L=\{\ L(M) | <M>\in L \}$ then for any
$L$, if $S_L=RE$ then $L\in R$. Correct or Incorrect and explain why.
I think the claim is incorrect, and I'm trying ...
0
votes
1answer
61 views
Reduction from problem A to another problem B
I have a question from a test that I failed to pass, I failed to do the question.
The question:
Let A and B have two languages so that there is a reduction function f: $A\leq _pB$.
Suppose that $A \in ...
1
vote
2answers
56 views
Reduction between CLIQUE to SUBSET SUM
I have a question from a test that I failed to pass, I failed to do the question.
The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the ...
2
votes
1answer
37 views
Reduction from language in P to another language in NP
I have a question I was unable to do, from a last test I had.
This is the question:
Will be $A \in NP$
Let $c \in P$ be a language so that there exists $C \leq _pA$. Determine which of the following ...
5
votes
1answer
91 views
Reduction from the SAT problem to the NAE-SAT problem
I study complexity and computation independently.
I have a problem that I can not solve.
That's the problem:
For the SAT problem, there is a version in which we receive as input phrase $\varphi$ in ...
1
vote
2answers
136 views
edge-coloring and vertex-coloring reduction problem
I study complexity and computation independently.
I have a problem that I can not solve.
That's the problem:
Edge-Coloring problem, we get as input graph G = (V, E) and natural
number k and ask "...
0
votes
1answer
23 views
Reduction from the Clique problem to the Odd Clique problem
I have a question that is not clear to me, and I have not been able to answer it from a test I had.
This is the question:
Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And ...
0
votes
1answer
32 views
Complications of a language that reaches a state of reject
I have a question that is not clear to me, and I have not been able to answer it from a test I had.
This is the question
Let's look at the language $L_\mathrm{reject} = ${
$\left \langle M,w \right \...
3
votes
1answer
50 views
edge-coloring reduction problem
I study complexity and computation independently.
I have a problem that I can not solve.
That's the problem:
Edge-Coloring problem, we get as input graph G = (V, E) and natural
number k and ask "...
2
votes
1answer
36 views
Language in NPC and CoNP
A few days ago I had a test that I failed to pass, and it had a question that I failed to do.
the question:
given:
$A \in NPC$
$A \in CoNP$
Determine which of the following statements is correct:
$P\...