はてなブックマーク

��� � � ��� � � ��� � � Áº ��� ���� ��� �� ������ ������� �������� ���������� � ��� ��� �! ¯ ¯ ¯ ¯ ¯ ¯ ¯ "� �� ��# ��$�% & ¯ '�&(� )�����# ��*$ ¯ �� ���� # �� �����# ���+& � ¯ ¯ ¯ ¯ ¯ � � ¯ ¯ ¯ � � � � � ������ � �,� ������ � � � �,� � � � � � � � )����� � � � �� ��� �� � �� ÁÁº ���� ��� �� -��� � ��� � ��� -������ � �- � � ���� � �. � � �-����� �� � � ���� � ���� � ���� � ���� ������� � �- � � ��

∗ I 2 1 2 2 2 3 3 4 5 5 7 6 8 II 11 1 11 2 12 3 13 4 14 5 15 6 — 16 ∗ 2002 8 5 8 2006 5 2007 8 Soto-Andrade Varela 1984 1 Part I 1 Russell, B.A.W., 1872-1970 ( ) X ∈ X X M 1 M M M ∈ M M M M M ∈ M M 2 Cantor, G., 1845-1918 1 X 2X X u t X m : 2X → X X R R = {m(A) | A ⊆ X, m(A) 6∈ A} m(R) R m(R) ∈ R R m(A) 6∈ A A ⊆ X m(R) = m(A) m R = A m(R) 6∈ R m(R) 6∈ R R m(R) ∈ R 1 M 2 1 1 ( ) 3 1 2 X X X XX X u

∗ 1 semantics of programming languages recursion ∗ 59 (2007), 180–191 1 2 2.1 fact(x) ≡ if x = 0 then 1 else x × fact(x−1) well-defined Z * Z Z * Z F : (Z * Z) → (Z * Z) F(f)(x) =      1 (x = 0) x × f(x − 1) (x 6= 0, f(x − 1) ) ( ) F F fact fact [[fact]] : Z * Z [[fact]](x) = ( x! (x ≥ 0) ( ) 2 F f [[fact]] F([[fact]])(x) =      1 (x = 0) x × y (x 6= 0, [[fact]](x−1) = y) ( ) = ( x! (x ≥

計算可能性、計算量、アルゴリズム Highly Recommended N.D. Jones, Computability and Complexity: From a Programming Perspective. MIT Press, 1997. ● 計算可能性と計算量について、プログラミング言語を基礎に置いて 平易かつ統一的に説明するのに成功している良書。 もちろん、部分計算など、Jonesならではの話題も充実。 （ただし誤植がかなり多いので注意 － 再版でかなり修正されるそうです） [ 所蔵図書館 ] （研究室にもあります） J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Second Edition. Addison-W