2 (p0-1): 第一章抽象算法族与算法族可计算性 2 (p0-2): §1.1函数与算法 2 (p0-3): 1.1.1函数 2 (p0-4): 目录 5 (p0-5): 1.1.2算法及其分类 7 (p0-6): 1.1.3抽象算法族 10 (p0-7): 练习1.1 12 (p0-8): §1.2抽象算法族的基本性质 12 (p0-9): 1.2.1基础函数性质(BFP) 12 (p0-10): 1.2.2复合函数性质(CFP) 14 (p0-11): 1.2.3通用函数性质(UFP) 17 (p0-12): 1.2.4判定函数性质(DFP) 20 (p0-13): 1.2.5标号函数性质(IFP) 23 (p0-14): 练习1.2 26 (p0-15): 1.3.1标准算法族 26 (p0-16): 1.3.2标准算法族的固有局限性 26 (p0-17): §1.3标准算法族可计算性 30 (p0-18): 1.3.3标准算法族的计算能力 36 (p0-19): 练习1.3 39 (p0-20): 第二章 程序算法族及其可计算性 39 (p0-21): §2.1程序语言? 44 (p0-22): 练习2.1 45 (p0-23): §2.2 ?语言程序算法族可计算性 45 (p0-24): 2.2.1程序算法族可计算性的形式描述 48 (p0-25): 2.2.2初等函数与初等谓词是?程序可计算的 57 (p0-26): 2.2.3配对函数及程序编码 63 (p0-27): 2.2.4通用程序与标号计算程序 71 (p0-28): 练习2.2 73 (p0-29): 第三章Turing机与Turing可计算性 73 (p0-30): §3.1什么是Turing机 73 (p0-31): 3.1.1基本Turing机 80 (p0-32): 3.1.2基本Turing机实例 87 (p0-33): 3.1.3 Turing机的复合 89 (p0-34): 练习3.1 91 (p0-35): §3.2其他种类的Turing机 92 (p0-36): 3.2.1多道机以及其他的Turing机推广形式 95 (p0-37): 3.2.2单边机以及其他的Turing机限制形式 99 (p0-38): 练习3.2 100 (p0-39): §3.3通用Turing机 101 (p0-40): 3.3.1机和带的描述 104 (p0-41): 3.3.2通用机的构成 107 (p0-42): 练习3.3 108 (p0-43): 3.4.1 Turing机及其可计算性的形式描述 108 (p0-44): §3.4 Turing机族及其可计算性 112 (p0-45): 3.4.2 Turing机标号 114 (p0-46): 3.4.3 Turing机族 116 (p0-47): 3.4.4计算通用函数的Turing机 118 (p0-48): 3.4.5计算标号函数的Turing机 119 (p0-49): 练习3.4 120 (p0-50): §3.5Turing机族的计算功能及局限性 120 (p0-51): 3.5.1停机函数 122 (p0-52): 3.5.2标号计算函数 123 (p0-53): 3.5.3全性函数和等价性函数 125 (p0-54): 3.5.4递归定理 126 (p0-55): 练习3.5 129 (p0-56): 第四章原始递归函数 129 (p0-57): §4.1初等函数集的不足 131 (p0-58): 练习4.1 132 (p0-59): §4.2原始递归函数集 132 (p0-60): 4.2.1原始递归式 135 (p0-61): 4.2.2原始递归函数集 138 (p0-62): 练习4.2 140 (p0-63): §4.3可以化为原始递归式的其他递归式 140 (p0-64): 4.3.1联立递归式 143 (p0-65): 4.3.2串值递归式 146 (p0-66): 练习4.3 148 (p0-67): §4.4原始递归谓词 149...

zlibzh/no-category/王元元著/可计算性引论_117145737.pdf

Southeast University Press

China, People's Republic, China

