可計算性和複雜性/可計算性
此頁面需要開發。
可計算性理論是計算機科學的一個分支，它關注確定某個問題是否可解。問題可以被認為是非常基本的情況或問題。
在當今時代，我們被先進的計算機包圍著，這些計算機以令人眼花繚亂的速度工作；很容易假設，只要有足夠的記憶體或處理能力，計算機就可以計算任何問題。然而，透過數學，我們可以證明有些問題根本沒有明確的解決方案。例如：當給出問題“π的最後一位數字是什麼？”時，不可能找到解決方案，因為π是無限長的。
在衡量計算解決方案的“難度”時，“自動機理論”的概念對於計算和理解問題都很有幫助。自動機理論將在本書的後面進一步介紹——它是理解複雜性的核心組成部分。
在發現什麼可能是或可能不是可計算的時，構建表達我們計算背後的邏輯的模型是有幫助的——實際上，也許是必要的。模型允許我們精確地規劃出問題是如何解決的，並允許我們檢查過程的每個步驟。
自動機是一種模型，我們可以將它們視為一種機器，它表示一個問題（例如 2 + 2 是多少），然後在給定一些輸入（4）時，執行一系列步驟，並要麼接受輸入為有效，要麼拒絕它。這個想法（輸入是否匹配給定的約束？）非常強大——並且當順序使用時，可以解決所有可計算的問題。
自動機理論受到功能主義哲學運動的影響。功能主義者不是將數學視為利用數字進而表示值，而是更喜歡將數字視為僅僅是透過各種規則進行操作的符號。當我們檢查自動機時，你會看到許多字母而不是數字——這是因為我們將字母視為符號，它們本身沒有內在的重要性，只是由我們提供的規則進行操作。隨著你對自動機的工作越來越熟悉，這個概念將變得更有意義。
*d.png)
右側顯示的圖片是一個自動機的例子。如果輸入匹配約束 a(bc)*d（一個'a' 後跟任意數量的'bc'，然後是一個'd'），它就會接受——也就是返回'true'。
讓我們檢查一下這張圖片。每個圓圈稱為一個狀態，每個狀態都給定一個名稱 qN，其中 n 是識別號。如果我們將自動機想象成代表我們自己的心算，我們可以將每個狀態視為我們邏輯思維模式的哪個步驟。指向不同圓圈的箭頭稱為“轉換”，如果滿足某些條件，則從一個狀態到另一個狀態。根據你正在使用的自動機的型別，這些條件可能會有所不同。在給定的示例中，唯一的約束是我們的模型在當前正在檢查的輸入的點處看到指定的字元。
對於 a(bc)*d，我們首先應該檢查輸入的開頭是否包含一個'a'。如果我們看到一個 a，我們就進入第二個狀態。……