Sunday, January 2, 2022

Recent Questions - Mathematics Stack Exchange

Recent Questions - Mathematics Stack Exchange


Polynomial function greater than derivatives

Posted: 02 Jan 2022 09:46 PM PST

Is it possible to prove that $f(x, y)>\frac{df}{dx}+\frac{df}{dy}$ if $f(x,y)$ is a polynomial function?

Variance minimisation with mean constant in Randomised Matrix multiplication

Posted: 02 Jan 2022 09:45 PM PST

For example of obtaining (a,b) by random sampling , when we change probabilities for each of sampling columns (a,0) and (0,b), then expected value for a trial or sampling is given by p*(a,0) + (1-p)(0,b). So on sampling twice we do not get expected value equal to (a,b) rather 2[p(a,0) + (1-p)*(0,b)].

So how can we keep mean same and minimise variance in this case ?

How to prove $\sum\limits_{i = 1}^n {{a_i}} \sum\limits_{i = 1}^n {a_i^2} \le n\sum\limits_{i = 1}^n {a_i^3}$, $a_i>0$?

Posted: 02 Jan 2022 09:41 PM PST

How to prove $\sum\limits_{i = 1}^n {{a_i}} \sum\limits_{i = 1}^n {a_i^2} \le n\sum\limits_{i = 1}^n {a_i^3}$, $a_i>0$?

A First Look At Rigorous Probability Theory - Jeffrey Rosenthal Exercise 4.5.10

Posted: 02 Jan 2022 09:40 PM PST

In the exercise, it says :

"Let $X_1,X_2,...$ be iid with mean $\mu$ and variance $\sigma^2$, and let $N$ be an integer-valued random variable with mean $m$ and variance $\nu$, with $N$ independent of all the $X_i$. Let $S=X_1+...+X_N=\sum_{i=1}^{\infty}X_i\mathbb{1}_{N\geq i}$. Compute $Var(S)$ in terms of $\mu,\sigma^2,m,\nu$."

Is the question saying that $N$ is a constant or that its values are integers? Also, I'm a bit confused about this part: $S=X_1+...+X_N=\sum_{i=1}^{\infty}X_i\mathbb{1}_{N\geq i}$. Why is it that $X_1+...+X_N=\sum_{i=1}^{\infty}X_i\mathbb{1}_{N\geq i}$? Is it just a notation?

Explicit sequence

Posted: 02 Jan 2022 09:37 PM PST

Show that the explicit sequence {gn}  n0 such that gn = (A+Bn) (4n ) for all non zero constants A and B solves the recurrence relation: gn+2 – 8gn+1-16gn= 0, n  0.

Problem in an approach to a number theory problem

Posted: 02 Jan 2022 09:37 PM PST

So I was given this problem and wanted to know if my approach is correct.

Q) For what value of n is the function f(n) = (1776^n + 2022^n) / n! at its maximum value ?

Here's what I did: My intuition was that we needed to find the interval for which f(n) is strictly increasing, i.e. f(n+1) > f(n)

Therefore (n+1) < 2022*(1+a^(n+1) / (1+a^n)) and a here is 1776/2022

This holds for n<= 1000 and n is [1000,2020] For n > 2021 this inequality doesn't hold true.

So therefore f(2021) is max and therefore n=2021 gives max value of f(n)

Would I be correct in that inference?

If $f(x_{0})=g(x_{0})$ and $f(x)\leq g(x)$, then $f'{(x_{0})}=g'{(x_{0})}$?

Posted: 02 Jan 2022 09:39 PM PST

Is this the next conjeture true?

"Let $f,g$ be functions defined on $\left ( a,b \right )$ that are differentiable at $x_{0}$. If $f(x_{0})=g(x_{0})$ and $f(x)\leq g(x)$ for all $x\in \left ( a,b \right )$. Prove that $f'{(x_{0})}=g'{(x_{0})}$."

