Moc obliczeniowa człowieka: czy ludzie mogą rozwiązać problem zatrzymania na maszynach Turinga?

60

Wiemy, że problem zatrzymania (na maszynach Turinga) jest nierozstrzygalny dla maszyn Turinga. Czy są jakieś badania nad tym, jak dobrze ludzki umysł może poradzić sobie z tym problemem, być może wspomagane przez maszyny Turinga lub komputery ogólnego przeznaczenia?

Uwaga : Oczywiście, w ścisłym tego słowa znaczeniu, zawsze możesz powiedzieć „nie”, ponieważ istnieją maszyny Turinga tak duże, że nie można ich odczytać nawet za życia jednego człowieka. Ale to nonsensowne ograniczenie, które nie przyczynia się do faktycznego pytania. Tak więc, aby wszystko było w porządku, musielibyśmy zakładać ludzi o dowolnym czasie życia.

Możemy więc zapytać: biorąc pod uwagę maszynę Turinga T reprezentowaną w dowolny odpowiedni sposób, arbitralnie długotrwały ludzki H i dowolną ilość bufora (tj. Papier + długopisy), czy H może zdecydować, czy T zatrzymuje się na pustym słowie?

Następstwo: jeśli odpowiedź brzmi „tak”, czy nie rozstrzygałoby się to również, jeśli jakikolwiek komputer ma szansę na zdanie testu Turinga?

computability turing-machines halting-problem human-computing maska ​​bitowa
źródło
15
Ludzie mogą być w stanie ustalić, czy zatrzyma się kilka konkretnych maszyn. Ale z powodu nierozstrzygalności problemu zatrzymania i tezy Kościoła Turinga nie ma procedury algorytmicznej, którą człowiek mógłby zastosować do rozwiązania problemu.
Carl Mummert,
6
@CarlMummert: Ludzie mają pomysłowość; Ta pomysłowość niekoniecznie wiąże się z tym, co możesz wyrazić w formie TM. Powód, dla którego hp jest nierozstrzygalny dla TM, wynika z sprzeczności w języku przekątnym.
maska ​​bitowa
4
Gdyby ludzie mieli rodzaj mocy, aby dowiedzieć się, na jakich wejściach zatrzymuje się dana maszyna Turinga, prawdopodobnie nie odczuwaliby potrzeby sformułowania definicji maszyny Turinga lub klas P i NP itp., Tak jak by to zrobili wydają się nam przede wszystkim ciekawością opisywania całkowicie trywialnych problemów. (Oczywiście, jeśli jesteś w hojnym nastroju, może to być postrzegane jako opis naszego związku z deterministycznymi automatami skończonymi.)
Niel de Beaudrap
6
@NieldeBeaudrap: Nie zgadzam się. Chociaż możemy być w stanie coś zrobić, może to być trudne zadanie (aby uniknąć słowa „trudny”). Ponadto, jeśli nie skoncentrujemy się odpowiednio, popełniamy nieostrożne błędy, zwłaszcza przy żmudnych zadaniach.
maska ​​bitowa
8
Myślę, że najlepszą i jedyną odpowiedzią na twoje pytanie jest to, że nikt nie wie. Nikt nie wie, czy teza Kościoła-Turinga jest prawdziwa, czy jakie ograniczenia istnieją w tym, co ludzie mogą obliczyć. My może powiedzieć, że jeśli ludzie mogą rozwiązać problemu stopu, robią coś, że maszyny Turinga nie może.
Patrick87,

Odpowiedzi:

28

Bardzo trudno jest zdefiniować ludzki umysł z takim rygorem matematycznym, jak to możliwe, aby zdefiniować maszynę Turinga. Nadal nie mamy działającego modelu mózgu myszy, ale mamy sprzęt zdolny do jego symulacji. Mysz ma około 4 miliony neuronów w korze mózgowej. Człowiek ma 80-120 miliardów neuronów (19-23 miliardy kory mózgowej). Zatem możesz sobie wyobrazić, o ile więcej badań będzie trzeba przeprowadzić, aby uzyskać działający model ludzkiego umysłu.

