CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-disabled skin-theme-clientpref-day vector-toc-available" lang="cs" dir="ltr"> <head> <meta charset="UTF-8"> <title>Rozhodnutelnost – Wikipedie</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-disabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )cswikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":[",\t."," \t,"],"wgDigitTransformTable":["",""], "wgDefaultDateFormat":"ČSN basic dt","wgMonthNames":["","leden","únor","březen","duben","květen","červen","červenec","srpen","září","říjen","listopad","prosinec"],"wgRequestId":"104be69e-277c-4ab0-a1ab-bdfde5856a00","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Rozhodnutelnost","wgTitle":"Rozhodnutelnost","wgCurRevisionId":24225724,"wgRevisionId":24225724,"wgArticleId":196336,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Monitoring:Články s identifikátorem NKC","Monitoring:Články s identifikátorem BNF","Monitoring:Články s identifikátorem GND","Monitoring:Články s identifikátorem LCCN","Monitoring:Články s identifikátorem NLI","Monitoring:Články s identifikátorem SUDOC","Matematická logika","Neřešitelné úlohy"],"wgPageViewLanguage":"cs","wgPageContentLanguage":"cs","wgPageContentModel":"wikitext","wgRelevantPageName":"Rozhodnutelnost", "wgRelevantArticleId":196336,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"cs","pageLanguageDir":"ltr","pageVariantFallbacks":"cs"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":5000,"wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q430001","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled": true,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.WikiMiniAtlas","ext.gadget.OSMmapa","ext.gadget.direct-links-to-commons","ext.gadget.ReferenceTooltips","ext.gadget.courses","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader", "ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=cs&modules=ext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=cs&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=cs&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.5"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Rozhodnutelnost – Wikipedie"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//cs.m.wikipedia.org/wiki/Rozhodnutelnost"> <link rel="alternate" type="application/x-wiki" title="Editovat" href="/w/index.php?title=Rozhodnutelnost&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedie (cs)"> <link rel="EditURI" type="application/rsd+xml" href="//cs.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://cs.wikipedia.org/wiki/Rozhodnutelnost"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.cs"> <link rel="alternate" type="application/atom+xml" title="Atom kanál Wikipedie." href="/w/index.php?title=Speci%C3%A1ln%C3%AD:Posledn%C3%AD_zm%C4%9Bny&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Rozhodnutelnost rootpage-Rozhodnutelnost skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Přeskočit na obsah</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Projekt"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Hlavní menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Hlavní menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Hlavní menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">přesunout do postranního panelu</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">skrýt</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigace </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage" class="mw-list-item"><a href="/wiki/Hlavn%C3%AD_strana" title="Navštívit Hlavní stranu [z]" accesskey="z"><span>Hlavní strana</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/N%C3%A1pov%C4%9Bda:Obsah" title="Místo, kde najdete pomoc"><span>Nápověda</span></a></li><li id="n-helpdesk" class="mw-list-item"><a href="/wiki/Wikipedie:Pot%C5%99ebuji_pomoc" title="Pokud si nevíte rady, zeptejte se ostatních"><span>Potřebuji pomoc</span></a></li><li id="n-featuredcontent" class="mw-list-item"><a href="/wiki/Wikipedie:Nejlep%C5%A1%C3%AD_%C4%8Dl%C3%A1nky" title="Přehled článků, které jsou považovány za nejlepší na české Wikipedii"><span>Nejlepší články</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Speci%C3%A1ln%C3%AD:N%C3%A1hodn%C3%A1_str%C3%A1nka" title="Přejít na náhodně vybranou stránku [x]" accesskey="x"><span>Náhodný článek</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Speci%C3%A1ln%C3%AD:Posledn%C3%AD_zm%C4%9Bny" title="Seznam posledních změn na této wiki [r]" accesskey="r"><span>Poslední změny</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedie:Port%C3%A1l_Wikipedie" title="O projektu, jak můžete pomoci, kde hledat"><span>Komunitní portál</span></a></li><li id="n-villagepump" class="mw-list-item"><a href="/wiki/Wikipedie:Pod_l%C3%ADpou" title="Hlavní diskusní fórum"><span>Pod lípou</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Hlavn%C3%AD_strana" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedie" src="/static/images/mobile/copyright/wikipedia-wordmark-cs.svg" style="width: 7.5em; height: 1.1875em;"> <img class="mw-logo-tagline" alt="Wikipedie: Otevřená encyklopedie" src="/static/images/mobile/copyright/wikipedia-tagline-cs.svg" width="118" height="13" style="width: 7.375em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Speci%C3%A1ln%C3%AD:Hled%C3%A1n%C3%AD" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Prohledat tuto wiki [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Hledání</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Hledat na Wikipedii" aria-label="Hledat na Wikipedii" autocapitalize="sentences" title="Prohledat tuto wiki [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Speciální:Hledání"> </div> <button class="cdx-button cdx-search-input__end-button">Hledat</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Osobní nástroje"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Vzhled"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Změnit vzhled velikosti písma, šířky stránky a barvy" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Vzhled" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Vzhled</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_cs.wikipedia.org&uselang=cs" class=""><span>Podpořte Wikipedii</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Speci%C3%A1ln%C3%AD:Vytvo%C5%99it_%C3%BA%C4%8Det&returnto=Rozhodnutelnost" title="Doporučujeme vytvořit si účet a přihlásit se, ovšem není to povinné" class=""><span>Vytvoření účtu</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Speci%C3%A1ln%C3%AD:P%C5%99ihl%C3%A1sit&returnto=Rozhodnutelnost" title="Doporučujeme vám přihlásit se, ovšem není to povinné. [o]" accesskey="o" class=""><span>Přihlášení</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Další možnosti" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Osobní nástroje" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Osobní nástroje</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Uživatelské menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_cs.wikipedia.org&uselang=cs"><span>Podpořte Wikipedii</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Speci%C3%A1ln%C3%AD:Vytvo%C5%99it_%C3%BA%C4%8Det&returnto=Rozhodnutelnost" title="Doporučujeme vytvořit si účet a přihlásit se, ovšem není to povinné"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Vytvoření účtu</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Speci%C3%A1ln%C3%AD:P%C5%99ihl%C3%A1sit&returnto=Rozhodnutelnost" title="Doporučujeme vám přihlásit se, ovšem není to povinné. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Přihlášení</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Stránky pro odhlášené editory <a href="/wiki/N%C3%A1pov%C4%9Bda:%C3%9Avod" aria-label="Více informací o editování"><span>dozvědět se více</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Speci%C3%A1ln%C3%AD:Moje_p%C5%99%C3%ADsp%C4%9Bvky" title="Seznam editací provedených z této IP adresy [y]" accesskey="y"><span>Příspěvky</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Speci%C3%A1ln%C3%AD:Moje_diskuse" title="Diskuse o editacích provedených z této IP adresy [n]" accesskey="n"><span>Diskuse</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Projekt"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Obsah" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Obsah</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">přesunout do postranního panelu</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">skrýt</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(úvod)</div> </a> </li> <li id="toc-Rozhodnutelnost_logického_systému" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Rozhodnutelnost_logického_systému"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Rozhodnutelnost logického systému</span> </div> </a> <ul id="toc-Rozhodnutelnost_logického_systému-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Definice" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definice"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Definice</span> </div> </a> <button aria-controls="toc-Definice-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Přepnout podsekci Definice</span> </button> <ul id="toc-Definice-sublist" class="vector-toc-list"> <li id="toc-Rozhodnutelná_teorie" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Rozhodnutelná_teorie"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Rozhodnutelná teorie</span> </div> </a> <ul id="toc-Rozhodnutelná_teorie-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Silně_nerozhodnutelná_struktura" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Silně_nerozhodnutelná_struktura"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Silně nerozhodnutelná struktura</span> </div> </a> <ul id="toc-Silně_nerozhodnutelná_struktura-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Vlastnosti" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Vlastnosti"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Vlastnosti</span> </div> </a> <ul id="toc-Vlastnosti-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Příklady" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Příklady"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Příklady</span> </div> </a> <button aria-controls="toc-Příklady-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Přepnout podsekci Příklady</span> </button> <ul id="toc-Příklady-sublist" class="vector-toc-list"> <li id="toc-Důsledky_nerozhodnutelnosti_Robinsonovy_aritmetiky" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Důsledky_nerozhodnutelnosti_Robinsonovy_aritmetiky"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Důsledky nerozhodnutelnosti Robinsonovy aritmetiky</span> </div> </a> <ul id="toc-Důsledky_nerozhodnutelnosti_Robinsonovy_aritmetiky-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Rozhodnutelné_teorie" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Rozhodnutelné_teorie"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Rozhodnutelné teorie</span> </div> </a> <ul id="toc-Rozhodnutelné_teorie-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Odkazy" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Odkazy"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Odkazy</span> </div> </a> <button aria-controls="toc-Odkazy-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Přepnout podsekci Odkazy</span> </button> <ul id="toc-Odkazy-sublist" class="vector-toc-list"> <li id="toc-Související_články" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Související_články"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Související články</span> </div> </a> <ul id="toc-Související_články-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Literatura" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Literatura"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.2</span> <span>Literatura</span> </div> </a> <ul id="toc-Literatura-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Obsah" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Přepnout obsah" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Přepnout obsah</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Rozhodnutelnost</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Přejděte k článku v jiném jazyce. Je dostupný v 15 jazycích" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-15" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">15 jazyků</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Decidibilitat" title="Decidibilitat – katalánština" lang="ca" hreflang="ca" data-title="Decidibilitat" data-language-autonym="Català" data-language-local-name="katalánština" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/Decidability_(logic)" title="Decidability (logic) – angličtina" lang="en" hreflang="en" data-title="Decidability (logic)" data-language-autonym="English" data-language-local-name="angličtina" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Decidibilidad" title="Decidibilidad – španělština" lang="es" hreflang="es" data-title="Decidibilidad" data-language-autonym="Español" data-language-local-name="španělština" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AA%D8%B5%D9%85%DB%8C%D9%85%E2%80%8C%D9%BE%D8%B0%DB%8C%D8%B1%DB%8C_(%D9%85%D9%86%D8%B7%D9%82)" title="تصمیم‌پذیری (منطق) – perština" lang="fa" hreflang="fa" data-title="تصمیم‌پذیری (منطق)" data-language-autonym="فارسی" data-language-local-name="perština" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/D%C3%A9cidabilit%C3%A9" title="Décidabilité – francouzština" lang="fr" hreflang="fr" data-title="Décidabilité" data-language-autonym="Français" data-language-local-name="francouzština" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%9B%D7%A8%D7%99%D7%A2%D7%95%D7%AA" title="כריעות – hebrejština" lang="he" hreflang="he" data-title="כריעות" data-language-autonym="עברית" data-language-local-name="hebrejština" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Decidibilit%C3%A0" title="Decidibilità – italština" lang="it" hreflang="it" data-title="Decidibilità" data-language-autonym="Italiano" data-language-local-name="italština" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E6%B1%BA%E5%AE%9A%E5%8F%AF%E8%83%BD%E6%80%A7" title="決定可能性 – japonština" lang="ja" hreflang="ja" data-title="決定可能性" data-language-autonym="日本語" data-language-local-name="japonština" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95%EA%B0%80%EB%8A%A5%EC%84%B1" title="결정가능성 – korejština" lang="ko" hreflang="ko" data-title="결정가능성" data-language-autonym="한국어" data-language-local-name="korejština" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Rozstrzygalno%C5%9B%C4%87" title="Rozstrzygalność – polština" lang="pl" hreflang="pl" data-title="Rozstrzygalność" data-language-autonym="Polski" data-language-local-name="polština" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Decidibilidade" title="Decidibilidade – portugalština" lang="pt" hreflang="pt" data-title="Decidibilidade" data-language-autonym="Português" data-language-local-name="portugalština" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C" title="Алгоритмическая разрешимость – ruština" lang="ru" hreflang="ru" data-title="Алгоритмическая разрешимость" data-language-autonym="Русский" data-language-local-name="ruština" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sl mw-list-item"><a href="https://sl.wikipedia.org/wiki/Odlo%C4%8Dljivost" title="Odločljivost – slovinština" lang="sl" hreflang="sl" data-title="Odločljivost" data-language-autonym="Slovenščina" data-language-local-name="slovinština" class="interlanguage-link-target"><span>Slovenščina</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%9E%D0%B4%D0%BB%D1%83%D1%87%D0%B8%D0%B2%D0%BE%D1%81%D1%82" title="Одлучивост – srbština" lang="sr" hreflang="sr" data-title="Одлучивост" data-language-autonym="Српски / srpski" data-language-local-name="srbština" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%96%D1%87%D0%BD%D0%B0_%D1%80%D0%BE%D0%B7%D0%B2%27%D1%8F%D0%B7%D0%BD%D1%96%D1%81%D1%82%D1%8C" title="Алгоритмічна розв'язність – ukrajinština" lang="uk" hreflang="uk" data-title="Алгоритмічна розв'язність" data-language-autonym="Українська" data-language-local-name="ukrajinština" class="interlanguage-link-target"><span>Українська</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q430001#sitelinks-wikipedia" title="Editovat mezijazykové odkazy" class="wbc-editpage">Upravit odkazy</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Jmenné prostory"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Rozhodnutelnost" title="Zobrazit obsahovou stránku [c]" accesskey="c"><span>Článek</span></a></li><li id="ca-talk" class="new vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Diskuse:Rozhodnutelnost&action=edit&redlink=1" rel="discussion" class="new" title="Diskuse ke stránce (stránka neexistuje) [t]" accesskey="t"><span>Diskuse</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Změnit variantu jazyka" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">čeština</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Zobrazení"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Rozhodnutelnost"><span>Číst</span></a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit" title="Editovat tuto stránku [v]" accesskey="v"><span>Editovat</span></a></li><li id="ca-edit" class="collapsible vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Rozhodnutelnost&action=edit" title="Editovat zdrojový kód této stránky [e]" accesskey="e"><span>Editovat zdroj</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Rozhodnutelnost&action=history" title="Starší verze této stránky. [h]" accesskey="h"><span>Zobrazit historii</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Nástroje ke stránce"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Nástroje" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Nástroje</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Nástroje</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">přesunout do postranního panelu</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">skrýt</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Další možnosti" > <div class="vector-menu-heading"> Akce </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Rozhodnutelnost"><span>Číst</span></a></li><li id="ca-more-ve-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit" title="Editovat tuto stránku [v]" accesskey="v"><span>Editovat</span></a></li><li id="ca-more-edit" class="collapsible vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Rozhodnutelnost&action=edit" title="Editovat zdrojový kód této stránky [e]" accesskey="e"><span>Editovat zdroj</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Rozhodnutelnost&action=history"><span>Zobrazit historii</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> Obecné </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Speci%C3%A1ln%C3%AD:Co_odkazuje_na/Rozhodnutelnost" title="Seznam všech wikistránek, které sem odkazují [j]" accesskey="j"><span>Odkazuje sem</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Speci%C3%A1ln%C3%AD:Souvisej%C3%ADc%C3%AD_zm%C4%9Bny/Rozhodnutelnost" rel="nofollow" title="Nedávné změny stránek, na které je odkazováno [k]" accesskey="k"><span>Související změny</span></a></li><li id="t-upload" class="mw-list-item"><a href="//commons.wikimedia.org/wiki/Special:UploadWizard?uselang=cs" title="Nahrát obrázky či jiná multimédia [u]" accesskey="u"><span>Načíst soubor</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Speci%C3%A1ln%C3%AD:Speci%C3%A1ln%C3%AD_str%C3%A1nky" title="Seznam všech speciálních stránek [q]" accesskey="q"><span>Speciální stránky</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Rozhodnutelnost&oldid=24225724" title="Trvalý odkaz na současnou verzi této stránky"><span>Trvalý odkaz</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Rozhodnutelnost&action=info" title="Více informací o této stránce"><span>Informace o stránce</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Speci%C3%A1ln%C3%AD:Citovat&page=Rozhodnutelnost&id=24225724&wpFormIdentifier=titleform" title="Informace o tom, jak citovat tuto stránku"><span>Citovat stránku</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Speci%C3%A1ln%C3%AD:UrlShortener&url=https%3A%2F%2Fcs.wikipedia.org%2Fwiki%2FRozhodnutelnost"><span>Získat zkrácené URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Speci%C3%A1ln%C3%AD:QrCode&url=https%3A%2F%2Fcs.wikipedia.org%2Fwiki%2FRozhodnutelnost"><span>Stáhnout QR kód</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Tisk/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-create_a_book" class="mw-list-item"><a href="/w/index.php?title=Speci%C3%A1ln%C3%AD:Kniha&bookcmd=book_creator&referer=Rozhodnutelnost"><span>Vytvořit knihu</span></a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Speci%C3%A1ln%C3%AD:DownloadAsPdf&page=Rozhodnutelnost&action=show-download-screen"><span>Stáhnout jako PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Rozhodnutelnost&printable=yes" title="Tato stránka v podobě vhodné k tisku [p]" accesskey="p"><span>Verze k tisku</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> Na jiných projektech </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q430001" title="Odkaz na propojenou položku datového úložiště [g]" accesskey="g"><span>Položka Wikidat</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Nástroje ke stránce"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Vzhled"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Vzhled</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">přesunout do postranního panelu</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">skrýt</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">Z Wikipedie, otevřené encyklopedie</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="cs" dir="ltr"><p><b>Rozhodnutelnost</b> (<i>A</i> je - není větší, než <i>B</i>, formule <i>W</i> je pravdivá – nepravdivá, <i>a</i> je - není prvkem množiny <i>Y</i>, Turingův stroj zastaví - nezastaví...) je vlastnost <a href="/wiki/Exaktn%C3%AD" title="Exaktní">exaktního</a> světa (matematika, geometrie, Turingův stroj, exaktní hry např. šachy,...), v němž veškeré entity mají exaktní interpretaci. Rozhodnutelnost nelze instalovat v mlze vágnosti přirozeného světa vágní, emocionální a subjektivní lidské psýchy, používající přirozený jazyk s vágní (vnitřní <a href="/wiki/V%C3%A1gnost" title="Vágnost">vágnost</a>), emocionální a subjektivní interpretací měnící se od člověka k člověku a u každého z nich v čase, které se říká <a href="/wiki/Konotace" title="Konotace">konotace</a>. Nemůže proto existovat např. logika postavená nad přirozeným <a href="/wiki/Jazyk_(lingvistika)" title="Jazyk (lingvistika)">jazykem</a>, může existovat pouze formální logika postavená nad umělým formálním jazykem, který má z principu exaktní (s nulovou vnitřní vágností) interpretaci. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading3"><h3 id="Rozhodnutelnost_logického_systému"><span id="Rozhodnutelnost_logick.C3.A9ho_syst.C3.A9mu"></span>Rozhodnutelnost logického systému</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit&section=1" title="Editace sekce: Rozhodnutelnost logického systému" class="mw-editsection-visualeditor"><span>editovat</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Rozhodnutelnost&action=edit&section=1" title="Editovat zdrojový kód sekce Rozhodnutelnost logického systému"><span>editovat zdroj</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Rozhodnutelnost je <a href="/wiki/Matematika" title="Matematika">matematický</a> pojem z oblasti <a href="/wiki/Matematick%C3%A1_logika" title="Matematická logika">matematické logiky</a>. Vyjadřuje, zda existuje konečný <a href="/wiki/Algoritmus" title="Algoritmus">algoritmus</a>, který pro každou <a href="/wiki/Formule_(logika)" title="Formule (logika)">formuli</a> určí, zda je v dané <a href="/wiki/Teorie_(logika)" class="mw-redirect" title="Teorie (logika)">teorii</a> <a href="/wiki/Form%C3%A1ln%C3%AD_d%C5%AFkaz" class="mw-redirect" title="Formální důkaz">dokazatelná</a> nebo není. Teorie, pro niž takový algoritmus existuje, se nazývá <b>rozhodnutelná</b>, v opačném případě pak <b>nerozhodnutelná</b>. Problematika rozhodnutelnosti úzce souvisí s <a href="/wiki/G%C3%B6delovy_v%C4%9Bty_o_ne%C3%BAplnosti" title="Gödelovy věty o neúplnosti">Gödelovými větami o neúplnosti</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Definice">Definice</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit&section=2" title="Editace sekce: Definice" class="mw-editsection-visualeditor"><span>editovat</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Rozhodnutelnost&action=edit&section=2" title="Editovat zdrojový kód sekce Definice"><span>editovat zdroj</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Rozhodnutelná_teorie"><span id="Rozhodnuteln.C3.A1_teorie"></span>Rozhodnutelná teorie</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit&section=3" title="Editace sekce: Rozhodnutelná teorie" class="mw-editsection-visualeditor"><span>editovat</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Rozhodnutelnost&action=edit&section=3" title="Editovat zdrojový kód sekce Rozhodnutelná teorie"><span>editovat zdroj</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Teorie je rozhodnutelná, pokud <a href="/wiki/Mno%C5%BEina" title="Množina">množina</a> všech <a href="/wiki/Formule_(logika)" title="Formule (logika)">formulí</a> v ní dokazatelných je <a href="/wiki/Rekurzivn%C3%AD_mno%C5%BEina" class="mw-redirect" title="Rekurzivní množina">rekurzivní</a>. Není-li teorie rozhodnutelná, nazývá se nerozhodnutelná. </p> <div class="mw-heading mw-heading3"><h3 id="Silně_nerozhodnutelná_struktura"><span id="Siln.C4.9B_nerozhodnuteln.C3.A1_struktura"></span>Silně nerozhodnutelná struktura</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit&section=4" title="Editace sekce: Silně nerozhodnutelná struktura" class="mw-editsection-visualeditor"><span>editovat</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Rozhodnutelnost&action=edit&section=4" title="Editovat zdrojový kód sekce Silně nerozhodnutelná struktura"><span>editovat zdroj</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><a href="/wiki/Model_(logika)" title="Model (logika)">Struktura</a> se nazývá silně nerozhodnutelná, je-li nerozhodnutelná každá teorie, která ji má za <a href="/wiki/Model_(logika)" title="Model (logika)">model</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Vlastnosti">Vlastnosti</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit&section=5" title="Editace sekce: Vlastnosti" class="mw-editsection-visualeditor"><span>editovat</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Rozhodnutelnost&action=edit&section=5" title="Editovat zdrojový kód sekce Vlastnosti"><span>editovat zdroj</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Rozhodnutelnost či nerozhodnutelnost se přenáší mezi teoriemi, mezi nimiž je určitý vztah. Nejpoužívanější tvrzení, která o tomto hovoří, jsou následující: </p> <ul><li>Rozšíření rozhodnutelné teorie o konečně mnoho <a href="/wiki/Axiom" title="Axiom">axiomů</a> v témže <a href="/wiki/Jazyk_(logika)" title="Jazyk (logika)">jazyce</a> je rozhodnutelné.</li> <li>Rozšíření rozhodnutelné teorie o definice je rozhodnutelné.</li> <li>Teorie, v níž je <a href="/w/index.php?title=Interpretace_(logika)&action=edit&redlink=1" class="new" title="Interpretace (logika) (stránka neexistuje)">interpretovatelná</a> nerozhodnutelná teorie, je také nerozhodnutelná.</li> <li><a href="/w/index.php?title=Konzervativn%C3%AD_roz%C5%A1%C3%AD%C5%99en%C3%AD&action=edit&redlink=1" class="new" title="Konzervativní rozšíření (stránka neexistuje)">Konzervativní rozšíření</a> nerozhodnutelné teorie je nerozhodnutelné.</li></ul> <p>O silně nerozhodnutelných strukturách platí: </p> <ul><li>Je-li v nějaké struktuře definovatelná silně nerozhodnutelná struktura, pak je tato struktura také silně nerozhodnutelná.</li></ul> <p>Dále se často používá: </p> <ul><li>Rekurzivně axiomatizovatelná nerozhodnutelná teorie je <a href="/w/index.php?title=Ne%C3%BApln%C3%A1_teorie&action=edit&redlink=1" class="new" title="Neúplná teorie (stránka neexistuje)">neúplná</a>.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Příklady"><span id="P.C5.99.C3.ADklady"></span>Příklady</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit&section=6" title="Editace sekce: Příklady" class="mw-editsection-visualeditor"><span>editovat</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Rozhodnutelnost&action=edit&section=6" title="Editovat zdrojový kód sekce Příklady"><span>editovat zdroj</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Důsledky_nerozhodnutelnosti_Robinsonovy_aritmetiky"><span id="D.C5.AFsledky_nerozhodnutelnosti_Robinsonovy_aritmetiky"></span>Důsledky nerozhodnutelnosti Robinsonovy aritmetiky</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit&section=7" title="Editace sekce: Důsledky nerozhodnutelnosti Robinsonovy aritmetiky" class="mw-editsection-visualeditor"><span>editovat</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Rozhodnutelnost&action=edit&section=7" title="Editovat zdrojový kód sekce Důsledky nerozhodnutelnosti Robinsonovy aritmetiky"><span>editovat zdroj</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><a href="/wiki/Robinsonova_aritmetika" title="Robinsonova aritmetika">Robinsonova aritmetika</a> je nerozhodnutelná teorie. Dokonce každé <a href="/wiki/Bezesporn%C3%A1_teorie" title="Bezesporná teorie">bezesporné</a> rozšíření Robinsonovy aritmetiky je nerozhodnutelné. Tato dvě tvrzení mají mnoho důsledků: </p> <ul><li>Protože je Robinsonova aritmetika konečně <a href="/wiki/Axiom" title="Axiom">axiomatizovatelná</a>, je nerozhodnutelná také prázdná teorie v <a href="/wiki/Jazyk_aritmetiky" class="mw-redirect" title="Jazyk aritmetiky">jazyce aritmetiky</a>.</li> <li><a href="/wiki/Peanova_aritmetika" title="Peanova aritmetika">Peanova aritmetika</a> je nerozhodnutelná a protože je <a href="/w/index.php?title=Rekurzivn%C4%9B_axiomatizovateln%C3%A1_teorie&action=edit&redlink=1" class="new" title="Rekurzivně axiomatizovatelná teorie (stránka neexistuje)">rekurzivně axiomatizovatelná</a>, je <a href="/w/index.php?title=Ne%C3%BApln%C3%A1_teorie&action=edit&redlink=1" class="new" title="Neúplná teorie (stránka neexistuje)">neúplná</a>.</li> <li>Standardní model aritmetiky (struktura <a href="/wiki/P%C5%99irozen%C3%A9_%C4%8D%C3%ADslo" title="Přirozené číslo">přirozených čísel</a>) je silně nerozhodnutelná struktura.</li> <li>Teorie standardního modelu (jejími axiomy jsou všechny formule platné ve standardním modelu) je nerozhodnutelná, protože je však úplná, nemůže být rekurzivně axiomatizovatelná.</li> <li>Protože jsou přirozená čísla definovatelná v <a href="/wiki/Cel%C3%A9_%C4%8D%C3%ADslo" title="Celé číslo">celých</a> (např. pomocí <a href="/wiki/Lagrangeova_v%C4%9Bta_o_%C4%8Dty%C5%99ech_%C4%8Dtverc%C3%ADch" title="Lagrangeova věta o čtyřech čtvercích">Lagrangeovy věty o čtyřech čtvercích</a>) a celá v <a href="/wiki/Racion%C3%A1ln%C3%AD_%C4%8D%C3%ADslo" title="Racionální číslo">racionálních</a>, jsou struktury celých a racionálních čísel také silně nerozhodnutelné struktury. Odtud dále plyne: <ul><li>Teorie <a href="/wiki/Okruh_(algebra)" title="Okruh (algebra)">okruhů</a>, <a href="/wiki/Komutativita" title="Komutativita">komutativních</a> okruhů, <a href="/wiki/Obor_integrity" title="Obor integrity">oborů integrity</a>, <a href="/wiki/T%C4%9Bleso_(algebra)" title="Těleso (algebra)">těles</a>, komutativních těles či těles <a href="/wiki/Charakteristika_t%C4%9Blesa" class="mw-redirect" title="Charakteristika tělesa">charakteristiky 0</a>, jsou nerozhodnutelné.</li></ul></li></ul> <div class="mw-heading mw-heading3"><h3 id="Rozhodnutelné_teorie"><span id="Rozhodnuteln.C3.A9_teorie"></span>Rozhodnutelné teorie</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit&section=8" title="Editace sekce: Rozhodnutelné teorie" class="mw-editsection-visualeditor"><span>editovat</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Rozhodnutelnost&action=edit&section=8" title="Editovat zdrojový kód sekce Rozhodnutelné teorie"><span>editovat zdroj</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Následující teorie jsou rozhodnutelné: </p> <ul><li>teorie <a href="/wiki/Hust%C3%A9_uspo%C5%99%C3%A1d%C3%A1n%C3%AD" title="Husté uspořádání">hustých</a> <a href="/wiki/Line%C3%A1rn%C3%AD_uspo%C5%99%C3%A1d%C3%A1n%C3%AD" class="mw-redirect" title="Lineární uspořádání">lineárních uspořádání</a></li> <li>teorie <a href="/wiki/Abelovsk%C3%A1_grupa" class="mw-redirect" title="Abelovská grupa">abelovských grup</a></li> <li>teorie <a href="/wiki/Booleova_algebra" title="Booleova algebra">booleových algeber</a></li> <li>teorie <a href="/wiki/Algebraicky_uzav%C5%99en%C3%A9_t%C4%9Bleso" title="Algebraicky uzavřené těleso">algebraicky uzavřených těles</a></li> <li><a href="/wiki/Presburgerova_aritmetika" title="Presburgerova aritmetika">Presburgerova aritmetika</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Odkazy">Odkazy</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit&section=9" title="Editace sekce: Odkazy" class="mw-editsection-visualeditor"><span>editovat</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Rozhodnutelnost&action=edit&section=9" title="Editovat zdrojový kód sekce Odkazy"><span>editovat zdroj</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Související_články"><span id="Souvisej.C3.ADc.C3.AD_.C4.8Dl.C3.A1nky"></span>Související články</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit&section=10" title="Editace sekce: Související články" class="mw-editsection-visualeditor"><span>editovat</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Rozhodnutelnost&action=edit&section=10" title="Editovat zdrojový kód sekce Související články"><span>editovat zdroj</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Rekurzivn%C3%AD_mno%C5%BEina" class="mw-redirect" title="Rekurzivní množina">Rekurzivní množina</a></li> <li><a href="/wiki/G%C3%B6delovy_v%C4%9Bty_o_ne%C3%BAplnosti" title="Gödelovy věty o neúplnosti">Gödelovy věty o neúplnosti</a></li></ul> <div class="mw-heading mw-heading3"><h3 id="Literatura">Literatura</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Rozhodnutelnost&veaction=edit&section=11" title="Editace sekce: Literatura" class="mw-editsection-visualeditor"><span>editovat</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Rozhodnutelnost&action=edit&section=11" title="Editovat zdrojový kód sekce Literatura"><span>editovat zdroj</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><cite class="book" style="font-style:normal;"><a href="/w/index.php?title=V%C3%ADt%C4%9Bzslav_%C5%A0vejdar&action=edit&redlink=1" class="new" title="Vítězslav Švejdar (stránka neexistuje)">ŠVEJDAR, Vítězslav</a>. <i>Logika, neúplnost, složitost a nutnost</i>. Praha: Academia, 2002. <span style="white-space:nowrap"><a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Speci%C3%A1ln%C3%AD:Zdroje_knih/80-200-1005-X" title="Speciální:Zdroje knih/80-200-1005-X"><span class="ISBN">80-200-1005-X</span></a></span>.</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/cs.wikipedia.org:templatecitacemonografie&rft.btitle=Logika%2C+ne%C3%BAplnost%2C+slo%C5%BEitost+a+nutnost&rft.isbn=80-200-1005-X&rft.aulast=%C5%A0vejdar&rft.aufirst=V%C3%ADt%C4%9Bzslav&rft.place=Praha&rft.pub=Academia&rft.date=2002"><span style="display:none"> </span></span></li></ul> <style data-mw-deduplicate="TemplateStyles:r23078045">.mw-parser-output .navbox2{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox2 .navbox2{margin-top:0}.mw-parser-output .navbox2+.navbox2{margin-top:-1px}.mw-parser-output .navbox2-inner,.mw-parser-output .navbox2-subgroup{width:100%}.mw-parser-output .navbox2-group,.mw-parser-output .navbox2-title,.mw-parser-output .navbox2-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output th.navbox2-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox2,.mw-parser-output .navbox2-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox2-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output tr+tr>.navbox2-abovebelow,.mw-parser-output tr+tr>.navbox2-group,.mw-parser-output tr+tr>.navbox2-image,.mw-parser-output tr+tr>.navbox2-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox2 th,.mw-parser-output .navbox2-title{background-color:#e0e0e0}.mw-parser-output .navbox2-abovebelow,.mw-parser-output th.navbox2-group,.mw-parser-output .navbox2-subgroup .navbox2-title{background-color:#e7e7e7}.mw-parser-output .navbox2-subgroup .navbox2-title{font-size:88%}.mw-parser-output .navbox2-subgroup .navbox2-group,.mw-parser-output .navbox2-subgroup .navbox2-abovebelow{background-color:#f0f0f0}.mw-parser-output .navbox2-even{background-color:#f7f7f7}.mw-parser-output .navbox2-odd{background-color:transparent}.mw-parser-output .navbox2 .hlist td dl,.mw-parser-output .navbox2 .hlist td ol,.mw-parser-output .navbox2 .hlist td ul,.mw-parser-output .navbox2 td.hlist dl,.mw-parser-output .navbox2 td.hlist ol,.mw-parser-output .navbox2 td.hlist ul{padding:0.125em 0}</style><div role="navigation" class="navbox2" aria-labelledby="Autoritní_data_frameless_&#124;text-top_&#124;10px_&#124;alt=Editovat_na_Wikidatech_&#124;link=https&#58;//www.wikidata.org/wiki/Q430001#identifiers&#124;Editovat_na_Wikidatech" style="padding:2px"><table class="nowraplinks hlist navbox2-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th id="Autoritní_data_frameless_&#124;text-top_&#124;10px_&#124;alt=Editovat_na_Wikidatech_&#124;link=https&#58;//www.wikidata.org/wiki/Q430001#identifiers&#124;Editovat_na_Wikidatech" scope="row" class="navbox2-group" style="width:1%"><a href="/wiki/Autoritn%C3%AD_kontrola" title="Autoritní kontrola">Autoritní data</a> <span class="mw-valign-text-top" typeof="mw:File/Frameless"><a href="https://www.wikidata.org/wiki/Q430001#identifiers" title="Editovat na Wikidatech"><img alt="Editovat na Wikidatech" src="//upload.wikimedia.org/wikipedia/commons/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/10px-OOjs_UI_icon_edit-ltr-progressive.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/15px-OOjs_UI_icon_edit-ltr-progressive.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/20px-OOjs_UI_icon_edit-ltr-progressive.svg.png 2x" data-file-width="20" data-file-height="20" /></a></span></th><td class="navbox2-list navbox2-odd" style="text-align:left;border-left-width:2px;border-left-style:solid;width:100%;padding:0px"><div style="padding:0em 0.25em"> <ul><li><span class="nowrap"><a href="/wiki/N%C3%A1rodn%C3%AD_knihovna_%C4%8Cesk%C3%A9_republiky" title="Národní knihovna České republiky">NKC</a>: <span class="uid"><a rel="nofollow" class="external text" href="https://aleph.nkp.cz/F/?func=find-c&local_base=aut&ccl_term=ica=ph1231409">ph1231409</a></span></span></li> <li><span class="nowrap"><a href="/wiki/Francouzsk%C3%A1_n%C3%A1rodn%C3%AD_knihovna" title="Francouzská národní knihovna">BNF</a>: <span class="uid"><a rel="nofollow" class="external text" href="https://catalogue.bnf.fr/ark:/12148/cb119818468">cb119818468</a> <a rel="nofollow" class="external text" href="https://data.bnf.fr/ark:/12148/cb119818468">(data)</a></span></span></li> <li><span class="nowrap"><a href="/wiki/Gemeinsame_Normdatei" title="Gemeinsame Normdatei">GND</a>: <span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4152398-2">4152398-2</a></span></span></li> <li><span class="nowrap"><a href="/wiki/Library_of_Congress_Control_Number" title="Library of Congress Control Number">LCCN</a>: <span class="uid"><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/subjects/sh85036191">sh85036191</a></span></span></li> <li><span class="nowrap"><a href="/wiki/N%C3%A1rodn%C3%AD_knihovna_Izraele" title="Národní knihovna Izraele">NLI</a>: <span class="uid"><a rel="nofollow" class="external text" href="http://olduli.nli.org.il/F/?func=find-b&local_base=NLX10&find_code=UID&request=987007545768505171">987007545768505171</a></span></span></li> <li><span class="nowrap"><a href="/wiki/Univerzitn%C3%AD_syst%C3%A9m_dokumentace" title="Univerzitní systém dokumentace">SUDOC</a>: <span class="uid"><a rel="nofollow" class="external text" href="https://www.idref.fr/027868664">027868664</a></span></span></li></ul> </div></td></tr></tbody></table></div> <style data-mw-deduplicate="TemplateStyles:r16915398">.mw-parser-output div/**/#portallinks a{font-weight:bold}</style><div id="portallinks" class="catlinks"><a href="/wiki/Port%C3%A1l:Obsah" title="Portál:Obsah">Portály</a>: <a href="/wiki/Port%C3%A1l:Matematika" title="Portál:Matematika">Matematika</a> </div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1&useformat=desktop" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Citováno z „<a dir="ltr" href="https://cs.wikipedia.org/w/index.php?title=Rozhodnutelnost&oldid=24225724">https://cs.wikipedia.org/w/index.php?title=Rozhodnutelnost&oldid=24225724</a>“</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/N%C3%A1pov%C4%9Bda:Kategorie" title="Nápověda:Kategorie">Kategorie</a>: <ul><li><a href="/wiki/Kategorie:Matematick%C3%A1_logika" title="Kategorie:Matematická logika">Matematická logika</a></li><li><a href="/wiki/Kategorie:Ne%C5%99e%C5%A1iteln%C3%A9_%C3%BAlohy" title="Kategorie:Neřešitelné úlohy">Neřešitelné úlohy</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Skryté kategorie: <ul><li><a href="/wiki/Kategorie:Monitoring:%C4%8Cl%C3%A1nky_s_identifik%C3%A1torem_NKC" title="Kategorie:Monitoring:Články s identifikátorem NKC">Monitoring:Články s identifikátorem NKC</a></li><li><a href="/wiki/Kategorie:Monitoring:%C4%8Cl%C3%A1nky_s_identifik%C3%A1torem_BNF" title="Kategorie:Monitoring:Články s identifikátorem BNF">Monitoring:Články s identifikátorem BNF</a></li><li><a href="/wiki/Kategorie:Monitoring:%C4%8Cl%C3%A1nky_s_identifik%C3%A1torem_GND" title="Kategorie:Monitoring:Články s identifikátorem GND">Monitoring:Články s identifikátorem GND</a></li><li><a href="/wiki/Kategorie:Monitoring:%C4%8Cl%C3%A1nky_s_identifik%C3%A1torem_LCCN" title="Kategorie:Monitoring:Články s identifikátorem LCCN">Monitoring:Články s identifikátorem LCCN</a></li><li><a href="/wiki/Kategorie:Monitoring:%C4%8Cl%C3%A1nky_s_identifik%C3%A1torem_NLI" title="Kategorie:Monitoring:Články s identifikátorem NLI">Monitoring:Články s identifikátorem NLI</a></li><li><a href="/wiki/Kategorie:Monitoring:%C4%8Cl%C3%A1nky_s_identifik%C3%A1torem_SUDOC" title="Kategorie:Monitoring:Články s identifikátorem SUDOC">Monitoring:Články s identifikátorem SUDOC</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> Stránka byla naposledy editována 9. 9. 2024 v 10:41.</li> <li id="footer-info-copyright">Text je dostupný pod <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.cs">licencí Creative Commons Uveďte původ – Zachovejte licenci</a>, případně za dalších podmínek. Podrobnosti naleznete na stránce <a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Terms_of_Use/cs">Podmínky užití</a>.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Ochrana osobních údajů</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedie">O Wikipedii</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedie:Vylou%C4%8Den%C3%AD_odpov%C4%9Bdnosti">Vyloučení odpovědnosti</a></li> <li id="footer-places-contact"><a href="//cs.wikipedia.org/wiki/Wikipedie:Kontakt">Kontaktujte Wikipedii</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Kodex chování</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Vývojáři</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/cs.wikipedia.org">Statistiky</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Prohlášení o cookies</a></li> <li id="footer-places-mobileview"><a href="//cs.m.wikipedia.org/w/index.php?title=Rozhodnutelnost&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobilní verze</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-78f4c97c5d-8skxp","wgBackendResponseTime":171,"wgPageParseReport":{"limitreport":{"cputime":"0.109","walltime":"0.141","ppvisitednodes":{"value":194,"limit":1000000},"postexpandincludesize":{"value":7094,"limit":2097152},"templateargumentsize":{"value":395,"limit":2097152},"expansiondepth":{"value":6,"limit":100},"expensivefunctioncount":{"value":6,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":1988,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 109.914 1 -total"," 68.45% 75.234 1 Šablona:Autoritní_data"," 27.26% 29.965 1 Šablona:Citace_monografie"," 4.05% 4.452 1 Šablona:Portály"]},"scribunto":{"limitreport-timeusage":{"value":"0.038","limit":"10.000"},"limitreport-memusage":{"value":1258137,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-59bbd5969d-dtw69","timestamp":"20241128214232","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Rozhodnutelnost","url":"https:\/\/cs.wikipedia.org\/wiki\/Rozhodnutelnost","sameAs":"http:\/\/www.wikidata.org\/entity\/Q430001","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q430001","author":{"@type":"Organization","name":"P\u0159isp\u011bvatel\u00e9 projekt\u016f Wikimedia"},"publisher":{"@type":"Organization","name":"nadace Wikimedia","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2007-04-01T22:05:59Z","dateModified":"2024-09-09T09:41:48Z","headline":"matematick\u00fd pojem z oblasti matematick\u00e9 logiky"}</script> </body> </html>