-2
votes
0answers
32 views

Maximum number of compressed RLE strings under any given length

Given a random string of length L (for instance, "01100010000101" of length "14"), and knowing that this string is only numerical, how many other strings under the form Y one can achieve by ...
1
vote
1answer
54 views

Is there a more general proof for the halting problem?

Note:If this question is better suited for a different site, please tell me in the comments. Summary:Is there a proof for the impossibility of the halting problem that doesn't involve calling it on ...
-1
votes
1answer
54 views

Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
-1
votes
1answer
70 views

Turing & Computability & Computation

We know if we have: we can show (T=t= Turin Redu.) but i have no idea why this relation be correct? any idea?
2
votes
0answers
50 views

Big Challenge in TM & R.E Set [closed]

we know that Halting problem {(M.w) | M halts on input w} is r.e but not recursive. i see the following sentence in one book. "the set of {(M.w) | M halts on input w and M is a TM}} is not r.e" ...
2
votes
0answers
27 views

Generating interesting random TMs

To get a more intuitive understanding of the halting problem I want to generate some random TMs and see how they behave, what some heuristics can tell about them, etc. The problem is that, if I ...
0
votes
1answer
55 views

Function Combination on Computer Science

I read some material on Computational Function, every one could describe the result of following combination? suppose $g_1(x)=3x$, $g_2(x)=4x$, $f(x,y)=x+y$, how we compute combination of $f$ with ...
0
votes
0answers
71 views

Primitive Recursive Predicate Challenge

I'm an Computer scientist, and I recently ran into a challenge. If we have primitive recursive predicate $P(x), Q(x)$, I think that all of following 4 expressions can be primitive recursive. Any hint ...
0
votes
0answers
43 views

Recursive Set and Complement Problem

if we have $$A=\{x:|W_x\ne\phi\}$$ can we say always my tight listed below is true? $A$ is recursive , $A$ is r.e, complement of $A$ is r.e, complement of $A$ is not recursive?
0
votes
1answer
48 views

Complexity & Computation & Logic Problem [closed]

As i study for prepare to CS Final exam, i have some challenges. can i say all of following statements are true? 1) each infinite recursive set, is union of two disjoint infinite recursive set? 2) ...
2
votes
0answers
27 views

Bijection of simple set

Let $X$ is simple set (http://en.wikipedia.org/wiki/Simple_set) $Z \subset X$ is infinite recursive set. $Y = X$ \ $Z$. How to prove that there is a computable bijection $f$ that $x \in X ...
1
vote
0answers
25 views

Directed Hamiltonian Reduction

The reduction function given by Richard Karp in 'Reducibility among combinatorial problems' for Directed Hamiltonian Cycle $\leq_{p}$ Undirected Hamiltonian Cycle goes as follows : for input $G = ...
1
vote
1answer
25 views

Polynomial Reduction for restriction

I ran across a polynomial reduction that used the fact that one language was a restriction of the other. Is that statement really true? $$ L_1 \subseteq L_2 \rightarrow L_2 \leq_{p} L_1 $$ Thanks!
0
votes
1answer
25 views

Efficiency LL and LR parsing

My question is, is an LL parser or an LR parser more efficient (in big-O terms) ? I don't mean in terms of coding the parser, but rather in the context of the runtime of the parser. Is there a ...
1
vote
1answer
42 views

Are all polynomial-bounded functions computable? [closed]

Let $f = O(g)$, where $g$ is a polynomial. Then is $f$ computable? Let $K(s)$ be Kolmogorov complexity of a string $s$. It's an incomputable function. No. Let $f(x) : \Bbb{Q} \to \Bbb{R}, \ f(x) = ...
1
vote
4answers
69 views

Examples of partial functions in which the domain is not known?

I was reading this, it mentions about a kind of function in which the exact domain is not known. The only example given is this one - and I'm not really sure I understood it. I got curious about it: ...
0
votes
3answers
92 views

What is the difference between regex operations in math and regex in UNIX / Linux?

What is the difference between regular expression operations (union, concatenation, kleene star) and regular expression (implemented in UNIX and can be used together with the grep command)? Are there ...
0
votes
1answer
88 views

If the union of two languages is NP-complete, is one of them NP-complete?

Question 1) If $A\cup B$ is NP-complete, and $A$ is NP, and $B$ is P, then is $A$ NP-complete? I don't think so but I am unsure. When I try to reduce $A\cup B$ to $A$, I fail because strings in $B$ ...
1
vote
1answer
33 views