Można argumentować, że musimy jedynie stosować podejście odgórne i nie musimy rozumieć indywidualnych działań każdego neuronu. W takim przypadku możesz studiować jakąś niemonotoniczną logikę, rozumowanie uprowadzające, teorię decyzji itp. Kiedy pojawiają się nowe teorie, pojawia się więcej wyjątków i paradoksów. I wygląda na to, że nigdzie nie jesteśmy blisko działającego modelu ludzkiego umysłu.

Po uwzględnieniu rachunku zdań i predykatów zapytałem mojego profesora logiki:
„Czy jest jakaś logika, która może zdefiniować cały zestaw ludzkiego języka?”
Powiedział:
„Jak byście zdefiniowali następujące rzeczy?
Aby zobaczyć Świat w ziarnku piasku
I Niebo w dzikim kwiacie,
Trzymaj Nieskończoność w dłoni
I Wieczność za godzinę.
Jeśli możesz to zrobić, zrobisz to stać się sławnym."

Dyskutowano, że ludzki umysł może być równoważny maszynie Turinga. Jednak bardziej interesującym rezultatem byłoby, gdyby ludzki umysł nie był odpowiednikiem Turinga, ponieważ dałoby początek definicji algorytmu, którego prawdopodobnie nie da się obliczyć przez maszynę Turinga. Wtedy teza Kościoła nie byłaby aktualna i mógłby istnieć ogólny algorytm, który mógłby rozwiązać problem zatrzymania.

Dopóki nie zrozumiemy więcej, możesz znaleźć pewne spostrzeżenia w dziedzinie filozofii. Jednak żadna odpowiedź na twoje pytanie nie jest ogólnie akceptowana.

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Minds_and_machines http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments

Dávid Natingga
źródło
Zakładając, że mózg można modelować jako zbiór cząsteczek oddziałujących ze sobą, czy nie wystarczyłoby wykazanie, że cząsteczki są „obliczalne”? Wydaje się, że istnieją pewne dowody na to założenie (patrz OpenWorm).
Olivier Lalonde
@OlivierLalonde Twoje założenie sugerowałoby, że ludzie mogą być symulowani przez maszynę Turinga, a zatem nie mogą rozwiązać problemu zatrzymania. Twoje założenie jest jednak zbyt silne. Zgodnie z zasadą nieoznaczoności en.wikipedia.org/wiki/Uncertainty_principle w mechanice kwantowej, stanu układu fizycznego nie można symulować na komputerze, ponieważ dowolna losowa sekwencja stanów jest nieprzewidywalna. Możesz następnie argumentować, że model układu fizycznego jest deterministyczny - niełatwy. Pytanie ogranicza się do tego, czy można obliczyć symulację mózgu.
Dávid Natingga
@DavidToth Losowa nieskończona sekwencja stanów nie jest obliczalna. Każdy system zawierający skończoną liczbę zdarzeń jest obliczalny, przy założeniu, że wszystkie wielkości w tym systemie są obliczalne względem siebie. I nawet jeśli tak nie jest, po prostu otrzymalibyśmy błąd zaokrąglenia mniejszy niż hałas termiczny, co nie powinno mieć znaczącego wpływu na poznanie człowieka. (W rzeczywistości błąd byłby niezmiernie mały).
Keen
@Cory Tak, każdy skończony podzbiór dowolnego zestawu, nawet niepoliczalny, jest obliczalny, ale chodzi o to, aby „symulować przyszłość”, a nie odtwarzać przeszłości. W tym sensie może nie istnieć maszyna Turinga, która przewidziałaby ludzkie działanie w dowolnie odległym czasie w przyszłości. Musiałby przewidzieć jedną z kombinacji nieskończonej sekwencji przyszłych wydarzeń. Fakt, że liczba możliwych zdarzeń w danym momencie może być skończona, nie zmienia nieprzewidywalności nieskończonej sekwencji.
Dávid Natingga
2
@DavidToth Nie twierdzę, że cała rzeczywistość jest koniecznie obliczalna przez Turinga. Jednak argument losowości kwantowej nie podtrzymuje się. Mechanika kwantowa to system wykorzystywany przez fizyków do obliczania właściwości przyszłych stanów rzeczywistości. Modele fizyków (obliczalne) mogą poradzić sobie z tą losowością, ponieważ liczba (dających się rozróżnić) wyników jest zawsze policzalna (a zatem obliczalna), nawet w przypadkach, gdy jest nieskończona. Zauważ, że nie ma również powodu, aby sądzić, że losowość kwantowa dałaby ludziom, a nie innym maszynom, zdolność do oceny funkcji nieobliczalnych.
Keen
16

