Beräkning spelar en nyckelroll i att förutsäga och analysera naturfenomen. Det finns två grundläggande hinder för vår förmåga att beräkna det långsiktiga beteendet hos ett dynamiskt system som beskriver en naturlig process. Den första är oredovisad för fel, vilket kan göra systemet oförutsägbart bortom en mycket begränsad tidshorisont. Detta gäller särskilt kaotiska system, där en liten förändring i de ursprungliga förhållandena kan orsaka en dramatisk förändring i banorna. Den andra är Turingfullständighet. Genom obeslutbarheten av Halting Problem, de långsiktiga utsikterna för ett system som kan simulera en Turing Machine kan inte bestämmas beräkningsmässigt. Vi undersöker samspelet mellan dessa två oredovisade fel och Turing-fullständighet. Vi visar att införandet av även en liten mängd buller i ett dynamiskt system är tillräckligt för att "förstöra" Turing-fullständighet, och för att göra systemets långsiktiga beteendeberäkningar förutsägbara. På en mer teknisk nivå behandlar vi långsiktiga statistiska egenskaper hos dynamiska system, som beskrivs av invarianta åtgärder. Vi visar att även om det finns enkla dynamiska system för vilka de invarianta åtgärderna är icke-komputerbara, gör perturbing sådana system de invarianta åtgärderna effektivt beräkningsbara. Således, buller som gör det kortsiktiga beteendet i systemet svårare att förutsäga, kan göra dess långsiktiga statistiska beteende beräkningsbar. Vi får också viss insikt i den beräkningsmässiga komplexiteten i att förutsäga system som påverkas av slumpmässigt buller.
Att införa buller i icke-linjär dynamik har visat sig kunna förenkla analysen av icke-linjära dynamiska system genom att "förstöra" Turing-fullständighet av klasser av dynamiska system och därmed göra systemets långsiktiga beteende beräkningsmässigt förutsägbar REF.
Noise vs computational intractability in dynamics
{'venue': "ITCS '12", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Physics']}