一、引言
有窮與無窮問題在邏輯與數學帶有根本性質，在計算機科學中也是主要問題。在計算機科學看來耍在“仟意人的有窮”和“可行的有窮”之間。
數學中的經典數學是采用非直謂主義的觀點的，直覺主義數學則是采用直謂主義觀點。“有窮主義”是數學基礎中的學派提出的，主張在數學基礎中，不能允許假定有無窮的步驟。至於直謂主義則是本世紀五十年代以來，集合論中的一個流派。
二、經典數學與構造主義數學
構造主義數學（亦稱“直覺主義數學”）產生於本世紀初年。19世紀70年代以無窮集合為研究對象的集合論產生以後，有些重要的數學家對這種新數學是表示懷疑的，反對得特別厲害。到了上一個世紀末，集合論已為大多數數學家所接受。但本世紀初，集合論中發現了“悖論”，於是出現了危機。最有名的“悖論”是英國邏輯學家和哲學家在1902年發現的。這一“悖論”後來被稱作“悖論”。這一“悖論”是說：就一個包括一切不包括自身作為元素集合的集合而言，這個集合根據定義既不能不包含自身，又不能包含自身。
為了避免這一類“棒論”，提出了“排除惡性循環的法則”，根據這一法則，一個集合不能包含它本身作為元素，這樣，悖論就可以避免，荷蘭數學家提出了另一種避免“悖論”的方案，這就是直覺主義。這種觀點認為數學產生於人的直覺（這就是“直覺主義”名稱的由來），和不承認實無窮的存在，因而認為邏輯中的《排中律》隻對於有窮集合有效。直覺主義主要有兩個觀點，即數學產生於直覺，數學的構造性。後來的構造主義隻強調後者。近年來有些計算機科學家認為構造主義對計算機科學有用，特別是對程序自一個集合定義稱作非直謂的，如果定義中包含有這個集合所屬的類，否則稱作直謂的。動生成可能有。這一問題我們介下麵還要談判。
考慮長的不可概觀的邏輯證明，隻是說明這一技巧(這是由幾何學的證明產生的技巧可能失敗，因而新的技巧是必須的。
“證明必須是可概觀的，這就是說我們必須注意重複一個證明和重複一個實驗之間的區別。重複一個證明的意思不是重現產生一個特定結果的條件，而是重複每一步和那個結果。雖然這說明證明必須是能夠完全地自動地加以重現的，這種重現必須包含有證明的力量，這種力量迫使人們必須承認這一結果”。
所說的計算與證明的“可概觀性”是和我們在計算機科學中所討論的“可行性”是非常相近的。
目前在計算機科學中我們暫時接受了叩-論題，認為一項計算是可行的，當且僅當它是在計算機上多項式時間內可計算的：所說的“多項式時間內可計算”是指，一項計算相對於輸入長度而言的計算時間（即計算步數）的增長率是多項式的。
近年來有些有關的研究工作者對這一論題提出懷疑意見。他們認為對這個論題是能夠提出反證的，因為在直觀上，如果有關的多項式次數較高（比如說父)，很難說這種計算是可行的。
此外，近幾年已發現：通常按“最壞情形”計算複雜未必合理。因為有人作過實驗。就線性規劃的解題算法而言，在“最壞情形”時單純形法的複雜性為指數的，“橢球算法”（即蘇聯哈赤揚在1979年時提出的算法）的複雜性為多項式的。而就一個有3000個未知數的實例而言，在一台每秒能執行三百萬條指令的計算機上，前者需要的計算時間為30分鍾而後者估計為上千萬年這是因為單純形法的複雜性就“平均情形”而言是的多項式。因之現在有些學者認為應該考慮平均情形的複雜性。
還有，關於複雜性的函數般是以輸人長度為變量的。但近幾年已發現，算法的複雜性可以有最近有人證明：就哈亦揚法的複雜性而言，如果以輸入長度為變量，它的複雜件函數楚多項式的，如果自然參數等式數為變覺則它的複雜性函數是指數的。而最近還有人證明：就線性規劃而言，如果維數是固定的，則存在著線性算法規劃是線性的。
計算機科學中的形式概念及與其相對應的直觀概念
邏輯中的“形式刻畫”
此後，各種各樣的形式化邏輯理論相繼問世，其中也包括直覺主義邏輯的形式化理論。所謂直覺主義邏輯指的是這樣一種邏輯，它主張對無窮集合使用排中律是無效的，因而用反證法做出的證明也是無效的。這種邏輯也稱為構造性邏輯，它對計算機科學有用。