Myślę, że nie ma sposobu, aby udzielić ostatecznej odpowiedzi na to pytanie, ponieważ nikt tak naprawdę nie zna możliwości ludzkiego umysłu (i wątpię, by ktokolwiek kiedykolwiek).

Ale istnieje pogląd, który daje jedno możliwe rozwiązanie lub wyjaśnienie tego pytania:

Kiedy szukamy wyroczni, aby rozwiązać problem zatrzymania (lub decydujemy o sprawdzalności formuł logicznych pierwszego rzędu itp.), Naturalnie chcemy, aby wyrocznia była poprawna , nie może popełniać żadnych błędów. Ale ludzki umysł nie jest konsekwentny, popełnia błędy. Nikt nie może szczerze powiedzieć, że wszystkie stwierdzenia, które uważa za prawdziwe, są naprawdę prawdziwe. Ta niekonsekwencja może być postrzegana jako źródło mocy, jaką posiada ludzki umysł. Ze względu na jego niespójność nie podlega ograniczeniom wynikającym z problemu zatrzymania, twierdzenia o niekompletności Gödela itp. Popełniamy błędy, błędnie wierzymy w fałszywe stwierdzenia, a wraz z naszą wiedzą poprawiamy je (i oczywiście znajdujemy nowe fałszywe oświadczenia, w które wierzymy). Z drugiej strony chcemy, aby wszystkie formalizacje pojęcia algorytmu lub wszystkich logicznych rachunków były spójne, abyśmy mogli raz na zawsze udowodnić, że są wolni od takich błędów. A to czyni je ograniczonymi.

Petr Pudlák
źródło
Nie popełniamy większego błędu niż nasze systemy sprawdzające. Praca nad hipotezami jest dość powszechna, nawet w matematyce. Czasami prowadzą do wyników, które mogą być błędne (lub obserwacyjnie błędne w naukach przyrodniczych), a my weryfikujemy nasze przekonania i niektóre z naszych hipotez roboczych. W matematyce jest to podstawa dowodu przez reductio ad absurdum (które nie są konstruktywne). Automaty niedeterministyczne opierają się również na założeniu, że można uzyskać wyniki nawet podczas eksploracji złych ścieżek, o ile można także eksplorować inną ścieżkę. Nic tam nie różnicuje ludzkiego umysłu.
babou
Interesujący punkt na temat możliwości, że niekonsekwencja jest jednym ze źródeł (obliczeniowej) mocy umysłu. Czy przyszło ci do głowy, że mogą istnieć myśli poza matematyką, w których dwie ewidentnie sprzeczne dane mogą być prawdziwe? Jakość „prawdy” jako pojęcia względnego, której nie można przypisać żadnej liczbie, jest rozróżnieniem myśli ludzkiej, która jest trudna (czy mogę powiedzieć, że niemożliwa?) Do pełnej replikacji w maszynie. Chodzi o to, że zdefiniowanie niekonsekwencji mentalnej jako „błędnej wiary w kłamstwo” (jak się wydaje, że tak robisz) jest raczej ograniczonym poglądem.
Wildcard,
Można wykazać, że nie można udowodnić, że nigdy się nie pomylisz, ale to nie znaczy, że mogą obalić, że nigdy się nie popełnią. Załóżmy na przykład, że nasz wszechświat to symulacja życia Conwaya, która nie jest zgodna z teorią wielu światów. Ponadto załóżmy, że oświadczasz, że nigdy nie popełniłeś błędu. Wówczas pewien algorytm nie zatrzyma się, dopóki nie stwierdzisz, że ten algorytm się nie zatrzyma. Jeśli używasz wystarczająco silnego systemu, możesz wywnioskować, że nigdy nie powiesz, że się nie zatrzyma, a zatem, że nigdy się nie zatrzyma, i stwierdzi, że powoduje to zatrzymanie.
Timothy
11