I was trying to prove this by the definition $\varepsilon$-$\delta $ of the limit but I could not bound this term $\left |\frac{f(x)-g(x)}{x-x_{0}}\right |$. Any idea will be apreciated

Functions and constants.

Posted: 02 Jan 2022 09:24 PM PST

I have a book saying that:

If a.f(x) + b.f(1/x) = 1/x -5, then a.f(1/x) + b.f(x) = x - 5

Any logic or verification behind the same?

Calculating best letter for greedy Hangman algorithm

Posted: 02 Jan 2022 09:20 PM PST

I'm making a greedy Hangman algorithm such that the letter with the highest frequency in a word list is recommended to be chosen for the next guessed letter. It is easy to calculate the frequency of a letter in the list: frequency = (# words with letter) / (total # words). If we calculate the ratio for each letter, then the letter with the highest frequency is the best choice. Explanation:

  • If it is correct, then we don't lose a life and gain more insight into the final word.
  • If it is wrong, then we eliminate the largest number of possible answers from our list.

This solution works great and is easy to implement in code, but I theorize that doing multiple passes (meaning look more than 1 letter into the future) may result in different recommendations or at least provide more insight into what the best guessing strategy is.

In a perfect world, I would calculate the frequency for each letter and then the frequency for 1 or 2 more letter guesses after. But this is expensive, because it requires practically 26^n number of passes over the data set. So, I was thinking about only considering the top 3 results for each subsequent guess.

If I were to implement multiple passes, how would that affect the best guessing strategy? Specifically, what would the math look like for this? I'm lost here...

A Question about the Cumulative Hierarchy.

Posted: 02 Jan 2022 09:39 PM PST

I am self-studying set theory, following the book "The Joy of Sets" by Keith Devlin.

In section 2.2, page 37, the author introduced two equivalent definitions of the cumulative hierarchy.

First, for each ordinal number $\alpha$, there is a set $V_{\alpha}$. It is defined as follows:

  1. $V_{0}=\emptyset$
  2. For each successor ordinal $\alpha$, the set $V_{\alpha+1}$ is defined as the power set of $V_{\alpha}$, i.e $$V_{\alpha+1}=\mathcal{P}(V_{\alpha})$$
  3. For each limit ordinal $\alpha$, one might consider $$V_{\alpha}=\mathcal{P}\left(\underset{\beta<\alpha}{\bigcup}V_{\beta}\right).\tag{1}$$

This definition seems totally fine for me, but then the author claims that when we come to investigate the set-theoretic hierarchy more thoroughly we shall see that

$$V_{\alpha+1}=\mathcal{P}\left(\underset{\beta\leq\alpha}{\bigcup}V_{\beta}\right).\tag{2}$$

There's a very subtle difference between the presumed naive definition (1) and the set-theoretical defnition (2). How much is the correct definition (2) different from (1)?

After that, the author gives an equivalent definition for the limit ordinal number case:

$$V_{\alpha}=\underset{\beta<\alpha}{\bigcup}V_{\beta} \tag{3}.$$

How to show that definition (3) is indeed equivalent to definition (2)?

A direct consequence of Lusin's theorem?

Posted: 02 Jan 2022 09:14 PM PST

Lusin's theorem is stated in Royden's book as

Let $f$ be a real-valued measurable function on $E$. Then for each $\epsilon >0$, there is a continuous function $g$ on $\mathbb{R}$ and a closed set $F$ contained in $E$ for which $f=g$ on $F$ and $|E-F|<\epsilon$.

Here $E$ is a domain and $|E-F|$ refers to the measure of the complement of $F$ in $E$.

Now let $A$ be a Lebesgue measurable set in $\mathbb{R}$. Then the characteristic function $\chi_A$ would be measurable. In this case we let $\chi_A$ play the role of $f$ in Lusin's theorem. I need to show that we can find a continuous function $g$ such that $$|\{x \in \mathbb{R}:g(x) \neq \chi_A(x)\}| < \epsilon.$$

