可計算函數 pdf epub mobi txt 電子書下載 2025

簡體網頁||繁體網頁

☆☆☆☆☆

[俄羅斯] 瀋（A.Shen），[俄羅斯] 韋列夏金（N.K.Vereshchagin）著，陳光還譯

圖書標籤:

可計算性理論
遞歸論
圖靈機
lambda演算
形式語言
算法
計算復雜性
數學邏輯
理論計算機科學
程序設計語言

下載連結在頁面底部

facebook linkedin mastodon messenger pinterest reddit telegram twitter viber vkontakte whatsapp 複製連結

想要找書就要到新城書站

book.cndgn.com

立刻按 ctrl+D收藏本頁

你會得到大驚喜!!

齣版社：高等教育齣版社

ISBN：9787040386929

版次：1

商品編碼：11398662

包裝：平裝

叢書名：大學生數學圖書館

開本：32開

齣版時間：2014-01-01

用紙：膠版紙

頁數：159

字數：140000

正文語種：中文

具體描述

內容簡介

　　這本生動、簡潔的書基於作者在莫斯科大學力學數學係的本科生課程講義，涵蓋瞭計算的一般理論的基本概念。《可計算函數》從可計算函數的定義和一個算法開始，討論瞭可判定性、可數性、通用函數、編號係統及其性質、m-完全性、不動點定理、算術分層、oracle計算、不可判定性的度。作者還介紹瞭一些特殊的函數模型，如Turing機和遞歸函數。
　　《可計算函數》可供數學和計算機專業的本科生閱讀，也可供所有希望學習計算的一般理論的基礎知識的數學傢和程序員使用。

內頁插圖

《大學生數學圖書館》叢書序
引言

第一章可計算函數、可判定集與可數集
1.可計算函數
2.可判定集
3.可數集
4.可數集與可判定集
5.可數性與可計算性

第二章通用函數與不可判定性
1.通用函數
2.對角構造
3.可數的不可判定集
4.可數的不可分集
5.單集：Post構造

第三章編號與運算
1.Godel通用函數
2.可計算函數的可計算序列
3.Godel通用集

第四章 Godel編號係統的性質
1.編號集
2.舊函數的新編號
3.Godel編號係統的同構
4.函數的可數性

第五章不動點定理
1.不動點與等價關係
2.打印程序文本的程序
3.係統的技巧：另一個證明
4.幾點附注

第六章 m-可約性與可數集的性質
1.m-可約性
2.m-完全集
3.m-完全性與有效不可數性
4.m-完全集的同構
5.産生集
6.不可分集的對

第七章 Oracle計算
1.Oracle機
2.相對可計算性：等價描述
3.相對化
4.0'-計算
5.不可比集
6.Friedberg-Muchnik定理：構造的一般方案
7.Friedberg-Muchnik定理：勝齣條件
……
第八章算術分層
第九章 Turing機
第十章可計算函數的算術化
第十一章遞歸函數
參考文獻
人名錶
索引

精彩書摘

　　Turing機可以計算什麼樣的函數呢？根據Turing論點，任何可計算函數都是Turing可計算的。自然地，這句話的含義依賴於對術語“可計算函數”的理解。如果是按照模糊的直覺意義來理解f就像“一個函數可被算法地求值”即“由完全清晰的規則”或某些類似的東西），那麼Turing論點的嚴格證明當然是不可能的。我們能說的隻有一件事，從Euclid到Knuth的許多世紀以來從未遇到過一個算法不能轉譯為Turing機程序的，然而，下麵我們還是要給齣一個論證（雖然不太有說服力）。如果把Turing論點中的“可計算”當成“用Pascal程序可計算”，並且設想Pascal程序的語法和語義都定義好瞭，那麼Turing論點就是一個可證明成立或不成立的明確的命題瞭。當然這樣的證明必須建立在Pascal的語法和語義的形式化描述之上，而這從來沒有人做過，然而，這類證明的簡化的計算模型實際上曾經給齣過，它們近似於冗長程序的正確性證明，很少人願意去寫，更少人願意去讀它。
　　最後，我們來介紹上麵提到的支持任何可計算函數的Turing機可計算性的非形式化論證，假設你（或者任何其他人）能對給定的變量計算某個函數f.我們來描述模擬你的工作的Turing機。
　　你自然要用紙和鉛筆（連同橡皮擦），因為能記住的信息總量是很有限的，假設你寫在同樣大小的紙頁上：有兩堆紙頁，分彆放在你當前頁的兩邊；在當前頁做完後，可以把它放到其中一堆上，再從另一堆頂上取下一個工作頁。
　　……