Żeby było jasne: hipoteza Kościoła Turinga nie ma nic wspólnego z dogmatem hipotetycznego Kościoła Turinga. Nie ma w tym nic religijnego. Przeciwnie, jest to tylko hipoteza podsumowująca naszą najlepszą wiedzę. Nie ma metafizycznej implikacji. Pytanie, czy ludzie potrafiliby lepiej, że mogliby osiągnąć więcej niż maszyny, jest pytaniem metafizycznym, ponieważ nie mamy nad tym absolutnie żadnego pojęcia ani żadnej wskazówki na temat tego, co mogłoby odróżnić człowieka od maszyny. To pytanie należy przenieść do metaphysics.stackexchange.com.

Załóżmy jednak, że ludzki mózg może rozwiązać problem zatrzymania maszyny Turinga. Wtedy model obliczeniowy Maszyn Turinga staje się znacznie mniej ważny, a hipoteza Kościoła Turinga staje się mniej istotna, ponieważ mamy mocniejszy model zwany Modelem Ludzkim (aby uniknąć maszyny słownej ). Oczywiście ten (arbitralnie długotrwały) model ludzki ma własną hipotezę dotyczącą obliczalności.

Ale chociaż problem zatrzymania maszyn Turinga nie jest już krytyczny, musimy teraz poradzić sobie z problemem zatrzymania modelu ludzkiego. A diagonalizacja pokaże, że problem modelowania człowieka nie jest rozstrzygalny przez człowieka. Co wtedy

Teraz możesz sprzeciwić się, że diagonalizacja nie miałaby zastosowania. Oznaczałoby to, jak sądzę, powiązanie jakiejś formy numeracji Gödla z urządzeniami obliczeniowymi, dowodami lub czymkolwiek, co opisujemy notacją, nie byłoby już możliwe, chociaż jest to obecnie podstawa całej nauki. Innymi słowy, musielibyśmy mieć do czynienia z bytami, pojęciami, które nie mają pisemnej reprezentacji, które nie mogą mieć pisemnej reprezentacji, lub mówiąc bardziej ogólnie, koncepcjami bez reprezentacji składniowej, czy to pisemnej, ustnej czy innej.

Oczywiście byłoby to sprzeczne z nauczaniem Jana, którego pierwsze zdanie brzmi: „ Na początku było Słowo, a Słowo było u Boga, a Bogiem było Słowo. ” Negowanie fundamentalnej wagi składni, słowo jest zatem bardzo antychrześcijańskim stwierdzeniem. Oczywiście nie zajmuję stanowiska w tej sprawie, ale odkąd po raz pierwszy przyjmuję to pytanie, jest to metafizyczne, a ponieważ pytanie nie zostało zawieszone, wydaje się naturalne, że rozważa się wszystkie konsekwencje, w tym konsekwencje metafizyczne.