What Lusin's theorem tells us is that given a fixed $\epsilon > 0$, we can find a continuous function $g$ and a closed subset $B \subset A$ for which $\chi_A = g$ on $B$ and $|A-B|<\epsilon$. Since $A-B$ is precisely the set of points where $g$ and $\chi_A$ don't coincide, it does seem like we are done. Or am I missing something? For example, do I need to explicitly construct this closed subset $B$ or the function $g$?

To understand whether a module is flat, injective or projective through a explicit example

Posted: 02 Jan 2022 09:09 PM PST

Suppose a ring $R = \mathbb{C}[x, y]$, An ideal $I = (y^2 − x^3 + x^7)$ and $M = (R/I )_I \oplus (R/I )$. We can easily check that $R/I$ is an integral domain thus $I$ is a Prime Ideal. Hence multiplicative set is $S:=R\backslash I$, thus localization makes sense. Now I want to determine whether M is flat, projective, or injective but I have no idea how should I start this problem.

Any hint(s), suggestion(s), or help is highly appreciated. Thank you.

Intuition behind Principal Ideal Domain

Posted: 02 Jan 2022 09:48 PM PST

In a group, normal subgroups are most likely not cyclic and hence not generated by a single element. Ideals, as kernels of homomorphisms, is a similar concept to normal subgroups. Why would we expect some integral domains to have the property which all ideals are principle (generated by one single element)?

As a second part of the question, what is the best way to visualize principle ideal domains in general? Since prime ideals are maximal, these ideals "cover a lot of grounds" and their intersections contain the reducible elements? I do not know whether my visualization is correct.

$\int_{-1}^{1} \log\left(\frac{1+x}{1-x} \right) \frac{1}{1-ax} dx.$

Posted: 02 Jan 2022 09:44 PM PST

Definite Integral: $$\int_{-1}^{1} \log\left(\frac{1+x}{1-x} \right) \frac{1}{1-ax} dx,$$

where $0 < a <1$.


I tried with integration by parts taking $\log\left(\frac{1+x}{1-x} \right) $ as the first function and $\frac{1}{1-ax} $ as the second function, but it did not work.

Need some help to compute it.

Can A function grow quicker than another but never catch up to it

Posted: 02 Jan 2022 09:13 PM PST

I know this is a bit of a strange question, but it is one that has been on my mind for a little bit now. If we have two real valued functions f(x) and g(x) and they are both everywhere continuous and differentiable, could we choose f(x) and g(x) such that three conditions are satisfied

  1. f(x) > g(x) for all x in R
  2. g'(x) > f'(x) for all x in R
  3. f(x) and g(x) both diverge as x tends to infinity

Essentially, I'm asking if g(x) can grow infinitely but never catch up to f(x)? I know this problem would be simple if f(x) and g(x) converged, but I am curious about if these criterion could be met while maintaining divergence. My initial thought is that no such functions exist, but I am not sure how I could prove that. If such functions did exist, I suspect g(x) would need to be ln(x) or something of the like, but I am not convinced it is possible for these criterion to all be met. If anyone has insight either way, that would be extremely helpful.

If the following S is a vector space, are the following U and V subspaces of S?

Posted: 02 Jan 2022 08:53 PM PST

If the following $S$ a vector space: $$ S = \left\{ \begin{bmatrix} ax^2+bx+c \\d \end{bmatrix} | \space a,b,c,d \space \in \space \mathbb{R}\right\} $$

Then are the following $U$ and $V$ subspaces of S? $$ U = \left\{ \begin{bmatrix} ex+f \\g \end{bmatrix} | \space e,f,g \space \in \space \mathbb{R}\right\} $$ $$ V = \left\{ \begin{bmatrix} h \\0 \end{bmatrix} | \space h \space \in \space \mathbb{R}\right\} $$

In my head it makes sense for both to be subspaces of $S$.

$U$ could be the subspace of $S$ where $a = 0$, and $V$ could be a subspace where $a = b = d = 0$, but this does not seem like a correct answer at all to me.

Evaluate $\lim_{n \to \infty} \left(\int_0^1 e^{-x^2/n} dx\right)^n$

