Od programowania do kafelkowania (i z powrotem)

16.10.2009 - Krzysztof Dryś
TrudnośćTrudnośćTrudność

Ciężkie jest życie kafelkarza!

Co tu się właściwie wydarzyło? Postawiliśmy proste, wydawałoby się, zadanie. Należy określić czy da się wykafelkować ścianę w taki sposób, by kafelki spełniały parę prostych zasad. Co się okazało? Zobaczyliśmy, że komputer nie może sobie poradzić z tym zadaniem!

Uwaga! Symulowanie komputera za pomocą kafelków uda się Wam tylko jeżeli macie dowolnie dużą ścianę!

Jest tak dlatego, że za pomocą kafelków można symulować Maszyne Turinga. Ta natomiast jest równoważna naszym komputerom. Oznacza to, że na kafelkach można symulować obliczenia komputerowe. Innymi słowy: można tak dobrać reguły by z kafelków dało się ułożyć ścianę wtedy i tylko wtedy, gdy Maszyna Turinga (albo odpowiadający mu program) zatrzyma się.

Zobaczyliśmy problem który, chociaż wydaje się zwyczajny, jest nierozwiązywalny na komputerze. I to niezależnie od możliwości sprzętowych, dostępnego czasu i umiejętności programistycznych. Trudność tego problemu wyniknęła z tego można za jego pomocą symulować zachowanie komputera.

Dlatego następnym razem, zanim zabierzecie się za rozwiązywanie problemu przy pomocy komputera, zastanówcie się najpierw, czy jest w ogóle możliwe!

4.6
Twoja ocena: Brak Ocena: 4.6 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com