File Permission and Ownership

To show file permission and ownership (owner, group), use

ls -l

For instance,

-rw--w-r-- 1  mzt mzt    37 2013-01-20 08:57 code.py
drwxrwxr-x 2  mzt root 4096 2013-01-20 08:57 foo

To change the owner to root

chown root code.py

To change the group to root

chgrp root code.py

File permissions are given as code r (read), w (write), x (execute), d marks it is a directory. There are three classes of codes per file/directory, respectively they are for owner, group, others.

To add execute permission for the owner,

chmod u+x code.py

To set exactly read permission for the others,

chmod o=r code.py

To add both write and execute permission for the group,

chmod g+wx code.py

To remove execute permission for everyone,

chmod a-x code.py

To recursively apply write permission for both the owner and the group on a folder,

chmod -R ug+w foo

Note that performing these modifications may also affect your right on these commands. A non-root user can't modify a file/directory which belongs to root.

Practical vi Techniques

Although many places have iterated vi common commands, one may still come across with obstacles to maneuver comfortably.
The following is an ongoing list which I consider be worth recording and practicing.

• Syntax Highlight (update your vim if this is not installed as default):
  

  sudo apt-get install vim
  :syntax on, :syntax off
  

• Undo (one can undo multiple steps with the newer version)

  u

• Replace (refer advanced regex skills):

  :s/foo/bar/g

• Search by keyword

  /keyword

• Go to the first line, last line, head of line, end of line

  1G, G, 0, shift+4
  

• Backward or forward by one word

  b, e

• Go to line n

  :n

• New line with input mode (on next line, on previous line)

  o, shift+o

• Multiple lines cut-and-paste, copy-and-paste

  ndd+p, nyy+p
  

• Copy-and-paste from clipboard (using the shortcut of terminal window)

  ctrl+shift+c, ctrl+shift+v

• Set line number and unset

  :set nu, :set nu!

• Save the file often, override even when complaining read-only permission

  :w, :w!

Rice-Shapiro Theorem