Showing a Problem Is Undecidable

How can I show that T is undecidable using only this information? $$T = \{\langle M, w, r\rangle \mid M \text{ accepts } w^r \text{ when it accepts } w.\}$$ So, what it's saying is that the machine ...
0
votes
1answer
66 views

Reduction from HALT on any string to HALT on empty string

The title says it all (if I have phrased it properly). How can we show that HALT on any string is undecidable using a decider for HALT on empty string? I think this is written: $$ HALT \leq ...
0
votes
1answer
41 views

Polytime implementation of Discrete Log using primitive recursive functions

The primitive recursive functions are defined by Godel as: $z() = 0$ $s(x) = x+1$ $\pi_i(x_1, \dots, x_k) = x_i$ Plus closure under Composition: $h(x_1, \dots, x_m) = f(g_1(x_1, \dots, x_m), ...
1
vote
1answer
57 views

Show that the Turing machine will solve the self-halting problem

Suppose we have Turing machine $M^*$ that: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Show that you cannot construct $M^*$. ...
2
votes
1answer
42 views

The “computability” of fundamental physical constants

I would like to ask if any of the fundamental physical quantities like the speed of light or plancks constant (all measured according to a common standard of of units) can be classified as computable ...
2
votes
1answer
139 views

Subsets of all Diophantine's sets

Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable $\Leftrightarrow$ graph of function is Diophantine. Consider some subset $S$ of computable functions (for example some Grzegorczyk's class or ...
0
votes
1answer
36 views

classifying problems with reducibility

How can we use a reduction to prove non membership of a class. Can we say if A is reducible to B they are in same class or if we can't reduce A to B. B is not same class as A. Regards,
3
votes
1answer
35 views

Mapping reduction to show NeverHalt is undecidable

I need help with showing that $NeverHalt_{TM} = \{\langle M\rangle|M\text{ is a TM which runs forever on every input $w$}\}$ is undecidable by giving an explicit mapping reduction. To show that a ...
1
vote
0answers
59 views

Showing particular language is NP-complete

How is FLO NP-complete? Let G be a social network where vertices correspond to people and edges are relationships between people (undirected). Some pairs of people (who are friends) get married. We ...
1
vote
2answers
100 views

Books about Turing machines and undecidability

I need help with finding literature about Turing machine and undecidability. First book I was suggested is Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani and Ullman. ...
2
votes
1answer
118 views

If P = NP, then 3-SAT can be solved in P

Prove that if $P = NP$, then there is an algorithm that can find a boolean assignment for a 3-SAT problem in P time if it exists. $P = NP$ only says that we can decide whether a 3-SAT problem is ...
0
votes
1answer
39 views

Prove a language is NP-Complete

$A$ is NP-complete. $B$ is P. $A \cap B = \emptyset $ $A \cup B \neq \sum^{*}$ Prove that $A \cup B $ is NP-complete. How can I prove this ? I think if anything can be P-reducible to A then it ...
1
vote
1answer
61 views

Ackermann function and primitive recursiveness

If we define $b_n(m) := a(n,m)$ for all $n$ and $m \in \mathbb{N}$. For which $n$ is the function $b_n$ primitive recursive and for which $n$ it is not a primitive recursive function? Can anyone ...
2
votes
1answer
57 views

Decidable language closed under complement

Why are decidable languages closed under complement? So if L is decidable why is the complement of L also decidable.
1
vote
1answer
60 views

Generating a context free grammar

How do I generate a context free grammar for a language $$\left\{a^ib^jc^k:i=j\text{ or }j=k,\text{ and }i,j,k\ge 0\right\}\;?$$ Thanks.
3
votes
2answers
120 views

context free grammar problem

$L$ is the context free grammar over $\{a, b\}$ $S \rightarrow aSb \; | \;bR \; |\;Ra$ $R \rightarrow bR \;|\;aR\;|\;\epsilon$ Briefly describe this CFG with English sentences and prove your ...
0
votes
1answer
173 views

Simultaneous recursion

I have no idea how to even start proving the following theorem: If $f_0, f_1: \mathbb{N}^r \rightarrow \mathbb{N}$ and $g_0, g_1: \mathbb{N}^{r+3} \rightarrow \mathbb{N}$ are primitive recursive, ...
0
votes
2answers
52 views

context free grammar design

Design a context free grammar and PDA for the following language. $$\Sigma = \{0,1\},\qquad L = \left\{uv \mid u \in \sum^{*} \;v\in \sum^{*}1\sum^{*} \text{ with }|u| \geq |v| \right\}$$ I'm not ...
0
votes
1answer
128 views

Arithmetic Hierarchy problems

Is $\Sigma^{0}_n$ closed under intersection? I think yes m I correct? Let $L_1$ be an $\Sigma^{0}_1$ complete language, and $L_2$ be a $\Pi^{0}_1$ complete language, such that $\emptyset \neq L= ...
3
votes
1answer
46 views

A diophantine program for a basic For Loop

By Matiyasevich, every computable function has a diophantine representation. I am wondering if there is a general way to represent a simple iterative for loop. Specifically: Let $f(x)$ be any ...
3
votes
1answer
47 views

Can this simple functional language be simplified further without losing any computational power?

Here is a definition of a very simplistic programming language (it is not Turing complete). Input to a function is any natural number. The following functions are primitive to the language: ...
-4
votes
1answer
195 views

How does 3-sat work in laymen's terms?

I know only basic math like so: (+,-,x,\,). And I studied a little bit of programming up to the point of knowing a little bit about Boolean values.I desperately want to understand the 3-sat question ...
1
vote
0answers
50 views

A diophantine definition of the Kleene star

Let $f(x \, | \, y_1, \dots, y_n)$ be a Diophantine polynomial that generates the Diophantine set $F$. By Matiyasevich, the set $F^*$ (Kleene star of $F$) is also Diophantine. My question: how can ...
1
vote
0answers
37 views

Regular Functional Algorithms

A language is regular if it is accepted by a read-only Turing machine. I am curious about applying this model to functional problems rather than decision problems. Definition: A functional read-only ...
2
votes
1answer
89 views

What does noncomputable really mean?

I believe I understand the definition of a noncomputable problem from an introductory computer science class, but I don't understand what it really means. One of my hypothesis was that a ...
3
votes
2answers
137 views

How do we know that every halting Turing Machine can be expressed as a recursive function?

I've hear many times that a major result in Recursion Theory is the equivalence of Turing and Godel's models: the functions implementable on a Turing machine are precisely the functions that can be ...
9
votes
0answers
163 views

Reference on standard types

This question is about what I presume is a basic construction in type theory. The finite types are defined as follows: 0 is a finite type; if $\sigma, \tau$ are finite types, then so is ...
26
votes
4answers
724 views

Why do we believe the Church-Turing Thesis?

The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to ...
3
votes
1answer
136 views

Books on computational complexity

Can anyone recommend a good book on the subjects of computability and computational complexity? What are the de facto standard texts (say, for graduate students) in this area? I've heard a thing or ...
6
votes
4answers
254 views

What is the relationship between “recursive” or “recursively enumerable” sets and the concept of recursion?

I understand that "recursive" sets are those that can be completely decided by an algorithm, while "recursively enumerable" sets can be listed by an algorithm (but not necessarily decided). I am ...
3
votes
1answer
93 views

Is this language decidable?

Is this language decidable? $$\{x\mid \text{$x$ is the code of a Turing machine that always halts on $y$ in less than $y^3$ steps}\}$$ I think it is, because it halts in a finite number of ...
1
vote
2answers
73 views

decidability of $\{x|W_x \text{is different from K in only finitely many elements}\}$

Is the following language decidable? Please explain your argument as I want to learn how such problems must be solved to do the rest on my own. $$\{x \mid W_x \text{ is different from K in only ...