Wykonalność maszyn Gödel

Ostatnio natknąłem się na dość interesującą konstrukcję teoretyczną. Tak zwana maszyna Gödela

To ogólne narzędzie do rozwiązywania problemów, które jest zdolne do samooptymalizacji. Nadaje się do środowisk reaktywnych.

Jak rozumiem, można go zaimplementować jako program do uniwersalnej maszyny Turinga, choć jego wymagania wykraczają daleko poza obecnie dostępny sprzęt. Nie mogłem jednak znaleźć wielu szczegółów.

Czy takie maszyny można budować w praktyce? Czy są przynajmniej wykonalne w naszym Wszechświecie?

1. Czy takie maszyny można budować w praktyce?

   Tak. Przez „maszynę” Schmidhuber oznacza po prostu „program komputerowy”.

2. Czy są przynajmniej wykonalne w naszym Wszechświecie?

   Nie w obecnej formie - algorytmy są zbyt nieefektywne.

Z perspektywy dziesięciu tysięcy metrów Jürgen Schmidhuber (i byli studenci, tacy jak Marcus Hutter) badali pomysł połączenia wyszukiwania Levina z rozumowaniem bayesowskim w celu opracowania algorytmów ogólnego rozwiązywania problemów.

$n$$2^{n}$$n$$2^n$

Wykonali sporo pracy, czyniąc stałe czynniki mniej oszałamiającymi, przerażająco okropnymi i są optymistami, że ten rodzaj schematu może działać w praktyce. Jestem (w oparciu o moje doświadczenie w automatycznym dowodzeniu twierdzeń) bardzo sceptyczny, ponieważ dobre struktury danych mają kluczowe znaczenie dla dowodzenia twierdzeń, a kodowanie Goedela to okropne struktury danych.

Ale nie wiesz, że to nie zadziała, dopóki nie spróbujesz go uruchomić! W końcu żyjemy już w świecie, w którym ludzie rozwiązują problemy poprzez redukcję do SAT.