The Rice-Shapiro theorem is thus phrased (due to Mr. Zunino's notes, link ), Given $\mathcal{F}$ is a set of partial recursive functions, i.e. $\mathcal{F} \subseteq \mathcal{R}$. Also $A = \{ n | \varphi_n \in \mathcal{F} \} \in \mathcal{RE}$. Then $$ f \in \mathcal{F} \Leftrightarrow \exists g \subseteq f . \big( \mathsf{dom}(g) \textit{ is finite} \wedge g \in \mathcal{F} \big) $$ It is rewritten in the counter-positive manner to prove $A \notin \mathcal{RE}$.

• check $A$ is semantically closed
• ($\Rightarrow$) pick $f \in \mathcal{F}$ s.t. $\nexists g \subseteq f . g \in \mathcal{F} \wedge \mathsf{dom}(g) \textit{ is finite}$
• ($\Leftarrow$) pick $f \notin \mathcal{F}$ s.t. $\exists g \subseteq f . g \in \mathcal{F} \wedge \mathsf{dom}(g) \textit{ is finite}$

Some examples.

• $A = \{ n | \mathsf{dom} (\varphi_n) \backslash \mathsf{ran} (\varphi_n) \neq \varnothing \}$
• $B = \{ n | \mathsf{dom} (\varphi_n) \text{ is finite} \}$
• $C = \{ n | \mathsf{dom} (\varphi_n) \text{ is infinite} \}$

$A \notin \mathcal{RE}$. By R-S $\Leftarrow$, we provide $g(0)=1 \in \mathcal{F}$, also we scheme $f(0)=1,f(1)=0$, s.t. $g \subseteq f \wedge f \notin \mathcal{F}$, both $f$ and $g$ are finite (let the otherwise case undefined).

$B$ and $C$ are both not $\mathcal{RE}$ (directly from R-S theorem). This says, the set of indices of all finite domain functions are not recursively enumerable. So is the set of indices of all infinite domain ones.

Recursion Theory

To be updated.

• A set $A \subseteq \mathbb{N}$ is recursive if its characteristic function is computable, noted as $A \in \mathcal{R}$
• A set $A \subseteq \mathbb{N}$ is recursively enumerable if its semi-characteristic function is computable, noted as $A \in \mathcal{RE}$

Example. Justify the following sets whether they belong to $\mathcal{R}$

• $A = \{ \mathsf{pair}(max(1000,k),n) | \varphi_n(n) \textit{ halts in } k \textit{ steps} \}$
• $B = \{ \mathsf{pair}(min(1000,k),n) | \varphi_n(n) \textit{ halts in } k \textit{ steps} \}$

$A \in \mathcal{R}$. Given an input $y$, $n=\mathsf{proj2}(y)$, then $\varphi_n(n)$ halts either within 1000 steps, or $\mathsf{proj1}(y)$ steps, which can be computed.

$B \notin \mathcal{R}$. By contradiction, assume $V_B$ is a verifier. Then We can write a verifier also for $\mathsf{K}$ $$V_{\mathsf{K}} = \begin{cases} 1 & \textit{if } V_B(\mathsf{pair}(y,n))=1 \textit{ for some } 0 \leqslant y \leqslant 1000 \\ 0 & o.w. \end{cases}$$ And $\mathsf{K} \notin \mathcal{R}$ due to diagonalization argument. The trick lies in $A$ and $B$ is that $A$ records the halting step of functions taking over 1000 steps, but $B$ is not.

Appendix

• $\pair (n,m) = m + \frac{(n+m)(n+m+1)}{2}$
• $\projl(\pair(n,m)) = n$

Lambda Definability

A set is $\lambda$-definable if a verifier can be written in $\lambda$-calculus

Here is a collection of examples (tbd). $$ A = \{ \# M | \mathbf{\Theta} M =_{\beta\eta} (\lambda x.xx) \} $$ Such $A$ is empty due to the fact that $\forall M. \mathbf{\Theta} M \not \Rightarrow_{\beta\eta}$. Thus $V_A = \mathbf{K} \mathbf{F}$ $$ B = \{ \# M | M \mathbf{T} =_{\beta\eta} M \mathbf{F} \ulcorner M \urcorner \}$$ $$ C = \{ 2^{\#M} \cdot 3^{\#N} | M =_{\beta\eta} N \}$$

Suppose $C$ is $\lambda$-defined by $V_C$, we scheme a set $C' = \{ \#M | M =_{\beta\eta} \mathbf{I} \}$, then it would be defined by

$$ V_{C'} = \lambda n . V_C ( \mathbf{Mul} \, (\mathbf{Exp} \, \mathbf{2} \, n ) \, (\mathbf{Exp} \, \mathbf{3} \, \ulcorner \mathbf{I} \urcorner )) $$

However, $C'$ is not $\lambda$-definable due to Rice's theorem.

Appendix - Common Lambda Terms

• $\mathbf{\Theta} = (\lambda wf.fww)(\lambda wf.fww)$, $\mathbf{\Theta}$ is a fixed-point combinator, i.e. $\mathbf{\Theta}F =_{\beta\eta} F(\mathbf{\Theta}F)$
• $\ulcorner M \urcorner$ is the encoding of $M$ in Church numbers.

Determine the Convergence of an Improper Integral of Polynomials with Parameters

The question is as follows, Determine for which $\alpha$ does the integral converge:

$$\int_3^\infty \frac{(x^{\alpha} +1)^{^\frac{2}{3}}}{(x+1)^{\frac{5}{3}}(x+2)} dx$$

For the theory of testing the convergence of integrals, please view the Czech Math Tutor page (link)

We need to utilize a fact on the improper integral of polynomials

\begin{align*} \int_1^\infty \frac{1}{x^p} dx &= \begin{cases} \frac{1}{p-1} &p>1 \\ \infty &o.w. \end{cases} \end{align*}

Here we need to make $\frac{8}{3} - \frac{2\alpha}{3} > 1$ to make our integral converge. Thus $\alpha < \frac{5}{2}$

LaTeX: Positioning Treaky Footnotes

Footnotes to Paragraph/Section Titles

When you put foonotes in paragraph titles or section titles, you will get complaints from LaTeX. The following fixes this and puts no footnotes in the table of contents.

\paragraph[foo-title]{foo-title \protect\footnote{bar-footnote}}
\section[foo-title]{foo-title \protect\footnote{bar-footnote}}

Footnotes to Captions

\begin{figure}
\includegraphics[]{foo.eps}
\caption[bar-title]{bar-title \footnotemark}
\end{figure}
\footnotetext{Here goes your foot note text}