Babou
źródło
Nie-chrześcijanin nie jest synonimem ateisty.
ubadub,
@ubadub Masz całkowitą rację. Mój błąd całkowicie, a ściślej mój brak uwagi na ważny punkt. Dokonałem korekty. Czy wiesz, co inne religie mają do powiedzenia w tej sprawie?
babou,
kilka szkół buddyzmu klasyfikuje rzeczywistość „absolutną” jako niewysłowioną, tj. całkowicie poza językowym opisem, a jednak możliwą do poznania (przez oświeconych). Daje to interesujący zestaw zagadnień filozoficznych, które były przedmiotem dyskusji buddyjskiej od tysiącleci. Zobacz ten artykuł: bit.ly/2G71tmk dla jednego ujęcia , chociaż nie jest to jedyny. Garfield czytał dialektyzm buddyzmu Madhyamaka, z którym nie wszyscy naukowcy się zgadzają (np. Patrz „Dialetyzm Gorampy” „Wolność od proliferacji konceptualnej?” Autorstwa C. Kassora).
ubadub,
8

Rozważ to z innej perspektywy.

  • Logika pierwszego rzędu jest nierozstrzygalna, to znaczy nie ma procedury decyzyjnej, która określa, czy arbitralne formuły są logicznie poprawne. (Ale zestaw prawdziwych formuł pierwszego rzędu jest w połowie rozstrzygalny , to znaczy jeśli formuła jest prawdziwa, możliwe jest znalezienie dowodu za pomocą algorytmu.)
  • Pomocni dowódcy pomagają udowodnić twierdzenia w logice pierwszego rzędu (a nawet wyższego rzędu). Asystent ds. Weryfikacji zapewnia prawidłowe wykonanie dowodu, a nawet może pomóc w rozwiązaniu niektórych przypadków. Jednak interakcja człowieka jest konieczna, aby asystent dowodu poprowadził właściwą odpowiedź.

Dowody pomocnicze mogą być wykorzystane do udowodnienia właściwości poszczególnych maszyn Turinga.

Dave Clarke
źródło
3

Komentarz Carla Mummerta go przybił.

  1. Moje rozumienie (popraw mnie, jeśli się mylę) tezy Kościoła Turinga polega na tym, że wszystko, co można obliczyć, może być obliczone przez Maszynę Turinga.

  2. A także, jeśli Maszyna Turinga mogłaby obliczyć, czy inna Maszyna Turinga zatrzymałaby się lub nie na wejściu (problem z zatrzymaniem), możesz również obliczyć, czy inna Maszyna Turinga nie zatrzymałaby się na danym wejściu (po prostu zamień tak na nie i nie na tak!) - znaczące, ponieważ wtedy mógłbyś sam nakarmić tę maszynę Turinga - czy nie zatrzyma się na wejściu? Jeśli tak (nie zatrzymuje się), to nie (zatrzymuje się?). Jeśli nie, to tak. Jeśli tak, to nie. Jeśli nie, to ... hmmm.

Tak więc 2. pokazuje, że maszyna Turinga nie może rozwiązać problemu zatrzymania. Ale nie sądzę, aby w tej chwili istniały jakiekolwiek wyraźne dowody, które mogłyby temu zaprzeczać. Każdy znany model obliczeniowy wciąż może rozwiązać (zdecydować) tyle, ile potrafi maszyna Turinga.

Ciężar dowodu wydaje się spoczywać na osobie, która wymyśliła nowy model obliczeń, który ma więcej mocy (czyli może decydować o większej liczbie problemów) niż klasyczna maszyna Turinga.

Nawiasem mówiąc, kilka świetnych wykładów na ten temat można znaleźć tutaj .

Bingo
źródło
3

Nie ma żadnych dowodów na to, że ludzki mózg jest w rzeczywistości czymś więcej niż maszyną Turinga. W rzeczywistości wydaje się, że cały wszechświat można symulować na (wystarczająco dużej) maszynie Turinga.

Ludzie są „inteligentni” z powodu inteligentnych algorytmów, które są sprytnie zapisane w neuronach, dzięki czemu informatycy nie mogą ich ukraść ani skutecznie wdrożyć. Jakkolwiek sprytne są te algorytmy, najprawdopodobniej nie są w stanie w wiarygodny sposób rozwiązać problemu zatrzymania.