Posted: 02 Jan 2022 08:51 PM PST

Evaluate $\lim_{n \to \infty} \left(\int_0^1 e^{-x^2/n} dx\right)^n$.

I've tried this: from Taylor's expansion at $t_0=0$ of the function $e^t$, I get that for any $t \in \mathbb{R}$ it is $e^t \ge 1+t$. Moreover, for the Lagrange's remainder of the Taylor's expansion there exists $c(t)$ on the segment of endpoints $0$ and $t$ such that $$e^t=1+t+\frac{t^2}{2}+\frac{t^3}{6}e^{c(t)}$$ When $t \le 0$, it is $\frac{t^3}{6}e^{c(t)}\le0$; hence for $t \le 0$ it is $e^t\le1+t+\frac{t^2}{2}$.

Since $-\frac{x^2}{n} \le 0$ for any $x\in[0,1]$ and for any $n\in\mathbb{N}$, it is $$1-\frac{x^2}{n}\le e^{-x^2/n} \le 1-\frac{x^2}{n}+\frac{x^4}{2n^2}$$ For monotonicity of integral, integrating in the inequality in the interval $[0,1]$ it is $$1-\frac{1}{3n} \le \int_0^1 e^{-x^2/n} dx\le1-\frac{1}{3n}+\frac{1}{10n^2}$$ Since $1-\frac{1}{3n} \ge 0$ for any $n\in\mathbb{N}$, for the monotonicity of the $n$-th power it is $$\left(1-\frac{1}{3n}\right)^n \le \left(\int_0^1 e^{-x^2/n} dx\right)^n \le \left(1-\frac{1}{3n}+\frac{1}{10n^2}\right)^n$$ Since the limit preserves non strict inequalities, it is $$\lim_{n\to\infty} \left(1-\frac{1}{3n}\right)^n\le \lim_{n \to \infty} \left(\int_0^1 e^{-x^2/n} dx\right)^n \le \lim_{n\to\infty} \left(1-\frac{1}{3n}+\frac{1}{10n^2}\right)^n$$ So, since for $n\to\infty$ it is $\left(1-\frac{1}{3n}\right)^n \to e^{-1/3}$ and $\left(1-\frac{1}{3n}+\frac{1}{10n^2}\right)^n \to e^{-1/3}$, for the squeeze theorem it follows that $$\lim_{n \to \infty} \left(\int_0^1 e^{-x^2/n} dx\right)^n=e^{-1/3}$$ Could this work? I am unsure about the use of the Taylor formula for $t \le 0$ and the various monotonicity arguments I made.

How do I prove/disprove this??

Posted: 02 Jan 2022 09:50 PM PST

I have to do a proof of the statement: $$N(b)\equiv2(2b+1)^2(2b+2)^2=\sum_{k=0}^{2b-1}\Biggl(\prod_{j=1}^4(4b-k+j)\biggl)+\prod_{j=1}^4(2b+j)-(2b+1)\prod_{j=1}^3(2b+j)$$ I know I'm not supposed to ask a question and then have someone solve it, but I really just need at least a place to start this proof. It looks like it needs to be done by induction, but it seems too complicated to substitute $N(b)$ into $N(b+1)$, or maybe I am wrong.

I have come to this statement by attempting to deductively prove that the alternating sum of every row (apart from the $0$th) of Pascal's triangle is equal to $0$. I know it is a lot easier to do this by induction, and I understand how to, but still wanted to know if you could do this by deduction which lead me to the statement above. This also leads to the possibility of error, so the statement above may not be true.

Here is my working out if it helps: Note that $m\in Z_{\ge0}$

Could someone please explain how to prove this? And possibly show how?

What is the generalization of composition in abstract algebra (of rings and fields)?

Posted: 02 Jan 2022 08:48 PM PST

I'm newer to abstract algebra, and recently I came back to the concept of a field after finding rational functions form a field.

But, what I notice is that rational functions (and algebraic functions) are closed under composition.

