Tag Info

Hot answers tagged computer-science

8

I understand where they got baa and ab but how did they get it to have abb ? Just follow the arrows. "a" takes you to q1, then "b" takes you to q2, and another "b" takes you to q3, which is an accepting state. this is confusing to me with having a q7 state here. The q7 represents a failure state. Once the automaton enters that, it can't leave, so ...

4

Expanding on Newb's point, you can think of Q7 as a 'trap' - the automaton can never escape, since both A and B lead back to Q7. It is necessary so that all strings are valid inputs to the FA, acting as a 'catch-all' for strings longer than four characters; however, as we've noted before, only ab, abb, and baa will be accepted.

4

All of them. It's possible to verify if a proof is valid in polynomial time, and it's possible to check if the last step of a proof is the theorem under consideration in polynomial time, so just encode "valid proof of length N" as a satisfiability problem. N = 1 DO IF (there is a valid proof of length N that proves theorem T) THEN return TRUE IF ...

4

This forum is about mathematics, and while career advice is sometimes found on here, your particular situation really requires career advice external to the mathematical sciences. ("What are your goals in life? What do you really want to do?" Etc.) I suggest you ask on academia.SE, but even those folks may not be the right crowd. You are looking for very ...

3

This is a funny question, and the answer is: it depends. First, if $x$, $y$ and $z$ are given sequentially, then pumping lemma implies that triplet $\langle 1(0^n),0,1(0^m)\rangle$ would have to be accepted for multiple values of $m$ and $n$, not necessarily equal. On the other hand, if the numbers are given simultaneously (e.g. on three tapes, or perhaps ...

3

That is a strange problem, and I feel like that shouldn't happen. Also, how can a player have points without having any shots? Anyway, here's an easy fix: $$\text{SOTP} = \frac{\text{shots on target} +.001}{\text{shots} + .001}$$ This will give you approximately the right answer most of the time, and will give you $1$ when $\text{shots} = 0$. Instead of ...

3

Let's make the problem a little more general and have two sets of input numbers $A$ and $B$, and ask for the number of pairs $(a,b)\in A\times B$ such that $a \oplus b \le K$. If $K=0$ then the answer is just $|A\cap B|$. Otherwise let $K=2^p+Q$ with $Q<2^p$. (This is just finding the most significant set bit in $K$). Then partition both $A$ and $B$ ...

2

I have a Knuth-Bendix program, and I ran it on this example. It completed with the $7$ rewrite rules: [R^3 -> 1], [S^3 -> 1], [S*R*S -> R^2], [R*S*R -> S^2], [R^2*S^2 -> S*R], [S^2*R^2 -> R*S], [S*R^2*S -> R*S^2*R] The $12$ normal form words are: 1, R, R^2, R^2*S, R*S, R*S^2, R*S^2*R, S, S*R, ...

2

Your best bet is to just store the values in an array, and when you want a value, access the array element at the index, i.e. a[1] for level 1, a[2] for level 2... a[199] for level 199. There's probably no nice formula for this problem. Here's why. Launching off from Peter's answer, let's assume you want to recreate the table he linked with a closed form ...

1

If you want an expression matching particular sequence of numbers, it's certainly useful to include more than first few numbers followed by a gap of unknown length and a bunch of "last" few numbers. A bit of Googling suggests that you're trying to get the numbers matching the experience required for level and got pointed to the term "Exponential regression" ...

1

You assume $L_{UIUC}$ is decidable, so $R$ is the machine that decides this language. Then, with the help of $R$, you construct a machine $S$ that can decide on $A_{TM}$. But it's a fact that $A_{TM}$ is undecidable, so you get a contradiction. The construction of $S$ is as follows. Input is a pair of a turing machine and a string, $\langle M,w\rangle$. ...

1

"Synthetic topology of data types and classical spaces" by Martin Escardo is an excellent (although quite long) source on the connection between programming languages and topology. The central idea is that an observable property in a data type corresponds to an open set in a topological space. If $f : \mathbf{X} \to \mathbf{Y}$ is a computable function and ...

1

As an aside, when doing any kind of math, make sure you have a strong grasp of the definitions. This means that for any proof you should write out the basic definition you will be working with. Also when trying to figure out my solutions below, I would recommend going step by step and attempting to verify, if you have trouble with any of my steps please let ...

1

Gold's property does not characterize languages learnable in the limit from positive examples. However, Angluin (1980; pdf) does give a property that is both necessary and sufficient: An indexed family $C$ of nonempty languages $\{L_1,L_2,..\}$ has Angluin's Property if there exists a Turing Machine which on any input $i \geq 1$ enumerates a finite set ...

1

Your question is rather imprecise, but it makes it even more interesting... First, why is your question imprecise? Mainly because you not specify the alphabet and the coding of the triples $(x,y,z)$. So let me modify your question as follows: Is there an encoding of the triples of integers $(x, y, z)$ on a suitable alphabet $A$ such that the set $L$ ...

1

No. Say your numbers are written in base $b$, so your alphabet is symbols 0 to $b - 1$, and (,). The proof is standard pumping lema: suppose $L$ is regular, let $N$ be the pumping lema constant. Take $\sigma =(10^N,10^N,20^N)$. The pumping lema tells you that a piece of the first number can be repeated without touching the other two. But doing so makes ...

1

For your josephus problem, the recursion has one function call for each of n, n-1, n-2,...,1, so that $T(n)=O(n)$ is the expected outcome. The $T(2n)=c\cdot T(n)+O(1)$ behavior occurs typically for divide and conquer algorithms like efficient integer powers, Karatsuba multiplication and other fast multiplication algorithms, FFT. There you can consider the ...

1

Hints: Question 1: Note that the neighbourhood of a vertex is the set of vertices that are connected to it plus all the edges that connect those vertices among themselves. A vertex does not belong to its own neighbourhood. If there is an edge between two vertices then they are definitely in the neighbourhood of each other. What would that imply? Question ...

1

1) You are right. To prove it formally, first note that you can replace any for-loop in a given program by some other equivalent construction, and then you can replace halting by entering some special for-loop. Now the new program reaches a for-loop if and only if the original program halts. Edit: For me, the word "looping" for Turing machines has a precise ...