ithisa
źródło
„wydaje się, że cały wszechświat można zasymulować” - nie, nie może, ponieważ zasada nieoznaczoności oznacza, że ​​nie możemy znaleźć stanu początkowego z wystarczającą dokładnością, aby to zrobić. Możemy symulować się wszechświat podejmowania arbitralnych decyzji dotyczących stanu początkowego, ale to niekoniecznie jest symulacja z wszechświatem.
Periata Breatta
1
Nie ma również żadnych dowodów na to, że cała myśl opiera się na dowodach. Istnieje wyraźna możliwość, że Wiedza jest lepsza od dowodu i że wiedza oparta na dowodach jest znacznie niższą zdolnością umysłową niż wiedza bezpośrednia w sposób niepodatny na dowód. Czy cała wiedza musi opierać się na dowodach? Co powiesz na bezpośrednie tworzenie nowej wiedzy?
Wildcard
1
Cytat z książki Madeleine L'Engle „Many Waters” czyni to zagadnienie o wiele bardziej zwięzłym, nawet jeśli jest rozważane jedynie jako możliwość, a nie faktyczne stwierdzenie: „Pewne rzeczy trzeba wierzyć, aby je zobaczyć”. Jeśli wejdziesz w dziedzinę epistemologii, zakładając, że nic nie istnieje, o ile nie zostanie udowodnione, że nakładasz dowolne granice potencjalnego zakresu wiedzy.
Wildcard
Jeśli chodzi o część wszechświata, potrzebujesz tam kwantu, tj. En.wikipedia.org/wiki/...
Fizz
2

W skrócie: NIE

są maszyny Turinga, o których nie wiemy (jeszcze), czy te maszyny się zatrzymały ( na przykład hipoteza Collatza ).

Dopóki nie znajdziemy sposobu na policzenie wszystkich Maszyn Turinga, dla których nie mamy zabezpieczenia przed zatrzymaniem, i dopóki nie znajdziemy sposobu na udowodnienie Zatrzymania tych maszyn, nie jesteśmy lepsi od maszyny Turinga (jeśli Mam rację, ktoś już udowodnił, że nie możemy wszystkiego udowodnić, co wskazuje na fakt, że jesteśmy tak ograniczeni jak maszyny Turinga). Och, czekaj, nie możemy wyliczyć wszystkich tych maszyn, ponieważ w rzeczywistości mamy ograniczoną pamięć i ograniczoną żywotność.

Niezależnie od tego, czy pytasz, jest to odpowiedź:

Pytasz, czy człowiek jest w stanie „zdecydować”, ale sama decyzja jest zdefiniowana jako algorytm, tak więc my uruchamiamy algorytm w naszych umysłach i dochodzimy do prawidłowego wniosku (lub wcale nie do wniosku: otwarte problemy), lub zgadujemy.

Teoria obliczeń dotyczy:

  • Załóżmy, że istnieje algorytm czarnej skrzynki (Oracle), który może odpowiedzieć tak lub nie na niektóre pytania
  • Następnie możesz użyć go, aby odpowiedzieć na pytania, na które nie można odpowiedzieć, budując inny algorytm, który go używa
  • Robiąc to, kończysz się sprzecznością

Oznacza to, że dopóki masz dowolny system, który chce odpowiedzi Nolub Yes, Oracle nie jest kompatybilne z tym systemem, więc Oracles może faktycznie istnieć, ale nie mamy możliwości przekazania wyników , ponieważ jeśli jesteśmy w stanie przekazać wyniki, kończy się gdzieś sprzeczność.

Załóżmy, że mechanika kwantowa składa się z wielu małych wyroczni, więc nie możesz przekazać ich wyników, ponieważ kiedy odczytujesz status cząstki, zmieniasz również status tej cząstki.

Miałem odpowiedź, ale ją przeczytałem ...

W rzeczywistości możemy udowodnić wszystko, jeśli zaczniemy od fałszywej hipotezy. Możemy więc udowodnić, że algorytm się zatrzymuje, ale możemy również udowodnić, że algorytm się nie zatrzymuje, co może być interesujące, ale jest bezużyteczne, ponieważ sprzeczny wynik (chcesz odpowiedzi Yeslub Noodpowiedzi) nie jest tym, czego chcesz.