If I equip a field with $+, \cdot, -, /,$ then what abstraction can I add to include $\circ,$ or function composition?

How does one generalize the idea of functional composition to include it to a field, and does such an object have a name?

Atiyah-Macdonald Proposition 1.2

Posted: 02 Jan 2022 08:53 PM PST

Proposition 1.2.

Let $A$ be a ring $\neq 0$. Then the following are equivalent:

i) $A$ is a field

ii) the only ideals in $A$ are $0$ and $(1)$

iii) every homomorphism of $A$ into a non-zero ring $B$ is injective.

I am confused by how ii) implies iii). Given a homomorphism of $A$ into a non-zero ring $B$, the kernel of the homomorphism is an ideal. So by ii), it has to be $0$ or $(1)$. If it is $0$, $A$ is injective. But why can't it be $(1)$?

Computing Smith normal form of matrix of integers

Posted: 02 Jan 2022 09:50 PM PST

I known that the Smith normal form of $A$ provides two unimodular matrices $U$ and $V$ of respective dimensions $m \times m$ and $n \times n$ such that the matrix $$B=[b_{i,j}]=UAV$$ and B has the form \begin{pmatrix} b_{11} & 0 & \ldots & 0 & 0 & 0 & 0\\ 0 & b_{22} & \ldots & 0 & 0 & 0 & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots\\ \vdots & 0 & \ldots & b_{ii} & \vdots & \vdots & \vdots\\ \vdots & \vdots & \ldots & 0 & 0 & 0 & 0\\ \vdots & \vdots & & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & 0 & 0 & 0 & 0\\ \end{pmatrix}

But I don't know how to find the matrices $U$ and $V$.
For example with the matrix $$A:= \begin{pmatrix} 3 & 4 \\ 2 & 5 \\ -2 & -3 \end{pmatrix}$$ How can I find the matrices $U$ and $V$ to conclude the Smith normal form?

Find a point on a line that creates a perpendicular in 3D space

Posted: 02 Jan 2022 09:35 PM PST

Visual of Question

Given the values of points A, B, and C, find the value of point D, where line BD is perpendicular to line AC.

This isn't homework, I'm creating a gizmo representation of "Spherecast" in unity. I know this is probably a pretty easy problem, I'm just really rusty with trig and can't find the right words in google.

Puzzle: binary number shrinkage on operation

Posted: 02 Jan 2022 09:46 PM PST

Given a random binary number with n digits. Define operation P: count number of ones, suppose there are k ones in this binary number, then flip k-th digit(1 to 0, 0 to 1) counting from left(or right, it does not make a difference). Repeat P until all digits are turned into 0. For example, b'101' has 2 ones, flip 2nd digit, we get b'111';follow same operation, b'110', b'100', b'000', end. 101->111->110->100->000, 4 steps.

  1. Are steps finite for all binary number? Prove it.
  2. For n digit random binary number, calculate expectation of steps.

I have test n=2,3,4 and they all fall into all zeros.

For any step, it will change 1->0 or 0->1. If steps are infinite, it means there will be a fixed point or loop for operation P, which does not exist except all zeros(need proof here). All zeros is a absorption state, all other state is unstable. Can anyone give a rigorous proof?

n=1, 0; 1->0. $E_1=(0+1)/2=0.5$

n=2, 00; 10->00; 01->11->10->00; 11->10->00. $E_2 = (0+1+3+2)/4=1.5$

n=3, 000; 100->000; 010->110->100->000; 011->001->101->111->110->100-> 000. $E_3 = (0+1+3+5+2+4+6+3)/8=3$

@JimmyK4542 does a simulation, the answer holds unitl 20,maybe prove by induction? $$E_n = n(n+1)/4$$

Area of a Triangle Inside a Trapezoid

Posted: 02 Jan 2022 09:17 PM PST

I am stuck on the following math contest problem:

