Vispārīgā gadījumā - jā, šādu izsecināšanu var izdarīt. "Vai tam pietiks resursu", savukārt, automātiski kļūst par "cik daudz resursu tam vajadzēs".

(Reply to this) (Parent) (Thread)

In general there is a disctincition between polynomial algorithms (tractable) and exponential algorithms (intractable) - complexity 101.

(Reply to this) (Parent) (Thread)

I agree on the distinction but not on the specification. In practice tractability most frequently can be seen as equal to the upper bound of available computational resources.

Galvenokārt tādēļ, ka "praksē" ir stiepjams jēdziens kā tāds. Tiklīdz mēs esam šaipus computability robežai, jelkura problēma ir atrisināma ar universālo Tjūringa mašīnu galīgā skaitā soļu = galīgā laikā. Tas, ka šis laiks var būt ilgs, netiek apstrīdēts, taču es neredzu, kādēļ tā būtu problēma.

(Reply to this) (Parent) (Thread)

Principā, ir pierādīts (L. A. Levin, Universal sequential search problems, 1973), ka katru problēmu, kurai eksistē programma p ar garumu ℓ(p), kura apstājas laikā t(p), var sliktākajā gadījumā atrisināt ar universālo Tjūringa mašīnu laikā 2^ℓ(p)+1t(p). Tas ir vismazāk optimālais gadījums, kurā tiek veikta Levina meklēšana pa koku no visām programmām, kas atbilst iepriekšminētajiem kritērijiem. Jau šobrīd eksistē virkne universālās meklēšanas algoritmu, kas atrod atbildi vai apstājas optimālākā laikā (Hatera meklēšana, pieaugošas varbūtības algoritmiskie ģeneratori) un universāliem tuvu algoritmu, kuru laika optimalitāte ir vēl augstāka (AIξ^tl aģenti, sakārtotu programmu koku pakāpeniska meklēšana (OOPS sistēma), metaoptimizējošā semantiskā evolucionārā meklēšana (MOSES sistēma)). Parādoties AGI, šai problēmai rodas vēl viens risinājumu virziens - inteliģentas sistēmas, kas spēj saprast uzdevumu un aktīvi ierobežot tā meklēšanas telpu.

(Reply to this) (Parent) (Thread)

Ja laiks ir ilgāks par paredzamo Visuma pastāvēšanas mums zinamajā veidā laiku, tad arī neredzi, ka tā varētu būt problēma?

(Reply to this) (Parent) (Thread)

Tas, principā, ir vienīgais problemātiskais scenārijs, ko es šajā sakarā varu iedomāties. Un pat tādā gadījumā runa ir par meklēšanas laiku ar klasisku kanonisko Tjūringa mašīnu, kas izmanto vienu viena bita platuma lenti. Praksē ļoti daudzas sequentially neatrisināmas problēmas piepeši kļūst pat ļoti atrisināmas, iesaistot masveida paralēlismu un citas reālas skaitļošanas tehnikas, kuras parastie teorētiskie Tjūringa mašīnu apraksti neņem vērā.

Jāpiezīmē, ka šeit es pieturos pie maksimāla present-grounded reālisma, kas neapsver hipotētiskas iespējas par tehnikām un iespējām, ko varētu ultramasīvai skaitļošanai izmantot nākotnē.

(Reply to this) (Parent) (Thread)

Eksponenciālie algoritmi ir un paliek eksponenciāli, un parastais paralēlisms tos kvalitatīvi neatrisinās.
Vienīgā no fizikas viedokļa puslīdz ticamā pretinde ir kvantu datori, bet arī tie spēj panākt eksponenciālu uzlabojumu tikai atsevišķām problēmām.

(Reply to this) (Parent) (Thread)

If you can't use a computable problem with adding more computational resources, you aren't adding enough. Pie tam, kā jau sacīju, klasisks universālam meklēšanas algoritmam eksponenciāls pieaugums ir novērojams tikai sliktākajā, tīra brute-force gadījumā.

(Reply to this) (Parent)