Số Graham – Wikipedia Tiếng Việt

Số Graham (tiếng Anh: Graham's Number) là một con số khổng lồ phát sinh như giới hạn trên cho câu trả lời của một vấn đề trong lĩnh vực toán học của lý thuyết Ramsey. Nó được đặt theo tên nhà toán học Ramsey, người đã sử dụng số này trong các cuộc trò chuyện với nhà văn khoa học phổ thông nổi tiếng Martin Gardner như một lời giải thích đơn giản về các giới hạn trên của vấn đề mà ông đang làm việc. Năm 1977, Gardner đã mô tả số này trong tạp chí Scientific American, giới thiệu nó với công chúng. Tại thời điểm giới thiệu, nó là số nguyên dương cụ thể lớn nhất từng được sử dụng trong một bằng chứng toán học được công bố. Con số được công bố trong Sách kỷ lục Guinness thế giới năm 1980, thêm vào sự quan tâm phổ biến của nó. Các số nguyên cụ thể khác (như TREE (3)) được biết là lớn hơn nhiều so với số Graham đã xuất hiện trong nhiều bằng chứng toán học quan trọng, ví dụ liên quan đến các dạng hữu hạn khác nhau của Harvey Friedman trong định lý Kruskal. Ngoài ra, các giới hạn trên nhỏ hơn về vấn đề lý thuyết Ramsey mà từ đó số xuất phát của Graham đã được chứng minh là hợp lệ.

Số Graham lớn hơn nhiều so với nhiều số lớn khác như số Skewes và số Moser, cả hai đều lần lượt lớn hơn nhiều so với googolplex. Như với những cái này, nó lớn đến mức vũ trụ quan sát được quá nhỏ để chứa một đại diện kỹ thuật số thông thường của số Graham, giả sử rằng mỗi chữ số chiếm một thể tích Planck, có thể là không gian đo được nhỏ nhất. Nhưng ngay cả số lượng chữ số trong biểu diễn số này của số Graham cũng sẽ là một con số lớn đến mức đại diện kỹ thuật số của nó không thể được biểu diễn trong vũ trụ quan sát được. Thậm chí số lượng chữ số của số đó cũng không thể, v.v., trong một số lần vượt xa tổng số khối lượng Planck trong vũ trụ quan sát được. Do đó, số Graham không thể được biểu thị ngay cả bởi các tháp mũ có dạng a b c ⋅ ⋅ ⋅ {\displaystyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}} .

Tuy nhiên, số Graham có thể được cung cấp rõ ràng bằng các công thức đệ quy có thể tính toán bằng cách sử dụng ký hiệu mũi tên lên Knuth hoặc tương đương, như đã được thực hiện bởi Graham. Vì có một công thức đệ quy để định nghĩa nó, nó nhỏ hơn nhiều so với các số Busy Beaver điển hình. Mặc dù quá lớn để được tính toán đầy đủ, chuỗi các chữ số của Graham có thể được tính toán rõ ràng thông qua các thuật toán đơn giản. 12 chữ số cuối cùng là ... 262464195387. Với Ký hiệu mũi tên lên Knuth, số Graham là g 64 {\displaystyle g_{64}} , trong đó

g n = { 3 ↑↑↑↑ 3 , n = 1 3 ↑ g n − 1 3 , n ≥ 2 , n ∈ N {\displaystyle g_{n}=\left\{{\begin{matrix}3\uparrow \uparrow \uparrow \uparrow 3,&n=1\\3\uparrow ^{g_{n-1}}3,&n\geq 2,n\in \mathbb {N} \end{matrix}}\right.}

Định nghĩa số Graham và tổng quát

Định nghĩa số Graham : g 64 = 64 { 3 ↑↑↑↑↑ . . . . . . ↑↑ 3 ⏟ 3 ↑↑↑↑↑↑ . . . . . . . ↑↑ 3 ⏟ 3 ↑↑↑ . . . . . ↑ 3 ⏟ . . . . . ⏟ 3 ↑↑ . . . . . . ↑ 3 ⏟ 3 ↑↑↑↑ 3 {\displaystyle g_{64}=64{\begin{cases}\underbrace {\underbrace {\underbrace {\underbrace {\underbrace {3\uparrow \uparrow \uparrow \uparrow \uparrow ......\uparrow \uparrow 3} _{3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow .......\uparrow \uparrow 3}} _{3\uparrow \uparrow \uparrow .....\uparrow 3}} _{.....}} _{3\uparrow \uparrow ......\uparrow 3}} _{3\uparrow \uparrow \uparrow \uparrow 3}\end{cases}}} Tóm lại với n là số nguyên dương ta có  : g n = n { 3 ↑↑↑↑↑ . . . . . . ↑↑ 3 ⏟ 3 ↑↑↑↑↑↑ . . . . . . . ↑↑ 3 ⏟ 3 ↑↑↑ . . . . . ↑ 3 ⏟ . . . . . ⏟ 3 ↑↑ . . . . . . ↑ 3 ⏟ 3 ↑↑↑↑ 3 {\displaystyle g_{n}=n{\begin{cases}\underbrace {\underbrace {\underbrace {\underbrace {\underbrace {3\uparrow \uparrow \uparrow \uparrow \uparrow ......\uparrow \uparrow 3} _{3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow .......\uparrow \uparrow 3}} _{3\uparrow \uparrow \uparrow .....\uparrow 3}} _{.....}} _{3\uparrow \uparrow ......\uparrow 3}} _{3\uparrow \uparrow \uparrow \uparrow 3}\end{cases}}} , trong đó 3 ↑↑↑↑ 3 = 3 3 3 { 3 3 3 3 3 3 3 . . . . . 3 ⏟ 3 3 3 3 3 3 3 . . . . . 3 ⏟ . . . . . . ⏟ 3 3 3 3 3 3 3 . . . . . 3 ⏟ 3 3 3 {\displaystyle 3\uparrow \uparrow \uparrow \uparrow 3=3^{3^{3}}{\begin{cases}\underbrace {\underbrace {\underbrace {\underbrace {3^{3^{3^{3^{3^{3^{3^{.....^{3}}}}}}}}} _{3^{3^{3^{3^{3^{3^{3^{.....^{3}}}}}}}}}} _{......}} _{3^{3^{3^{3^{3^{3^{3^{.....^{3}}}}}}}}}} _{3^{3^{3}}}\end{cases}}} hay g n = 3 ↑↑↑↑↑↑ . . . . . . . . ↑↑↑ 3 ⏟ g n − 1 {\displaystyle g_{n}=\underbrace {3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow ........\uparrow \uparrow \uparrow 3} _{g_{n-1}}} hoặc g n = { 3 ↑↑↑↑ 3 , n = 1 3 ↑ g n − 1 3 , n ≥ 2 , n ∈ N {\displaystyle g_{n}=\left\{{\begin{matrix}3\uparrow \uparrow \uparrow \uparrow 3,&n=1\\3\uparrow ^{g_{n-1}}3,&n\geq 2,n\in \mathbb {N} \end{matrix}}\right.}

Tham khảo