Let $ABCD$ be a trapezoid with $AB \parallel CD$. The bisectors of $\angle CDA$ and $\angle DAB$ meet at $E$, the bisectors of $\angle ABC$ and $\angle BCD$ meet at $F$, the bisectors of $\angle BCD$ and $\angle CDA$ meet at $G$, and the bisectors of $\angle DAB$ and $\angle ABC$ meet at $H$. Quadrilaterals $EABF$ and $EDCF$ have areas $24$ and $36$, respectively, and triangle $ABH$ has area $25$. Find the area of triangle $CDG$

Diagram (by the user Moti):

enter image description here

I don't know what the source is, so if anyone knows, please let me know. I searched for a solution on Art of Problem Solving (AoPS) but I could not find one.

So far, I have only figured out that $\angle AED = 90^{\circ} = \angle BFC$ and that $[CDG] = [EDCF]+[EFG] = 36+[EFG]$. Does anyone know how to solve the problem?

Note: [X] denotes the area of the polygon X.

The "tangent line" is non-linear, and it's slope is the derivative?

Posted: 02 Jan 2022 09:04 PM PST

I'm taking Brilliant.org's calculus course, and I'm on the section called The Derivative.

My (mis)understanding:

A tangent line is a linear function that grazes a point, $a$, on the graph of a different function. The slope of that tangent line is the instantaneous rate of change at $a$. The way you find this is by taking the difference ratio, giving you the slope, and plugging in equal values for the input points. So, for the function $f(x) = x^2$, the slope would be:

$$\require{cancel} \frac{b^2 - a^2}{b-a} = \frac{\cancel{(b-a)}(b+a)}{\cancel{b-a}} = b+a$$

Now, considering the case as the difference between $b$ and $a$ gets smaller, or equivalently, as the secant line's two points become one and the same point, thus turning it to a tangent line:

$$\lim_{b \rightarrow a} b +a = 2b = 2a$$

Thus, the derivative of the square function is found, $f'(x) = 2x$. The slope of the tangent is $2x$, but apparently, the derivative isn't the slope of the tangent, it is only so the other way around (see this Math.SE answer). I could define any number of functions of the form $g(x) = ax$, which would be tangent to or intersect the function $f(x)=x^2$, when $x=a$. For any of these functions, $g'(x) = a$, as per the difference ratio. The slopes of these functions would be any arbitrary number $a$, not $2x$. So, it seems we're dealing with the slope of one particular tangent. However, I can't see how this tangent line is linear. If it is linear, it's slope is a constant, but $2x$ contains a variable.

All of this leads me to think that we're talking about the tangent line in a very different sense than the one of "a linear line that grazes the function's graph". But I've only been made familiar with the latter sense, and this mysterious sense is very ill-defined in my head. What is it and what does it have to do with tangent lines? The trick with morphing a secant line into a tangent line doesn't really explain this, because one can do that anywhere on the graph and wind up with tangent lines that have differing slopes, none of which are equal to $2x$.

Compute the next limit using CLT

Posted: 02 Jan 2022 09:35 PM PST

Let $\{X_n\}_n$ be a sequence of random independent variables with density function $f_{X_n}=4x^2e^{-2x} \chi_{x>0}$, $\forall n \in \mathbb{N}$ if $S_n=\sum_{i=1}^n X_i$ find $$\lim_{n \to \infty} \mathbb{P}[S_n \leq \frac{3n}{2}+\sqrt{3n}]$$

The strategy I used to solve it is to calculate $E[S_n]$ and $Var[S_n]$ and then manipulate $\mathbb{P}[S_n \leq \frac{3n}{2}+\sqrt{3n}]$ so that $$\mathbb{P}\left[\frac{S_n -\frac{3n}{2}}{\sqrt{3n}} \leq 0 \right]$$ is left and apply CLT directly. Is this procedure correct?

Any comments, suggestions or help would be greatly appreciated.


qualitative analysis of a separable ODE problem

Posted: 02 Jan 2022 09:48 PM PST

