[發明專利]面向大數據的圖靈機不可解判別方法和系統

在審

• 申請號: 201711459621.6
• 申請日: 2017-12-28
• 公開（公告）號: CN108196918A
• 公開（公告）日: 2018-06-22
• 發明（設計）人: 朱定局;周國富
• 申請（專利權）人: 深圳市國華光電科技有限公司;華南師范大學
• 主分類號: G06F9/448
• 分類號: G06F9/448
• 代理公司: 深圳市神州聯合知識產權代理事務所(普通合伙) 44324
• 代理人: 劉真

本發明公開面向大數據的圖靈機不可解判別方法和系統，面向大數據的圖靈機不可解判別方法，定義圖靈機：M＝(Q,Σ,Γ,δ,q0,qaccept,qreject,m,P0,T0,P,T)，獲取運行時限：彈出輸入框，提示用戶輸入運行時限作為T；獲取讀寫頭能連續移動的格數閾值：彈出輸入框，提示用戶輸入讀寫頭能連續移動的格數閾值作為m；獲取最低價值密度閾值及其預設運行時長T0和所需價值密度P：彈出輸入框，提示用戶輸入最小價值密度閾值、對應預設運行時長、所需價值密度分別作為P0、T0、P。本發明通過給圖靈機的不可解判斷加上時間、空間、輸出的限制，使得更適應大數據應用的需求。

技術領域

本發明涉及圖靈機領域，尤其涉及面向大數據的圖靈機不可解判別方法和系統。

背景技術

圖靈機是現有所有計算機、手機等電子設備以及電子系統、電子平臺的計算模型。圖靈機模型的優越性就在于既能適用于最古老的最原始的計算機，又能適用于最新最先進的計算機，既能適用于單臺計算機，又能適用于分布式計算機集群，既能適合于小數據的處理，又能適用于大數據的處理，正是因為其通用性、普遍性，才能成為所有類型計算機和電子設備以及電子系統、電子平臺的計算模型。

圖靈機可以用M＝(Q，Σ，Γ，δ，q0,qaccept,qreject)，Q為狀態集合，Σ為輸入字符集合,存儲帶字符集合Γ＝Σ∪{□},轉移函數δ：Q×Γ→Q×Γ×{L,R}，q0是初始狀態,qaccept是接受狀態,qreject是拒絕狀態。

現有圖靈機對運行時間、通信開銷、計算結果都不進行了限制，只要在有限的時間內能完成計算，但有限時間可以很長，例如幾萬年，就是可解，不能停機或計算出錯才算不可解，但這樣無法滿足大數據處理的需求，因為大數據處理需要實時，顯然不能對運行時長不做限制；因為大數據處理時數據量非常大，如果在計算過程中需對數據進行遠距離傳輸，顯然由于數據量巨大，導致通信開銷巨大，從而會使得通信癱瘓，因此不能不對通信的距離進行限制，體現在圖靈機上就是計算一次時讀寫頭需要移動的格數；因為大數據的價值密度低，如果在一定的時間內還是挖掘不出一定數量的價值，說明使用當前算法挖掘當前數據是在做無用功，應該結束，而不是繼續挖掘下去。

發明內容

本發明的目的是提供面向大數據的圖靈機不可解判別方法和系統。

本發明的技術方案如下：

面向大數據的圖靈機不可解判別方法，

定義圖靈機：M＝(Q,Σ,Γ,δ,q0,qaccept,qreject,m,P0,T0,P,T)，

獲取運行時限：彈出輸入框，提示用戶輸入運行時限作為T；

獲取讀寫頭能連續移動的格數閾值：彈出輸入框，提示用戶輸入讀寫頭能連續移動的格數閾值作為m；

獲取最低價值密度閾值及其預設運行時長和所需價值密度：彈出輸入框，提示用戶輸入最小價值密度閾值、對應預設運行時長、所需價值密度分別作為P0、T0、P；

其中：Q為狀態集合，Σ為輸入字符集合，Γ為存儲帶字符集合,Γ＝Σ∪{□}，δ為轉移函數，δ：Q×Γ→Q×Γ×{L,R}；q0是初始狀態，qaccept是接受狀態，qreject是拒絕狀態。

進一步的，獲取圖靈機當前狀態，如以qaccept結束，則返回狀態為正常可解，同時獲取圖靈機當前讀寫移動的總格數，如果移動總格數未超過m，則返回狀態為移限內可解，如果運行時長沒有超過T，則返回狀態為時限內可解。

進一步的，獲取圖靈機當前狀態，如以qreject結束，則返回狀態為正常不可解。