Bookmarks: p0-1 (p2): 第一章抽象算法族与算法族可计算性
p0-2 (p2): §1.1函数与算法
p0-3 (p2): 1.1.1函数
p0-4 (p2): 目录
p0-5 (p5): 1.1.2算法及其分类
p0-6 (p7): 1.1.3抽象算法族
p0-7 (p10): 练习1.1
p0-8 (p12): §1.2抽象算法族的基本性质
p0-9 (p12): 1.2.1基础函数性质（BFP）
p0-10 (p12): 1.2.2复合函数性质（CFP）
p0-11 (p14): 1.2.3通用函数性质（UFP）
p0-12 (p17): 1.2.4判定函数性质（DFP）
p0-13 (p20): 1.2.5标号函数性质（IFP）
p0-14 (p23): 练习1.2
p0-15 (p26): 1.3.1标准算法族
p0-16 (p26): 1.3.2标准算法族的固有局限性
p0-17 (p26): §1.3标准算法族可计算性
p0-18 (p30): 1.3.3标准算法族的计算能力
p0-19 (p36): 练习1.3
p0-20 (p39): 第二章 程序算法族及其可计算性
p0-21 (p39): §2.1程序语言？
p0-22 (p44): 练习2.1
p0-23 (p45): §2.2 ？语言程序算法族可计算性
p0-24 (p45): 2.2.1程序算法族可计算性的形式描述
p0-25 (p48): 2.2.2初等函数与初等谓词是？程序可计算的
p0-26 (p57): 2.2.3配对函数及程序编码
p0-27 (p63): 2.2.4通用程序与标号计算程序
p0-28 (p71): 练习2.2
p0-29 (p73): 第三章Turing机与Turing可计算性
p0-30 (p73): §3.1什么是Turing机
p0-31 (p73): 3.1.1基本Turing机
p0-32 (p80): 3.1.2基本Turing机实例
p0-33 (p87): 3.1.3 Turing机的复合
p0-34 (p89): 练习3.1
p0-35 (p91): §3.2其他种类的Turing机
p0-36 (p92): 3.2.1多道机以及其他的Turing机推广形式
p0-37 (p95): 3.2.2单边机以及其他的Turing机限制形式
p0-38 (p99): 练习3.2
p0-39 (p100): §3.3通用Turing机
p0-40 (p101): 3.3.1机和带的描述
p0-41 (p104): 3.3.2通用机的构成
p0-42 (p107): 练习3.3
p0-43 (p108): 3.4.1 Turing机及其可计算性的形式描述
p0-44 (p108): §3.4 Turing机族及其可计算性
p0-45 (p112): 3.4.2 Turing机标号
p0-46 (p114): 3.4.3 Turing机族
p0-47 (p116): 3.4.4计算通用函数的Turing机
p0-48 (p118): 3.4.5计算标号函数的Turing机
p0-49 (p119): 练习3.4
p0-50 (p120): §3.5Turing机族的计算功能及局限性
p0-51 (p120): 3.5.1停机函数
p0-52 (p122): 3.5.2标号计算函数
p0-53 (p123): 3.5.3全性函数和等价性函数
p0-54 (p125): 3.5.4递归定理
p0-55 (p126): 练习3.5
p0-56 (p129): 第四章原始递归函数
p0-57 (p129): §4.1初等函数集的不足
p0-58 (p131): 练习4.1
p0-59 (p132): §4.2原始递归函数集
p0-60 (p132): 4.2.1原始递归式
p0-61 (p135): 4.2.2原始递归函数集
p0-62 (p138): 练习4.2
p0-63 (p140): §4.3可以化为原始递归式的其他递归式
p0-64 (p140): 4.3.1联立递归式
p0-65 (p143): 4.3.2串值递归式
p0-66 (p146): 练习4.3
p0-67 (p148): §4.4原始递归谓词
p0-68 (p149): §4.5 Loop程序与原始递归函数
p0-69 (p155): 练习4.5
p0-70 (p156): §5.1 Ackerman函数
p0-71 (p156): 5.1.1 Ackerman函数及基本性质
p0-72 (p156): 第五章递归函数
p0-73 (p159): 5.1.2 Ackerman函数的非原始递归性
p0-74 (p163): 练习5.1
p0-75 (p164): §5.2μ-递归函数
p0-76 (p165): 5.2.1μ-递归函数及其可计算性
p0-77 (p167): 5.2.2 Ackerman函数的μ-递归性
p0-78 (p173): 5.2.3 Turing可计算函数的μ-递归性
p0-79 (p177): 练习5.2
p0-80 (p179): 5.3.1一般递归式及递归函数集
p0-81 (p179): §5.3递归函数集
p0-82 (p181): 5.3.2递归函数的可计算性
p0-83 (p182): 5.3.3μ-递归函数的递归性
p0-84 (p186): 练习5.3
p0-85 (p186): §5.4 Church-Turing论题
p0-86 (p186): 5.4.1 Church-Turing论题
p0-87 (p188): 5.4.2递归函数集是最小的标准算法族
p0-88 (p188): 可计算函数集
p0-89 (p191): 练习5.4
p0-90 (p193): 第六章字函数及其可计算性
p0-91 (p193): §6.1∑*与∑*上的字函数
p0-92 (p194): 6.1.1∑*上的原始递归字函数
p0-93 (p198): 6.1.2∑*上的μ-递归字函数（递归字函数）
p0-94 (p201): 练习6.1
p0-95 (p201): §6.2无零K进制与字的数表示
p0-96 (p203): 6.2.1无零k进制与K进制的换算是
p0-97 (p203): 原始递归可计算的
p0-98 (p204): 6.2.2几个重要字函数的数论函数表示形式
p0-99 (p206): 练习6.2
p0-100 (p206): §6.3∑*上字函数的可计算性讨论
p0-101 (p206): 6.3.1程序语言？n
p0-102 (p213): 6.3.2∑*上递归字函数的可计算性
p0-103 (p213): 练习6.3
p0-104 (p214): 第七章形式语言与自动机
p0-105 (p214): §7.1形式语言的生成与识别
p0-106 (p214): 7.1.1形式语言的生成
p0-107 (p217): 7.1.2形式语言的识别
p0-108 (p219): 练习7.1
p0-109 (p219): §7.2正规语言和有穷自动机
p0-110 (p219): 7.2.1 正规文法与正规语言
p0-111 (p224): 7.2.2有穷自动机
p0-112 (p226): 7.2.3有穷自动机与正规语言
p0-113 (p232): 练习7.2
p0-114 (p233): §7.3正规语言的性质及正规表达式
p0-115 (p233): 7.3.1正规语言的封闭特性
p0-116 (p238): 7.3.2正规表达式
p0-117 (p241): 7.3.3 Pumping引理及其应用
p0-118 (p243): 练习7.3
p0-119 (p244): §7.4 上下文无关语言
p0-120 (p244): 7.4.1上下文无关文法及上下文无关语言
p0-121 (p246): 7.4.2文法树和导出树
p0-122 (p249): 7.4.3 Chomsky标准形、Pumping引理及
p0-123 (p249): 其他特性
p0-124 (p254): 练习7.4
p0-125 (p255): §7.5下推自动机
p0-126 (p259): 练习7.5
p0-127 (p259): §7.6形式语言的Chomsky分层
p0-128 (p259): 7.6.1上下文有关语言
p0-129 (p263): 7.6.2递归枚举语言
p0-130 (p266): 7.6.3 Chomsky分层
p0-131 (p267): 练习7.6
p0-132 (p268): 第八章递归集、递归枚举集和判定问题
p0-133 (p268): §8.1递归集和递归枚举集
p0-134 (p269): 8.1.1递归集和递归枚举集
p0-135 (p279): 8.1.2递归关系和递归枚举关系
p0-136 (p288): 练习8.1
p0-137 (p289): §8.2判定问题
p0-138 (p292): 8.2.1判定问题求解的常用定理及方法
p0-139 (p297): 8.2.2 Post对应问题
p0-140 (p303): 8.2.3形式语言中的判定问题
p0-141 (p307): 8.2.4其他判定问题简介
p0-142 (p314): 练习8.2
p0-143 (p316): 参考文献

related_files:
filepath:10832538.zip — md5:c85953914a69059ebb982703efece1f4 — filesize:15803332
filepath:10832538.zip — md5:4b4a40f94hf29e7eeecfa4933233eaec — filesize:15803332
filepath:/读秀/读秀3.0/读秀/3.0/3.0新/其余书库等多个文件/0107/15/10832538.zip
filepath:/读秀/读秀4.0/读秀/4.0/数据库06-3/10832538.zip
filepath:第八部分/QQQQQQQ/15/01/10832538.zip

2024-06-13