Vi beskriver en beräkningsmodell för att studera komplexiteten i självsammansatta strukturer med aktiva molekylära komponenter. Vår modell fångar begrepp om tillväxt och rörelse allestädes närvarande i biologiska system. Modellen är inspirerad av biologins fantastiska förmåga att montera biomolekyler som bildar system med komplicerad struktur och dynamik, från molekylärmotorer som går på styva spår och proteiner som dynamiskt förändrar cellstrukturen under mitos, till embryonal utveckling där storskaliga komplicerade organismer effektivt växer från en enda cell. Med hjälp av denna aktiva självmonteringsmodell visar vi hur man effektivt monterar ihop former och mönster från enkla monomerer. Till exempel visar vi hur man odlar en rad monomerer i tid och antal monomertillstånd som bara är logaritmiska i sin längd. Våra huvudsakliga resultat visar hur man växer godtyckligt anslutna tvådimensionella geometriska former och mönster i förväntad tid polylogaritmisk i storleken på formen plus ungefär den tid som krävs för att köra en Turing maskin avgöra om en given pixel är i form eller inte. Vi gör detta samtidigt som antalet monomerer typer logaritmiska i form storlek, plus monomerer som krävs av Kolmogorov komplexiteten i formen eller mönstret. Detta arbete belyser därmed den grundläggande effektivitetsfördelen med aktiv självmontering framför passiv självmontering och motiverar experimentella insatser för att konstruera aktiva molekylära självmonteringssystem.
Huvudresultatet av REF var att varje beräkningsbar form av storlek ≤ n × n kan byggas i tid polylogaritmisk i n, plus ungefär den tid som behövs för att simulera en TM som beräknar om en given pixel är i slutlig form eller inte.
Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
{'venue': "ITCS '13", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}