I have the following equation: $x'=(x-1)(t^2-1)h(t)$. Where $h(t)\in C^0(\mathbb{R})$ and $h(t)>0$. I have to prove that under this initial condition $x(3)=0$ the maximal interval for t is $\mathbb{R}$.For $t_+$ this is obvious because it is bellow the singular point and the solution is monotonically decreasing there. Now, for $t_-$ I used:$\int_{0}^{x} \frac{\mathrm{d}x}{x-1} = \int_{3}^{t_-}h(t)(t^2-1) \mathrm{d}t$ x goes to infinity so it diverges. But there is no other information about h and I am kinda stuck, would love some help.

Formula for the first base-$n$ digit of $n^{d+1}-\sum_{i=1}^{n}i^d$

Posted: 02 Jan 2022 08:58 PM PST

Let $k,n,d \in \mathbb{N}$ and $n>1$.

Converting $k$ in a base $n$,

$$k = (n_{ l} ~\cdots~ n_2~ n_1)_{n} \quad\text{where}\quad n_{l} \ne 0$$

Show that, if $$k = n^{d+1} - \sum_{i=1}^n i^d$$ then $$ n_l=n - \left\lceil\frac{\sum_{i=1}^n i^d}{n^d}\right\rceil $$

Example

Let $n=3$ and $d=2$.

$$3^3-(1^2+2^2+3^2)= 13 = (111)_{3}$$

So $n_l = 1$.

Simulating non-deterministic Turing Machine with 3 - Tape.

Posted: 02 Jan 2022 09:01 PM PST

I'm reading Sipser's description of a deterministic Turing machine D that is simulating a non-deterministic one (Page 179, Chapter 3).

3-Tape Diagram of Turing machine D

I'm having trouble understanding the behaviour of the 3rd "address" tape. I know this TM D will explore the computation tree with breadth-first search and it makes sense, but when I go on to read his description of this simulation (below), I can't put it together.

  1. Initially, tape 1 contains the input $\omega$, and tapes 2 and 3 are empty.
  2. Copy tape 1 to tape 2 and initialize the string on tape 3 to be $\epsilon$.
  3. Use tape 2 to simulate N with input $\omega$ on one branch of its nondeterministic computation. Before each step of N, consult the next symbol on tape 3 to determine which choice to make among those allowed by N's transition function. If no more symbols remain on tape 3 or if this nondeterministic choice is invalid, abort this branch by going to stage 4. Also go to stage 4 if a rejecting configuration is encountered. If an accepting configuration is encountered, accept the input.
  4. Replace the string on tape 3 with the next string in the string ordering. Simulate the next branch of N's computation by going to stage 2.

In step 3, we simulate N with input $\omega$ on simulation tape 2 for one branch of the computation tree. However, when it says to consult the next symbol to make a choice, I assume it is saying if successful that the 'symbol' transitions N and moves D deeper into the computation tree?

To make myself a bit more clear, Sipser wrote:

To every node in the tree we assign an address that is a string over the alphabet $T_b$ = {1, 2, ..., b}. We assign the address 231 to the node we arrive at by starting at the root, going to its 2nd child, going to that node's 3rd child, and finally going to that node's 1st child.

So why exactly in step 4, do we replace the string on tape 3 as opposed to appending? Wouldn't we lose our position in the computation tree if we simply replaced the string, as there will no longer be a queue for the breadth first search.

Also, I'm not entirely sure if I'm interpreting 'next string' and 'string ordering' properly. Are they referring to the next address string obtained from the child nodes?

How can I find a mod with negative number?

Posted: 02 Jan 2022 09:48 PM PST

I know how to solve mod using division i.e.

$$11 \mod 7 = 4$$

For this I did a simple division and took its remainder:

i.e.

$$11 = 7 \cdot 1 + 4$$

Where $11$ was dividend, $7$ divisor, $1$ quotient and $4$ was remainder.

But I have a problem with:

$$-11 \mod 7 = 3$$

How come it is $3$? I cannot figure this out using division but if it is possible I would like to.

No comments:

Post a Comment