From 4f670b750af5c11e1eac16d9cd8556455f89f46a Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan@mnpi.eu>
Date: Fri, 16 May 2025 22:18:44 +0200
Subject: Changed layout for more manageable volumes

---
 vol1/1.1.lyx | 550 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 550 insertions(+)
 create mode 100644 vol1/1.1.lyx

(limited to 'vol1/1.1.lyx')

diff --git a/vol1/1.1.lyx b/vol1/1.1.lyx
new file mode 100644
index 0000000..9644d3b
--- /dev/null
+++ b/vol1/1.1.lyx
@@ -0,0 +1,550 @@
+#LyX 2.4 created this file. For more info see https://www.lyx.org/
+\lyxformat 620
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\input defs
+\end_preamble
+\use_default_options true
+\maintain_unincluded_children no
+\language english
+\language_package default
+\inputencoding utf8
+\fontencoding auto
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_roman_osf false
+\font_sans_osf false
+\font_typewriter_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\float_placement class
+\float_alignment class
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_formatted_ref 0
+\use_minted 0
+\use_lineno 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style english
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tablestyle default
+\tracking_changes false
+\output_changes false
+\change_bars false
+\postpone_fragile_content false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\docbook_table_output 0
+\docbook_mathml_prefix 1
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc1[10]
+\end_layout
+
+\end_inset
+
+The text showed how to interchange the values of variables 
+\begin_inset Formula $m$
+\end_inset
+
+ and 
+\begin_inset Formula $n$
+\end_inset
+
+,
+ using the replacement notation,
+ by setting 
+\begin_inset Formula $t\gets m$
+\end_inset
+
+,
+ 
+\begin_inset Formula $m\gets n$
+\end_inset
+
+,
+ 
+\begin_inset Formula $n\gets t$
+\end_inset
+
+.
+ Show how the values of the 
+\emph on
+four
+\emph default
+ variables 
+\begin_inset Formula $(a,b,c,d)$
+\end_inset
+
+ can be rearranged to 
+\begin_inset Formula $(b,c,d,a)$
+\end_inset
+
+ by a sequence of replacements.
+ In other words,
+ the new value of 
+\begin_inset Formula $a$
+\end_inset
+
+ is to be the original value of 
+\begin_inset Formula $b$
+\end_inset
+
+,
+ etc.
+ Try to use the minimum number of replacements.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+
+\begin_inset Formula $t\gets a,a\gets b,b\gets c,c\gets d,d\gets t$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc5[12]
+\end_layout
+
+\end_inset
+
+Show that the 
+\begin_inset Quotes eld
+\end_inset
+
+Procedure for Reading This Set of Books
+\begin_inset Quotes erd
+\end_inset
+
+ that appears in the preface actually fails to be a genuine algorithm on at least three of our five counts!
+ Also mention some differences in format between it and Algorithm E.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+It fails on finiteness (it doesn't have an ending condition),
+ definiteness (the instructions are not unambiguous),
+ and effectiveness (solving the Fermat's theorem on the exercises is not 
+\begin_inset Quotes eld
+\end_inset
+
+sufficiently basic that it can be done exactly and in a finite length of time
+\begin_inset Quotes erd
+\end_inset
+
+),
+ and it may have no output (although,
+ this time,
+ this is the output).
+ It also doesn't have a header,
+ an ending mark,
+ or a letter prefix on the steps.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc7[HM21]
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $U_{m}$
+\end_inset
+
+ be the average number of times that step E1 is executed in Algorithm E,
+ if 
+\begin_inset Formula $m$
+\end_inset
+
+ is known and 
+\begin_inset Formula $n$
+\end_inset
+
+ is allowed to range over all positive integers.
+ Show that 
+\begin_inset Formula $U_{m}$
+\end_inset
+
+ is well defined.
+ Is 
+\begin_inset Formula $U_{m}$
+\end_inset
+
+ in any way related to 
+\begin_inset Formula $T_{m}$
+\end_inset
+
+?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+On average,
+ it will be the case that 
+\begin_inset Formula $n>m$
+\end_inset
+
+,
+ so after one step,
+ the two numbers will exchange positions and,
+ after two steps,
+ we'll have the same value for 
+\begin_inset Formula $m$
+\end_inset
+
+ but 
+\begin_inset Formula $n$
+\end_inset
+
+ will be the remainder of the original values of 
+\begin_inset Formula $n$
+\end_inset
+
+ and 
+\begin_inset Formula $m$
+\end_inset
+
+,
+ which is uniformly distributed on the integers between 
+\begin_inset Formula $0$
+\end_inset
+
+ and 
+\begin_inset Formula $m-1$
+\end_inset
+
+.
+ This means 
+\begin_inset Formula $U_{m}$
+\end_inset
+
+ is two plus the average number of times that E1 is executed if 
+\begin_inset Formula $m$
+\end_inset
+
+ is known and 
+\begin_inset Formula $0\leq n<m$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Further,
+ since after one step,
+ the two numbers interchange,
+ it is clear that 
+\begin_inset Formula $U_{m}=1+T_{m}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc9[M30]
+\end_layout
+
+\end_inset
+
+Suppose that 
+\begin_inset Formula $C_{1}=(Q_{1},I_{1},\Omega_{1},f_{1})$
+\end_inset
+
+ and 
+\begin_inset Formula $C_{2}=(Q_{2},I_{2},\Omega_{2},f_{2})$
+\end_inset
+
+ are computational methods.
+ For example,
+ 
+\begin_inset Formula $C_{1}$
+\end_inset
+
+ might stand for Algorithm E as in Eqs.
+ (2),
+ except that 
+\begin_inset Formula $m$
+\end_inset
+
+ and 
+\begin_inset Formula $n$
+\end_inset
+
+ are restricted in magnitude,
+ and 
+\begin_inset Formula $C_{2}$
+\end_inset
+
+ might stand for a computer program implementation of Algorithm E.
+ (This 
+\begin_inset Formula $Q_{2}$
+\end_inset
+
+ might be the set of all states of the machine,
+ i.e.,
+ all possible configurations of its memory and registers;
+ 
+\begin_inset Formula $f_{2}$
+\end_inset
+
+ might be the definition of single machine actions;
+ and 
+\begin_inset Formula $I_{2}$
+\end_inset
+
+ might be the set of initial states,
+ each including the program that determines the greatest common divisor as well as the particular values of 
+\begin_inset Formula $m$
+\end_inset
+
+ and 
+\begin_inset Formula $n$
+\end_inset
+
+.)
+\end_layout
+
+\begin_layout Standard
+Formulate a set-theoretic definition for the concept 
+\begin_inset Quotes eld
+\end_inset
+
+
+\begin_inset Formula $C_{2}$
+\end_inset
+
+ is a representation of 
+\begin_inset Formula $C_{1}$
+\end_inset
+
+
+\begin_inset Quotes erd
+\end_inset
+
+ or 
+\begin_inset Quotes eld
+\end_inset
+
+
+\begin_inset Formula $C_{2}$
+\end_inset
+
+ simulates 
+\begin_inset Formula $C_{1}$
+\end_inset
+
+
+\begin_inset Quotes erd
+\end_inset
+
+.
+ This is to mean intuitively that any computation sequence of 
+\begin_inset Formula $C_{1}$
+\end_inset
+
+ is mimicked by 
+\begin_inset Formula $C_{2}$
+\end_inset
+
+,
+ except that 
+\begin_inset Formula $C_{2}$
+\end_inset
+
+ might take more steps in which to do the computation and it might retain more information in its states.
+ (We thereby obtain a rigorous interpretation of the statement,
+ 
+\begin_inset Quotes eld
+\end_inset
+
+Program 
+\begin_inset Formula $X$
+\end_inset
+
+ is an implementation of Algorithm 
+\begin_inset Formula $Y$
+\end_inset
+
+.
+\begin_inset Quotes erd
+\end_inset
+
+)
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+We could state that 
+\begin_inset Formula $C_{2}$
+\end_inset
+
+ is a representation of 
+\begin_inset Formula $C_{1}$
+\end_inset
+
+ if there are functions 
+\begin_inset Formula $h:Q_{2}\to Q_{1}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $g:I_{1}\to I_{2}$
+\end_inset
+
+,
+ and 
+\begin_inset Formula $j:Q_{2}\to\mathbb{N}^{*}$
+\end_inset
+
+ such that 
+\begin_inset Formula $h\circ g=\text{Id}_{I_{1}}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\Omega_{2}=h^{-1}(\Omega_{1})$
+\end_inset
+
+,
+ and for all 
+\begin_inset Formula $q\in Q_{2}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $f_{1}(h(q))=h(f_{2}^{j(q)}(q))$
+\end_inset
+
+.
+\end_layout
+
+\end_body
+\end_document
-- 
cgit v1.2.3