|
|
Władysław Ludendorf
problem NP-zupełny jest dobrze zdefiniowanym problemem, bo nie występuje problem stopu i już na samym początku wiemy ile maksymalnie kroków potrzeba żeby maszyna się zatrzymała. Nawet jeśli potrzeba eksponencjalnej liczby kroków. Mi raczej chodzi o problem coś jak szukanie kolejnej liczby pierwszej, kiedy wiemy, że taka liczba istnieje, ale nie potrafimy powiedzieć kiedy się na nią natkniemy.
W sumie nawet nie o to mi chodzi. Po prostu każdy formalizm operuje na pewnym zbiorze symboli i aksjomatów/deklaratywnych reguł. Model obliczeniowy Turinga pozwala obliczyć wszysko co się da w tym i jakimkolwiek innym formaliźmie. Problem w tym, że jak pokazał Goedel, że każdym odpowiednio skomplikowanym formaliźmie istnieją zdania nieobliczalne w ramach tego formalizmu i model obliczeniowy w ramach tego formalizmu nie jest w stanie określić czy takie zdania włączyć z wartością Prawda lub Fałsz tak, aby ten rozszerzony formalizm nie okazał się sprzeczny. To jest decyzja w jakimś sensie arbitralna, niealgorytmiczna, intuicyjna. Każdy komputer jest uniwersalną maszyną Turinga więc AI działająca na komputerze ma powyższe ograniczenia. Prace nad modelem obliczeniowym dla komputerów kwantowych dopiero startują, bo takiego komputera nie mamy jak dotąd i co więcej nie rozumiemy jak QM działa. Chodzi mi o t sławetną procedurę R. |
|
|
Dark Regis
Problem 3SAT czyli wartościowanie klauzul z trzema zmiennymi, spełnianie zdań w tej formie, jest NP-zupełny i daje się liczyć na niedeterministycznej maszynie Turinga. Czyli takiej maszynie, która dopuszcza losowanie. Można losować jakieś potencjalne rozwiązanie problemu i potem w czasie wielomianowym sprawdzić. Oczywiście chodzi o problemy decyzyjne, bo inne da się do nich sprowadzić. Zagadnienie komiwojażera i szukania kliki w grafie też są NP-zupełne.
TSP: en.wikipedia.org
Kiedyś to liczyłem na tzw. maszynie Boltzmanna:
en.wikipedia.org
To jest jedna z metod symulowanego wyżarzania, albo inaczej symulowanej krystalizacji (simulated annealing):
en.wikipedia.org |
|
|
Władysław Ludendorf
Turing zaproponował model obliczeń. Jeżeli coś potrafimy obliczyć, to model Turinga jest wystarczający, żeby podać przepis na to obliczenie. Ale zdaje się nie jest to prawdą w przypadku dowodzenia (dowodzenie to też manipulowanie symbolami, wyliczenie wartości zdań logicznych a więc program) stąd też niektórzy logicy odrzucają dowody bez konstrukcji. |
|
|
Władysław Ludendorf
jn |
|
|
u2
niby nic nie potrafią i na niczym się nie znają
Bez przesady, nawet najmarniejszy prorok nie kaszlnie bez mojej wiedzy:) |
|
|
Dark Regis
Spróbuj wytłumaczyć 3x+1 ty niemiecki trollu spod znaku PIS-Moravec(ajwaj) próbujący dołować i wpędzać w kompleksy Polaków, że niby nic nie potrafią i na niczym się nie znają, a więc nic nigdy nie osiągną. Zaczynaj. Zniosę wiele, bo i tak wiem, że po syfie przyniesionym przez okrągłostolarzy edukacja w Polsce to zwykłe GWno, co widać i słychać. |
|
|
u2
Dużo by o tym pisać ;)))
Czekam na to z niecierpliwością. Jesteś świetny w tym twoim tłumaczeniu świata :-) |
|
|
Dark Regis
System dla pary (-a,b) odpowiada systemowi dla (a,b) w ten sam sposób jak system z bazą całkowitą B=10 odpowiada systemowi z bazą ujemną B=-10, albo dla dolnej innej bazy. Otóż rozkład repunitu w tym systemie z indeksem 2k , gdzie k jest nieparzyste jest następujący J(2k)=J(2)J(k)J(-k), gdzie J(-k) nie oznacza ujemnej liczby jedynek w zapisie liczby, tylko liczbę k jedynek w bazie ujemnej. To znany wzór dla liczby i wielomianów cyklotomicznych, ale o dziwo działa też w moich systemach. Dodatkowo działa tam również uogólnione małe twierdzenie Fermata, można liczyć NWD (które może być zbiorem dwucyfrowym), można wreszcie liczyć uogólnienie operacji modulo. Po prostu nałożenie systemu pozycyjnego na pierścień spowodował, że uporządkowaliśmy jego elementy w sposób liniowy, choć na płaszczyźnie zespolonej kręcą się one wokół zera na modłę fraktala (można to zobaczyć też poprzez formę xB+y liczby). Dużo by o tym pisać ;))) |
|
|
u2
3xN+1
en.wikipedia.org
|
|
|
Dark Regis
@Władysław Ludendorf. Właśnie rozmawiałem o Turning-complete oraz tych formalizmach z ChatGPT i - nie uwierzy Pan - zeszliśmy na temat toposów w informatyce i na mechanikę kwantową i komputery kwantowe. Chodzi o to że Godel przestaje obowiązywać gdy osłabimy aksjomaty arytmetyki albo rozszerzymy logikę, np. do logiki temporalnej (która jest dwumodalna, punkty oraz przedziały czasu i czas płynie nieliniowo, wielowątkowo). To szczenię jeszcze, a już tak wygadane i pyskate ;))) W każdym razie ja zrobiłem dzięki temu pewien postęp. Nie zdołam zamieścić tutaj listingu rozmowy, bo to kilkadziesiąt stron tekstu. Na koniec podał mi nawet namiary na źródła z literatury i okazały się arcyciekawe.
Co do tej techniki sumowania z "dużymi" cyframi, ewentualnie z "ujemnymi", to stworzyłem ją na bazie systemów z bazą ujemną, ale z myślą o zastosowaniu w moich systemach niewymiernych (dla pierścieni liczb całkowitych w ciałach kwadratowych). Takie systemy przypominają ujemną bazę ale mają znacznie bardziej rozbudowane kodowania dla "zera", "przeniesienia" oraz "pożyczki". Podawałem kiedyś przykłady kalkulacji w pierścieniu $\mathbb Z[(-1-\sqrt{-19})/2]$, który jest UFD ale nieeuklidesowy (liczba Heegnera). W tym systemie zero brane jest z równania kwadratowego, czyli z generatora ideału (ideał to jest to, co przejdzie przy homomorfizmie na zero, stąd pomysł) Z[X]/I, I=(x^2+3x+7), czyli "zero" = [137], B^2=-3B-7 (wszystko zapisuję względem bazy), "przeniesienie" = +[1240] (to kod liczby 7), zaś "pożyczka" = [136] = -1 (to wtedy po prostu trzeba dodać). Co ciekawsze podwójne przeniesienie to [111], czyli kolejne parzyste poczwórne [222], sześciokrotne [333] itd. co pozwala odrobinę zoptymalizować algorytmy arytmetyki. W zasadzie interesują mnie liczby w tym systemie, które mają po sto tysięcy cyfr i cechy podzielności na podstawie rozkładu repunitów, bo to pozwala "rozpoznawać ideały główne na oko" (w tym pierścieniu są akurat same główne, UFD). W przypadku ogólnych pierścieni Dedekinda mojej klasy jest kluczowe to, że ideały pierwsze maksymalne w pierścieniach bez jednoznacznej faktoryzacji (na elementy nierozkładalne) mają dwa generatory, przez co pewne konstrukcje jest łatwo przewidzieć. Na przykład definicja ciała Galois GF(q), to Z[X]/(p,w(X)), gdzie q=p^n, p pierwsza, w(X) nie jest rozkładalny i po redukcji współczynników mod p też. Jak widać wszystko się zgadza, ideał ten jest pierwszy, maksymalny, więc pierścień ilorazowy musi być ciałem. Oczywiście nie chodzi o to, że dla tego pierścienia dla wyróżnika d=-19 mogę zadać tylko system pozycyjny C-3-7 opisany wyżej. Takich systemów jest nieskończenie wiele, czyli wszystkie takie pary liczb a,b, że delta równania x^2+ab+b=0 wynosi $\sqrt{-19}$, warunek dodatkowy to b>a>=0. Skoro mam "ujemne" systemy, to gdzie są "dodatnie"? Ano w tym samym miejscu, bowiem wielomiany x^2-ax+b je zadają (b>a>=0). Liczba b zawsze tu mówi o liczbie cyfr, co ja nazywam radixem, a nie bazą. |
|
|
u2
A maszyna Turinga jest maszyną algorytmiczną
Czyli wykonuje pewien algorytm. A ten algorytm wynalazł Turing. Dla mnie swój chłop, dla innych Bóg ;-) |
|
|
Władysław Ludendorf
zastanawia mnie to sumowanie pozycyjne. Na wiki jest pokazane jak to zrobić, ale rozumiem, że to nie jest rozwiązanie, bo wychodzimy poza system liczbowy. Zresztą idea extra carry wygląda cokolwiek dziwnie podobnie jak używanie systemu trójkowego w obliczeniach systemu binarnego. Ale jest też wspomniane, żę to się stosuje w systemach niestandardowych, a chyba takim jest system o bazie ujemniej. Ciekawe, pomyślałem sobie, że może zamiast [19] w przypadku przeniesienia pożyczać [10] z bardziej znaczącej pozycji np:
[163]+[378] =
8+3 = 11 zapisuję [1] i dodaję [10] do następnej pozycji
6+7=13 ale dodaję [10] więc mam 12, zapisuję [2] i przenoszę [10]
1+3=4 ale miałem [10[ więc zapisuję [3]
np [1274]+[145]=[1219]
L=-1000+200-70+4+100-40+5=-801 P=-1000+200-10+9=-801
ale nie wiem, czy to jest poprawne np dla [309]+[103] = [592] gdzie pojawia się 9 ale zwiększa się liczba na następnej pozycji o 1
co do wymyślania algorytmów to nie miałem na myśli kompletności Turinga tylko, że sam proces znajdowania algorytmu jest w ogólności niealgorytmiczny. To trochę jak, ale tylko trochę, że umiemy udowodnić istnienie np. jakiejś liczby ale nie potrafimy podać jej konstrukcji, bo w ramach przyjętego formalizmu nie ma takich zdań, które do tego prowadzą. Ale może istnieć inny formalizm, w którym jest możliwa pewna konstrukcja i nagle okazuje się, że istnieje pewien izomorfizm tego formalizmu na ten pierwszy i okazuje się że już można tę liczbę skonstruować. Penrose uważa, że taki wgląd w te "formalizmy" jest procesem niealgorytmicznym. A maszyna Turinga jest maszyną algorytmiczną, więc nigdy nie wykroczy poza to, co "wie", co nie oznacza, że nie może być inteligentniejsza od czytelnika onetu :). |
|
|
Dark Regis
PS: Właśnie nauczyłem AI rozwiązywania problemu ważenia n kul z jedną kulą cięższą plus pisania odpowiedniej funkcji w JavaScript. ;)))
Następnym razem zajmiemy się problemem ważenia n kul, w tym dwóch kul innych, cięższej i lżejszej. Będzie tu chodziło o znalezienie obu. |
|
|
Dark Regis
@Władysław Ludendorf: W kwestii "wymyślania" algorytmów przez algorytmy - "Żaden niesprzeczny system formalny (teoria) pierwszego rzędu zawierający arytmetykę Peano (aksjomatykę arytmetyki liczb naturalnych i każdą teorię silniejszą) nie jest w stanie wykazać prawdziwości swoich wszystkich twierdzeń". Zwracam uwagę na różnice pomiędzy prawdziwością i dowodliwością, o czym pisałem kiedyś w kontekście systemów dowodzenia w logice. Sytuacja zmienia się, gdy osłabimy arytmetykę, lub logikę. Nie musi to być od razu logika drugiego rzędu, tylko powiedzmy jakaś logika z modalnością (logiki modalne nieformalnie traktuje się jakby były zawieszone pomiędzy logikami pierwszego i drugiego rzędu). Jednak prawdą jest, że w informatyce stosuje się logiki właśnie ze spektrum modalnego. To zmienia postać rzeczy. Ponadto mam podejrzenie graniczące z pewnością, że język wewnętrzny AI, na który ona przekłada wszystkie wprowadzane zdania jest Turing-zupełny. Zresztą to nie jest trudne do osiągnięcia, bo zarówno gra Life jak i systemy automatów w świecie gry jak np. Minecraft są Turing-zupełne. Oczywiście w obu przypadkach musimy dysponować nieograniczoną pamięcią.
Liczenie w bazie -10 i w każdej bazie ujemnej jest zwyczajnie "bazylne" ;)
Problem stanowi tu postać przeniesienia na bardziej znaczącą pozycję przy dodawaniu. W bazie -10 jest to oczywiście liczba [19]. Dodawanie krokowo wygląda więc tak (z użyciem "dużych" cyfr, które wprowadzam dla celów technicznych, nieznormalizowane liczby piszę w uszach ''):
[163]+[378] = ['4DB'] = ['4D1']+[190] = ['5M1'] = ['5C1']+[1900] = ['1EC1'] = ['1E21'] + [1900] = ...
Nie będę tego dalej rozpisywał, ale widać, że przeniesienie będzie się ciągnęło w tym obliczeniu do nieskończoności jak smród w gaciach i nie pozbędziemy się go w "legalny" sposób. Mnożenie zamieniamy na szereg dodawań (w słupku), zatem to tylko zwielokrotni problem nieskończonych kalkulacji. Dlatego opracowałem nową metodę obliczeń arytmetycznych w systemach z bazą ujemną, która polega na odejmowaniu "zer" zanim dokonamy przeniesienia. Właśnie w tym celu wprowadzam do arytmetyki pojęcie "dużych" cyfr. Reprezentacją zera w tym systemie jest więc [0], ['1A'], ['2K'], ['1A0'],... Najpierw dokonuję operacji mnożenia albo dodawania carryless, czyli bez żadnego przenoszenia jak w wielomianach, agregując duże cyfry na ich pozycjach, a następnie przeglądając wynikową 'liczbę' od końca staram się pousuwać wszystkie 'duże' cyfry poprzez odejmowanie 'zer'. W tym przypadku obliczenie wygląda tak:
[163]+[378] = ['4DB'] = ['4DB']-['1A'] = ['4C1'] = ['4C1']-['1A0'] = [321]
Sprawdzenie: L = 100-60+3 +300-70+8 = 411-130 = 281; P = 300-20+1 = 281.
Oczywiście mogą wystąpić w tym algorytmie problemy takie, że nie ma od czego odjąć np.
... = ['B'] = ['B']-['1A'] = ?
Ale wtedy w algorytmie opartym na Integer mogę zaimplementować pomocnicze "ujemne" cyfry a=-1,b=-2,... i dodać "zero"
= ['a1']+['1A0'] = [191] = 11. |
|
|
Edeldreda z Ely
@Imć Waszeć
Ponieważ umyślny z Diamentowym wiekiem już w drodze, pozwolę sobie i ja, w ramach rewanżu polecić Pana uwadze godny okaz.
W tym liście Benedykta XVI, opublikowanym przez Pana Rocha dwa razy, w istotnym kontekście pada słowo: granica.
Roberta Spaemann'a Granice Panu polecam. |