1

I'm assuming that "looping" means just to run indefinitely (as opposed to "there exists a configuration that happens infinitely many times" assumed by @Arno). You are correct, this is false. You could append some for-loop to any program and asking about this loop would be equivalent to asking whether program halts. You are correct, no such program could ...

1

It's useful to use examples for the problem in several cases and then work out the problem. For this type of problem, you need $\dbinom{n}{2} + \dbinom{m}{2}$ more edges to make $K_{m,n}$ complete. Remember that $K_{m,n}$ is a complete bipartite graph, which has each of $m$ vertices connected with each of $n$ vertices. To get $\dbinom{n}{2}$, we need to ...

1

@NasuSama's answer is a good approach (by counting how many edges we need to add in each partite set). An alternative way: you have already noted that the number of edges in $K_n$ is $\frac{n(n-1)}{2}$. So the number of edges in $K_{m+n}$ is $\frac{(m+n)(m+n-1)}{2}$. Since we only have $mn$ edges in $K_{m,n}$, the number of edges we need to add is the ...

1

3 Is true: Color the first graph $T_k$ with two colors, lets call them for simplicity red and blue. The vertex you picked from this graph has one color. Color the vertex picked from the second graph with the other color. As the second graph $T_m$ is 2-colorable, once we colored one single vertex with a color we can complete it to a 2-coloring of this ...

1

Alternative solution: $$\text{SOTP} = \frac{\text{shots on target}}{\text{shots} + 0^{\text{shots}}}$$ Also, if you want to set it to be $-1$ when there are no shots (as one of the comments suggested), you could have $$\text{SOTP} = \frac{\text{shots on target}-0^{\text{shots}}}{\text{shots} + 0^{\text{shots}}}$$

1

Your $T(n)$ is not the Fibonacci sequence, but that doesn't matter; the asymptotic growth is still the same. Indeed, set $U(n) = T(n) + 1$, so that the recurrence relation becomes $$U(n) = U(n-1) + U(n-2).$$ Now suppose you want to prove that $T(n) = O(\alpha^n)$ (or equivalently, that $U(n) = O(\alpha^n)$) for some $\alpha$. This means that for all $n \ge ... 1 In your point,$i$is not a contradiction.$ii$is not either, because$M^*$halts always, so it just print$1$on itself. You have to use something stronger. (We note$M(x)\uparrow$to say$M$on input$x$does not halt, and$\downarrow$for halt) So we suppose we have (a recursive)$M^*$such that$$M^*(n)=\left\{\begin{array}cM_n(1)\downarrow ... 1 You can determining whether a point is inside a triangle by using barycentric coordinates$\lambda_i$: Point$\mathbf{r}$lies inside the triangle if and only if$0 < \lambda_i < 1 \;\forall\; i \text{ in } 1,2,3\$. Choose the first triangle to be fixed and check whether any vertex of the other lies inside the fixed one.

Only top voted, non community-wiki answers of a minimum length are eligible