Twórca gier
źródło
dlaczego downvotes? Fakt, że przekazanie wyniku wyroczni nie jest możliwe, jest bardzo głębokim i interesującym punktem, który również odpowiada na pytanie.
GameDeveloper,
Ale czy nie sądzisz, że ludzie w końcu udowodnią lub
rozwiążą
1

podobnie jak w przypadku odpowiedzi DC (i nieco ją rozwinąć) istnieje silne poczucie, że to pytanie (połączenie człowieka i komputera w znalezieniu specjalnych rozwiązań problemu zatrzymania) jest powiązane z dziedziną ATP, automatycznym dowodzeniem twierdzeń i ściśle powiązane dowody wspierane komputerowo . od dawna wiadomo również, że istnieje silna zgodność między programami i dowodami w korespondencji Curry-Howarda . podobne / podobne do tego jest również zakończenie programu (np. za pomocą niezmienników pętli lub wariantów pętli ). w rzeczywistości istnieje głębokie poczucie, w którym wszyscymatematyki dotyczy tego problemu, ponieważ praktycznie wszystkie wyrażenia matematyczne można przekształcić w pytania dotyczące konkretnych programów w bazach TM zatrzymujących się lub nie zatrzymujących. patrz np. [2], aby uzyskać dodatkowe informacje i wiele innych informacji na temat ATP itp.

[1] to pół-znana książka na ten temat, która szczegółowo analizuje pytanie, odnosząc je do możliwości sztucznej inteligencji. pokrótce pomysł Penrose'a jest taki, że prawdziwa sztuczna inteligencja musi być niemożliwa, ponieważ ludzie mogą wymyślić dowody nierozstrzygalności, takie jak zatrzymanie problemu Turingów lub dowód niekompletności Godelsa, podczas gdy komputery nie mogą z powodu tych samych zjawisk.

[1] Nowy umysł cesarzy autorstwa Penrose'a

[2] przygody i komunikacje w bankomatach , vzn

vzn
źródło
1
Nie rozumiem, jak ktoś może głosować na tę odpowiedź, która łączy wiele interesujących materiałów. +1 i +100, gdybym tylko mógł.
GameDeveloper,
-1

Nowoczesne systemy superkomputerów z pewnością mogą symulować zachowanie co najmniej jednego atomu. Jeśli można symulować poszczególne atomy, można również symulować ludzki umysł, budując wystarczająco duży system komputerowy do symulacji poszczególnych atomów. Myślę jednak, że to samo nie wystarczy. Potrzebujesz również źródła entropii, aby uzyskać prawdziwe liczby losowe do symulacji ludzkiego umysłu. Najlepszym źródłem entropii byłby prawdopodobnie rozpad radioaktywny lub coś w tym rodzaju. Co to znaczy?

Myślę, że ludzki umysł jest potężniejszy niż Maszyna Turinga, ponieważ TM jest deterministyczna. Nie można symulować prawdziwej losowości na maszynie Turinga. (Przynajmniej takie wrażenie wywarłem z następującej dyskusji

https://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable

) Myślę jednak, że Maszyna Turinga, podłączona do prawdziwego źródła entropii, byłaby w stanie symulować ludzki umysł.

