Questions tagged [computability]

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

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

1
2 3 4 5
37