1/2的所有正整數冪之和是「可計算的」嗎？

01-04

最近看到了停機問題。但是對於1/2+1/4+1/8+……這個級數，如果一個個加，肯定加不完。但是我們完全可以算出最終等於1 。這算什麼呢？

一個個加的確算不完。但是證明這個問題的解是正確的，一個個加上去並不是唯一的方法。

感覺大家跑偏了啊。

回答題主，當然可計算啦。

def f = 1

你看我就寫出來了計算 $frac{1}{2}$ 的所有正整數冪之和的演算法，而且我還可以證明這個演算法是正確的。

題主這樣理解「可計算性」是不行的。

程序是需要有輸入的，對於一個特定輸入的問題，問它是否可計算，特別是當我們知道它的結果時，這沒有意義。

停機問題是判斷任意一個程序是否會在有限的時間之內結束運行的問題。它是有輸入的，你需要針對任意的輸入程序和對應的數據，判斷是否能停機。

對於結果未知的問題，我們倒是可以問這樣的問題。比如：判斷 Collatz 猜想的正確性是可計算的嗎？

很簡單，任給一個比1小的實數a，我總能通過有限步加法運算算到a和1之間，而我無論算多少步也不會比1大，所以結果就是1。

題主大概是沒理解分析語言的那種美感……

如果你追一個烏龜，你比烏龜快，一開始烏龜在你前面x米，要追到它，你要先跑到它的位置，這時候它已經往前走了y米，然後你又要跑到它的新位置，這時候它又往前跑了z米。。。

但這並不能證明你追不上，而是你的計算方法和思路有問題

具體到是否可計算，大體上說，「不可計算問題」是指」不可能給出一個演算法來解決這個問題的所有形式「，而不是」存在一個看似正確但無法完成的演算法「（其實無法完成的過程不應該稱之為演算法吧），要分清any、all、exist等詞在邏輯上的含義，所以離散數學的命題相關章節很重要呀

對於一種方法不能得出結果的問題，我們人類通常會換個角度，換個方法去解決。

除非是撞了南牆這還要往前懟的愣頭青

省略號只是幫助理解。考慮我們想驗證它確實是1，數學上其實在說這麼一件事 $lim _{n o infty} sum _{i=1} ^{n} frac 1 {2^i}=1$

按照定義，就是 $forall epsilon > 0 .exists N in mathbb N . forall n > N . left | sum _{i=1} ^{n} frac 1 {2^i}-1<br /> ight |<epsilon$

通俗講：你先說想要多接近，我總能給你一個N，你只要至少取前N項加起來，就能有這麼接近1。只要你給定接近要求，取了n，那麼和式當然式有限項，可計算。

這個等式實際上是一個包含全稱量詞的命題，你沒法基於值來一個個驗證，需要符號運算實現證明。

類比一下，你要如何用圖靈機證明 $forall n in mathbb N.n<n+1$ 呢？

「1/2的所有正整數冪之和」的定義並不是真的求無窮多個數的和（否則真的不可計算），而是一個數y，使得對於任意正數m，都存在t，使得對任意正整數x&>t有|(1/2)^1+(1/2)^2+...+(1/2)^x-y|&(1/2)^1+(1/2)^2+...+(1/2)^x是可計算的，它等於1-(1/2)^x。y也是可計算的，它等於1。

同學，我們只有在處理有限項運算的時候才會用「數數」的方法研究，因為那是我們力所能及的，但是對於無限，我們力所不能及，就只能通過邏輯來研究，比如為什麼自然數是無窮多個？數不完並不是一個完美的回答，其實因為自然數有後繼性，也就是如果n是自然數，那麼n+1也是，這就完成自然數沒有最大的，也就有無窮多個了。回到正題，那麼無窮項和怎麼「算」呢？其實用到我們處理無窮的另一種方式，就是極限，極限是我們把思維過度到無限的一個最好的思維方式，因為前n項和我們是能算的，那麼讓這個n趨向於無窮，就會得到無窮項的和。也就是通過逐項相加已經不行，而是通過極限邏輯構造的。

