停机问题与悖论: 当逻辑凝视自身

小赖子的英国生活和资讯

作者 JustYY.com 小赖子的英国生活和资讯

2025年6月20日 02:34

上一个世纪的电脑

停机问题：程序能预测自己吗？

问题：给定程序 P 和输入 x，你能判断 P(x) 是否会停机，还是永远运行下去吗？

由阿兰·图灵于 1936 年提出
被证明为不可判定——不存在通用算法能解决所有情况
本质是自指问题：程序能分析另一个程序（甚至是自己）吗？

图灵的思想实验

假设：H(P, x) 判断 P(x) 是否停机

定义下面的Python函数：

def D(P):
    if H(P, P):
        while True: pass  # 无限循环
    else:
        return 0  # 停机

那 D(D) 会发生什么？

如果 D(D) 停机 → 它应该陷入死循环
如果 D(D) 死循环 → 它应该停机

逻辑中的类比：自指悖论

1. 理发师悖论

理发师为所有“不自己刮胡子”的人刮胡子
那理发师给自己刮吗？
造成矛盾 —— 和 D(D) 的情况完全相同

2. 说谎者悖论

"这句话是假的。"

如果是真的 → 它就是假的
如果是假的 → 它就是真的
纯粹的自指，导致真假互相循环

3. 罗素悖论（集合论）

R = { x | x 是集合且 x ∉ x }

R ∈ R 吗？
如果是 → 不应该在 R 中
如果不是 → 应该在 R 中

4. Grelling–Nelson 悖论

异描述词 = 不描述自身的形容词

“异描述词”是异描述词吗？
如果是 → 就不是；如果不是 → 就是

5. 哥德尔不完备性定理

"这句话无法被证明。"

如果能被证明 → 矛盾
如果不能证明 → 它是真的但系统无法证明
某些真理超出了系统本身的证明能力

6. Quine 程序

# Python 中的 Quine 示例
s = 's = {!r}\nprint(s.format(s))'
print(s.format(s))

输出自身源码的程序
体现了受控的自指结构

7. 决定性问题（Entscheidungsproblem）

希尔伯特问：是否存在一种通用方法判定一切数学命题的真假？
图灵与邱奇给出的答案：否
停机问题正是其不可判定性的关键依据

总结对照表

问题	领域	核心问题	结论
停机问题	计算机科学	程序是否能分析自身？	不可判定
理发师悖论	逻辑	自指导致矛盾	悖论
说谎者悖论	哲学	真假自指	悖论
罗素悖论	集合论	集合是否包含自身	矛盾
哥德尔定理	数学逻辑	不可证明真理	不完备
Quine 程序	编程	输出自身代码	可控自指

最后的思考

所有这些悖论都说明了：当一个系统试图描述自身时，往往会触及其极限
自指非常强大，但也极具风险
停机问题不仅是计算问题，更是逻辑深处的一面镜子

计算机科学

英文：The Halting Problem and Its Paradoxical Cousins: When Logic Looks at Itself

本文一共 691 个汉字, 你数一下对不对.

停机问题与悖论: 当逻辑凝视自身. (AMP 移动加速版本)

赞赏我的几个理由.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈

75a5a60b9cac61e5c8c71a96e17f2d9c 停机问题与悖论: 当逻辑凝视自身学习笔记算法计算机

The post 停机问题与悖论: 当逻辑凝视自身 first appeared on 小赖子的英国生活和资讯.

Bash 编程: 计算两个正整数的最大公约数/GCD

小赖子的英国生活和资讯

作者 JustYY.com 小赖子的英国生活和资讯

2025年6月19日 05:36

使用 Bash 脚本计算最大公约数（GCD）

什么是 GCD？

GCD 是 最大公约数（Greatest Common Divisor） 的缩写。
它是能同时整除两个整数的最大正整数。
例如：
- 8 和 12 的 GCD 是 4
- 14 和 49 的 GCD 是 7
GCD 常用于化简分数、密码算法以及数论中。

计算 GCD 的常见算法

1. 欧几里得算法

最常见且高效的算法。
基于这样一个原理：gcd(a, b) = gcd(b, a % b)
重复上述步骤直到 b 为 0，此时 a 即为最大公约数。

2. 减法法

不断用较大的数减去较小的数，直到两个数相等。
结果就是它们的 GCD。
相比欧几里得算法，这种方法在处理大数时效率较低。

3. 二进制 GCD 算法（Stein 算法）

使用位运算代替除法运算。
在某些硬件中更高效，因为避免了除法和取模操作。
基于以下规则：
- 若两个数都为偶数：gcd(a, b) = 2 * gcd(a/2, b/2)
- 若其中一个是偶数，则将其除以 2
- 若两个数都为奇数，且 a > b，则 gcd(a, b) = gcd((a - b)/2, b)

功能概述

该脚本计算两个数字的最大公约数（GCD）
确保输入参数是正整数
当输入缺失或无效时，提供用法说明

脚本功能解释