Jeśli weźmie się również pod uwagę przypadkowość środowiska, które oddziałuje na ludzki umysł (np. Jedzenie, jemy, jak spać, chodzić, w zasadzie żyć naszym życiem), to z pewnością uważam, że TM z entropią jest potrzebna do symulacja ludzkiego umysłu. Nie zapominaj, że ludzki umysł jest również stale narażony na promieniowanie tła, które może również nieprzewidywalnie oddziaływać z cząsteczkami w naszym mózgu. Myślę jednak, że nawet jeśli weźmiemy pod uwagę całkowicie „izolowane” środowisko (czy to w ogóle możliwe? Ponieważ następujące elementy wydają się wskazywać, że może nie być to możliwe: http://hps.org/publicinformation/ate/faqs/faqradbods.html) - w zasadzie „mózg w słoiku” - scenariusz, prawdopodobnie nadal mielibyście naprawdę przypadkowe procesy, które miałyby miejsce gdzieś w ludzkim mózgu. Jestem pewien, że biolog może rozstrzygnąć tę część pytania? Nie zapominaj również, że człowiek jest w pewnym sensie także częścią swojego środowiska:

http://en.wikipedia.org/wiki/Human_Microbiome_Project

Być może niektóre z tych bakterii w jakiś sposób wpływają na wewnętrzne funkcjonowanie ludzkiego mózgu, a skład tych bakterii może ulec zmianie w ciągu życia człowieka (również w pewnych granicach, jak sądzę?). Pytanie brzmi, czy zachowanie tych bakterii jest losowe w określonych granicach. Jeśli co najmniej jeden proces w co najmniej jednym z tych organizmów jest naprawdę losowy, a także w jakiś sposób pośrednio wpływa na ludzki mózg, wówczas potrzebna byłaby TM ze źródłem entropii, aby symulować ludzki umysł.

Aby odpowiedzieć na pierwotne pytanie:

Czy „człowiek” (jak zdefiniowano w pytaniu) może rozwiązać problem zatrzymania? Tak, jeśli jest to problem zatrzymania dla wszystkich deterministycznych baz TM i nie, jeśli dotyczy wszystkich baz TM, podłączonych do źródła entropii.

Christopher Schmidt
źródło
2
To wydaje się bardzo spekulacyjne. Zasadniczo mówisz, że ludzki umysł zawiera przypadkowość, co oznacza, że ​​nie jest maszyną Turinga, co oznacza, że ​​może być w stanie zdecydować o problemie zatrzymania?
David Richerby,
Prawdopodobnie poprawne jest, że komputer może symulować to, co wiemy o atomach. Ale skąd miałbyś wiedzieć, że to, co wiemy, to wszystko, co trzeba wiedzieć? W takim razie losowość jest przyjemna: jeśli zaczekasz wystarczająco długo, jeśli znajdziesz właściwą odpowiedź ... wśród wielu innych. Po prostu używaj wystarczająco dużo małp wystarczająco długo lub poszukaj odpowiedniej książki w bibliotece Babel. Ale uzyskanie właściwej odpowiedzi to nie wszystko: skąd wiesz, że to właściwa odpowiedź?
babou
Nieokreślone maszyny Turinga nie są bardziej wydajne niż maszyny Turinga. Losowość nie wystarczy, aby stać się lepszym od maszyn Turinga. Zobacz moją odpowiedź
GameDeveloper,
-2

Cała ludzka myśl łączy pojedyncze problemy z osobistym doświadczeniem. Możemy się upewnić, że rozwiązaliśmy problem wystarczająco, aby go zatrzymać, ale nigdy nie wiemy na pewno w sensie algorytmicznym, że komputer uzyska rozwiązanie. Uspokój się i obserwuj swój umysł. 99,9% wiadomości przesyłanych w naszych obwodach neuronowych nie ma nic wspólnego z logiczną reprezentacją świata. Zamiast tego mamy do czynienia z odczuciami „jelitowymi”, danymi sensorycznymi i zalewem wspomnień, skojarzeń i postaw, które są stale różne. Właśnie dlatego mamy metodę naukową.

Steve
źródło
Myślę, że źle zrozumiałeś pytanie. Pytanie brzmi, czy ludzie mogą zdecydować, czy dana maszyna Turinga się zatrzyma, co tak naprawdę nie ma nic wspólnego z „rozwiązaniem problemu na tyle, aby go zatrzymać”. Czy masz na myśli, że możemy być „wystarczająco przekonani”, że maszyna się zatrzyma?
Tom van der Zanden