極限是精確的，不是近似的，它就是1

班門弄斧，計算機和人一樣，只能做有限的運算，但不同的是，對於無限的運算，人類卻可以理解證明，對無限進行預測。

這跟停機問題並沒有什麼關係

對於有理數等比級數的情況是可計算的，只要計算極限就行了，這個partial recursive function是在收斂的情況下有良好定義在不收斂時undefined

無理數的情況是無法計算的，首先就沒法把無理數輸入encode成一個自然數

演算法的有限性（時間和空間上的）已經限制了其前往現代數學大門的步伐，因為現代的數學尤其是分析學是建立在以連續和無窮為基礎上的微積分思想之上的，而計算機的邏輯原理是建立在0與1的離散值的排列組合之上的，你以為計算機在運算與思考，它其實只是在按照設定的程序規則通過顯示器或其它物理設備在解釋一串0與1罷了（這些意義是人賦予的，如ASCII表），所以這也就是為什麼計算機系的同學一般要學離散數學的原因。還有一點就是無限是個過程而不是值，如果你允許計算機進行無限時間的計算的話，它的值確實是1。因為在數學中用比較嚴格的說法就是對於任意小的正數ε，存在一個時間N，當該程序運行時間大於N時計算結果與1的差的絕對值小於ε。證畢

希望我的理解能幫到你

題主高中的時候沒有學過等比數列嗎？

這個問題不就是一個等比數列求和問題嗎？

這讓我想起小學的一個題，當時覺得這可真是太厲害

因為:

1/3=0.3333....

1/3*3=1

所以有:0.999...=1

我來隨便瞎說一點—一個一個加肯定能加完，做法：用一秒算加1，用半秒算加1/2，用四分之一秒算加1/4，這樣你一秒就全算完啦～

題主需要學一下高等數學入門知識之極限

有點明白了，自答

應該是說，只要存在演算法就是「可計算的」？雖然這些演算法機器想不出來

而1/2的所有正整數冪之和不僅能很好地被定義，也能找到演算法

相比之下蔡廷常數能被定義，但是不能找到演算法，所以說不可計算

而發散級數一般不可定義，所以也沒有能不能計算的說法

我就看個熱鬧，看看多少人沒學過極限

邀請我的也是夠無聊

題主你好，首先是可計算的，本質上是求極限，求極限也是一種計算。

題主可以看一下實數理論，你給出的這個級數，前n項和的表達式是可求的。本質上它就是一個數列了，這個數列因為實數本身的拓撲性質，可以求出它的極限就是1。

就這麼靜靜看著部分答主不明白什麼是，停機、可計算就來講一波極限就跑...

錯了，不是1是無窮接近1。等比數列知道吧，1/2+1/4+1/8+.....1/2n=1-1/2n 無限接近於1。有人對1用裂項1＝1/2+1/2 1/2=1/4+1/4 1/4=1/8+1/8.....最後你得到這個式子

1=1/2+1/4+1/8+....+1/2n 然後發現與上面的式子相悖對嗎？呵，嚴格來說對1用裂項法那步是錯的， 1=1/2+1/4+1/8+....+1/2n +1/2n 一般我們寫的時候都會只寫一個1/2n，(我也不知道為什麼，但是好像默認這麼寫的) PS:(2n意思是2的n次冪，因為輸入法好像打不出來冪，各位見諒)

所以嚴格來說應該是無窮接近於1

類似的還有餘數的一個例子，比如

1/3＝0.33333333....(0.33333333....代表循環小數循環小數實在不好打，見諒。)

兩邊同時乘三

1＝0.999999999....怎麼樣，是不是懷疑學了假的數學? 其實你如果仔細除法的定義，你會發現這種寫法其實是不規範的，分數不能直接等於循環小數，因為有餘數，也就是說

1/3=0.33333333....余 0.00000000....1(中間有無數個0)，但是為了簡便，我們是默認這種寫法的，而且差的也很少，但是嚴格意義上循環小數小於分數。

懂了嗎？