gcd() 函数： 使用循环和取模操作实现欧几里得算法。
参数个数检查： 确保用户传入了两个参数，否则提示用法并退出。
正则校验： 使用 Bash 正则判断两个输入是否为纯数字。
范围校验： 确保两个数字都大于零。
函数调用： 调用 gcd 函数并输出结果。

计算两正整数最大公约数GCD的BASH函数

以下是计算GCD的BASH代码。

#!/bin/bash

## 计算两个数的最大公约数

gcd() {
    local a=$1
    local b=$2

    while [ $b -ne 0 ]; do
        local temp=$b
        b=$((a % b))
        a=$temp
    done

    echo $a
}

# 检查是否传入了两个参数
if [ $# -ne 2 ]; then
    echo "用法: $0 <number1> <number2>"
    exit 1
fi

## 检查两个参数是否为正整数
if ! [[ $1 =~ ^[0-9]+$ ]] || ! [[ $2 =~ ^[0-9]+$ ]]; then
    echo "两个参数必须为正整数。"
    exit 1
fi
if [ $1 -le 0 ] || [ $2 -le 0 ]; then
    echo "两个参数都必须大于零。"
    exit 1
fi

# 调用 gcd 函数并打印结果
result=$(gcd "$1" "$2")
echo $result

输入校验流程

检查是否传入了两个参数
使用正则表达式确保输入为整数：=~ ^[0-9]+$
确保两个数都大于 0

使用示例

两个互质整数co-prime，它们的最大公约数为1。

命令	输出
`./gcd.sh 24 36`	`12`
`./gcd.sh 7 13`	`1`

小提示：

使用 chmod +x gcd.sh 让脚本可执行
然后运行：./gcd.sh 12 30

BASH小技巧

英文：Compute GCD in Bash with Input Validation

本文一共 599 个汉字, 你数一下对不对.

Bash 编程: 计算两个正整数的最大公约数/GCD. (AMP 移动加速版本)

赞赏我的几个理由.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈

75a5a60b9cac61e5c8c71a96e17f2d9c Bash 编程: 计算两个正整数的最大公约数/GCD BASH BASH 学习笔记数学程序设计算法计算机

The post Bash 编程: 计算两个正整数的最大公约数/GCD first appeared on 小赖子的英国生活和资讯.

比特币私钥的数学本质与人类算力的极限

小赖子的英国生活和资讯

作者 JustYY.com 小赖子的英国生活和资讯

2025年4月25日 02:56

Bitcoin

总是看到有一些暴力破解的程序在不停的尝试比特币钱包的密钥，还声称已经很幸运的试到了几个钱包的密钥，并且移走了里面的几万美金。

下面的文字是抄于 rssdao.eth 的朋友圈。

抛256次硬币，你就拥有一个比特币私钥：人类算力难以企及的加密奇迹

破解比特币需要40亿个银河系？普通人根本无法想象的数学深渊。

当你抛硬币正面朝上为1，反面朝上为0，连续抛256次，并把结果转换成一个16进制数，就是下一个比特币的密钥，那么换句话来说，比特币私钥的本质就是256位二进制数，听起来普普通通有没有，感觉用普通的计算机随便就能破解了？

能这么想的一般数学老师已经哭在了厕所，2的256次方，相当于8个2的32次方相乘，二的32次方约等于40亿，现在有概念了吗？就是40亿×40亿×40亿×40亿×40亿×40亿×40亿再除以40亿。量化一下吧，第一个40亿是现代电脑的GPU每秒可以计算10亿个哈希值，40亿就相当于一台非常好的电脑，每秒计算的哈希值。

第二个40亿用世界第一搜索引擎，谷歌公司作为例子，虽然谷歌没有对外公布服务器的数量，但有人估算大约在几百万个，是世界上最多服务器的企业之一，代表着地表最高算力，大部分谷歌服务器的算力都不如我们这些满载GPU的电脑强，那么40亿台电脑姑且约等于1000个谷歌算力。

第三个40亿全世界约有73亿人，我们假设地球一半以上的人每个人都有1000个谷歌的算力。再来看看第4个40亿，想象一下40亿个这样的地球像极了银河系有没有？姑且称为银河系算力。第5个40亿，我们把40亿个这样的银河系打包，算力之和每秒能计算出2的160次方。第6第7个40亿，我们从时间维度考量，40亿秒约等于126.8年，乘以40亿倍，就是5070亿年，差不多是目前我们已知的宇宙年龄的37倍。

最后我们得出了结论，以人类现在的文明程度要解开比特币的密钥，大约需要40亿个银河系的算力，计算37倍于宇宙的年龄一样长的时间，才有1/(40亿^8)可以算出密钥的可能。所以现阶段人类科技而言，要通过技术手段破解密钥，简直就是痴人说梦了，这种体量的计算连量子计算机串联也望尘莫及。

2021年2月旧文，再思考一下比特币的伟大发明。

今天一个大饼的价格是9.2万美金。