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="ro" dir="ltr"> <head> <meta charset="UTF-8"> <title>Teoria computației - Wikipedia</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(/(?:^|; )rowikimwclientpreferences=([^;]+)/);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":"dmy","wgMonthNames":["","ianuarie","februarie","martie","aprilie","mai","iunie","iulie","august","septembrie","octombrie","noiembrie","decembrie"],"wgRequestId":"2a0672f0-9655-421f-9822-0b766ca0f312","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Teoria_computației","wgTitle":"Teoria computației","wgCurRevisionId":15748718,"wgRevisionId":15748718,"wgArticleId":1999816,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Pagini cu citări cu argumente redundante","Pagini cu legături externe nefuncționale","Webarchive template wayback links","Pagini ce folosesc legături automate către ISBN","Informatică teoretică"],"wgPageViewLanguage":"ro","wgPageContentLanguage":"ro","wgPageContentModel":"wikitext","wgRelevantPageName":"Teoria_computației","wgRelevantArticleId":1999816,"wgTempUserName":null,"wgIsProbablyEditable":true, "wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":true,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"ro","pageLanguageDir":"ltr","pageVariantFallbacks":"ro"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q844718","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false, "wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false,"wgSiteNoticeId":"2.2"};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","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","ext.dismissableSiteNotice.styles":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","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","ext.dismissableSiteNotice"];</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=ro&modules=ext.cite.styles%7Cext.dismissableSiteNotice.styles%7Cext.math.styles%7Cext.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=ro&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=ro&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <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 property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/1200px-Maquina.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="667"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/800px-Maquina.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="444"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/640px-Maquina.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="356"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Teoria computației - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//ro.m.wikipedia.org/wiki/Teoria_computa%C8%9Biei"> <link rel="alternate" type="application/x-wiki" title="Modificare" href="/w/index.php?title=Teoria_computa%C8%9Biei&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="Wikipedia (ro)"> <link rel="EditURI" type="application/rsd+xml" href="//ro.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://ro.wikipedia.org/wiki/Teoria_computa%C8%9Biei"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.ro"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Abonare Atom" href="/w/index.php?title=Special:Schimb%C4%83ri_recente&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-Teoria_computației rootpage-Teoria_computației skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Sari la conținut</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="Site"> <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="Meniul principal" > <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">Meniul principal</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">Meniul principal</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">mută în bara laterală</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">ascunde</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigare </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage" class="mw-list-item"><a href="/wiki/Pagina_principal%C4%83" title="Vedeți pagina principală [z]" accesskey="z"><span>Pagina principală</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:Schimb%C4%83ri_recente" title="Lista ultimelor schimbări realizate în acest wiki [r]" accesskey="r"><span>Schimbări recente</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Wikipedia:Cafenea" title="Informații despre evenimentele curente"><span>Cafenea</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Aleatoriu" title="Afișează o pagină aleatoare [x]" accesskey="x"><span>Articol aleatoriu</span></a></li><li id="n-Facebook" class="mw-list-item"><a href="https://www.facebook.com/WikipediaRomana" rel="nofollow"><span>Facebook</span></a></li> </ul> </div> </div> <div id="p-Participare" class="vector-menu mw-portlet mw-portlet-Participare" > <div class="vector-menu-heading"> Participare </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-Cum-încep-pe-Wikipedia" class="mw-list-item"><a href="/wiki/Ajutor:Bun_venit"><span>Cum încep pe Wikipedia</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/Ajutor:Cuprins" title="Locul în care găsiți ajutor"><span>Ajutor</span></a></li><li id="n-Portals" class="mw-list-item"><a href="/wiki/Portal:R%C4%83sfoire"><span>Portaluri tematice</span></a></li><li id="n-Articole-cerute" class="mw-list-item"><a href="/wiki/Wikipedia:Articole_cerute"><span>Articole cerute</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Pagina_principal%C4%83" 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="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="enciclopedia liberă" src="/static/images/mobile/copyright/wikipedia-tagline-ro.svg" width="120" height="13" style="width: 7.5em; 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/Special:C%C4%83utare" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Căutare în Wikipedia [c]" accesskey="c"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Căutare</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="Căutare în Wikipedia" aria-label="Căutare în Wikipedia" autocapitalize="sentences" title="Căutare în Wikipedia [c]" accesskey="c" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Căutare"> </div> <button class="cdx-button cdx-search-input__end-button">Căutare</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Unelte personale"> <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="Aspect"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <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="Aspect" > <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">Aspect</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_ro.wikipedia.org&uselang=ro" class=""><span>Donații</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=Special:%C3%8Enregistrare&returnto=Teoria+computa%C8%9Biei" title="Vă încurajăm să vă creați un cont și să vă autentificați; totuși, nu este obligatoriu" class=""><span>Creare cont</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=Special:Autentificare&returnto=Teoria+computa%C8%9Biei" title="Sunteți încurajat să vă autentificați, deși acest lucru nu este obligatoriu. [o]" accesskey="o" class=""><span>Autentificare</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 user-links-collapsible-item" title="Mai multe opțiuni" > <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="Unelte personale" > <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">Unelte personale</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Meniul de utilizator" > <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_ro.wikipedia.org&uselang=ro"><span>Donații</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:%C3%8Enregistrare&returnto=Teoria+computa%C8%9Biei" title="Vă încurajăm să vă creați un cont și să vă autentificați; totuși, nu este obligatoriu"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Creare cont</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:Autentificare&returnto=Teoria+computa%C8%9Biei" title="Sunteți încurajat să vă autentificați, deși acest lucru nu este obligatoriu. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Autentificare</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 id="mw-dismissablenotice-anonplace"></div><script>(function(){var node=document.getElementById("mw-dismissablenotice-anonplace");if(node){node.outerHTML="\u003Cdiv class=\"mw-dismissable-notice\"\u003E\u003Cdiv class=\"mw-dismissable-notice-close\"\u003E[\u003Ca tabindex=\"0\" role=\"button\"\u003Eascunde\u003C/a\u003E]\u003C/div\u003E\u003Cdiv class=\"mw-dismissable-notice-body\"\u003E\u003C!-- CentralNotice --\u003E\u003Cdiv id=\"localNotice\" data-nosnippet=\"\"\u003E\u003Cdiv class=\"anonnotice\" lang=\"ro\" dir=\"ltr\"\u003E\u003Cdiv class=\"plainlinks\" style=\"border: 1px solid #ddd; margin: 0 0 3px;\"\u003E\n\u003Cdiv class=\"nomobile\" style=\"float:right\"\u003E\n\u003Cspan typeof=\"mw:File\"\u003E\u003Ca href=\"/wiki/Wikipedia:Concurs_de_scriere\" title=\"Wikipedia:Concurs de scriere\"\u003E\u003Cimg src=\"//upload.wikimedia.org/wikipedia/commons/thumb/5/55/Concurs_de_scriere.png/126px-Concurs_de_scriere.png\" decoding=\"async\" width=\"126\" height=\"95\" class=\"mw-file-element\" srcset=\"//upload.wikimedia.org/wikipedia/commons/thumb/5/55/Concurs_de_scriere.png/189px-Concurs_de_scriere.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/55/Concurs_de_scriere.png/251px-Concurs_de_scriere.png 2x\" data-file-width=\"506\" data-file-height=\"383\" /\u003E\u003C/a\u003E\u003C/span\u003E\u003C/div\u003E\n\u003Cdiv style=\"color: grey; max-width:1280px; margin: 12px auto; font-family: Tahoma, \u0026#39;DejaVu Sans Condensed\u0026#39;, sans-serif; text-align: center; font-size: 12pt; position: relative;\"\u003EA început o nouă ediție a concursului de scriere! Sunteți cu drag invitați să participați la ediția cu numărul 22, cu articole scrise sau dezvoltate considerabil între 1 aprilie și 30 noiembrie 2024. Pentru înscriere de articole la concurs (nominalizări), condiții de eligibilitate, punctare și alte detalii, vă rugăm să accesați \u003Cb\u003E\u003Ca href=\"/wiki/Wikipedia:Concurs_de_scriere\" title=\"Wikipedia:Concurs de scriere\"\u003Epagina\u0026#160;concursului\u003C/a\u003E\u003C/b\u003E.\u003C/div\u003E\n\u003Cdiv style=\"clear: both;\"\u003E\u003C/div\u003E\n\u003C/div\u003E\u003C/div\u003E\u003C/div\u003E\u003C/div\u003E\u003C/div\u003E";}}());</script></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="Site"> <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="Cuprins" 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">Cuprins</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">mută în bara laterală</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">ascunde</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">Început</div> </a> </li> <li id="toc-Istorie" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Istorie"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Istorie</span> </div> </a> <ul id="toc-Istorie-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Ramuri" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Ramuri"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Ramuri</span> </div> </a> <button aria-controls="toc-Ramuri-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>Toggle Ramuri subsection</span> </button> <ul id="toc-Ramuri-sublist" class="vector-toc-list"> <li id="toc-Teoria_automatelor" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Teoria_automatelor"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Teoria automatelor</span> </div> </a> <ul id="toc-Teoria_automatelor-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Teoria_limbajelor_formale" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Teoria_limbajelor_formale"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Teoria limbajelor formale</span> </div> </a> <ul id="toc-Teoria_limbajelor_formale-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Teoria_calculabilității" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Teoria_calculabilității"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Teoria calculabilității</span> </div> </a> <ul id="toc-Teoria_calculabilității-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Teoria_complexității_computaționale" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Teoria_complexității_computaționale"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.4</span> <span>Teoria complexității computaționale</span> </div> </a> <ul id="toc-Teoria_complexității_computaționale-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Modele_de_calcul" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Modele_de_calcul"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Modele de calcul</span> </div> </a> <ul id="toc-Modele_de_calcul-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Referințe" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Referințe"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Referințe</span> </div> </a> <ul id="toc-Referințe-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Lectură_suplimentară" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Lectură_suplimentară"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Lectură suplimentară</span> </div> </a> <ul id="toc-Lectură_suplimentară-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Legături_externe" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Legături_externe"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Legături externe</span> </div> </a> <ul id="toc-Legături_externe-sublist" class="vector-toc-list"> </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="Cuprins" 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="Comută cuprinsul" > <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">Comută cuprinsul</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">Teoria computației</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="Mergeți la un articol în altă limbă. Disponibil în 41 limbi" > <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-41" 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">41 limbi</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D9%86%D8%B8%D8%B1%D9%8A%D8%A9_%D8%A7%D9%84%D8%AD%D9%88%D8%B3%D8%A8%D8%A9" title="نظرية الحوسبة – arabă" lang="ar" hreflang="ar" data-title="نظرية الحوسبة" data-language-autonym="العربية" data-language-local-name="arabă" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-ast mw-list-item"><a href="https://ast.wikipedia.org/wiki/Teor%C3%ADa_de_la_computaci%C3%B3n" title="Teoría de la computación – asturiană" lang="ast" hreflang="ast" data-title="Teoría de la computación" data-language-autonym="Asturianu" data-language-local-name="asturiană" class="interlanguage-link-target"><span>Asturianu</span></a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/Alqoritml%C9%99r_n%C9%99z%C9%99riyy%C9%99si" title="Alqoritmlər nəzəriyyəsi – azeră" lang="az" hreflang="az" data-title="Alqoritmlər nəzəriyyəsi" data-language-autonym="Azərbaycanca" data-language-local-name="azeră" class="interlanguage-link-target"><span>Azərbaycanca</span></a></li><li class="interlanguage-link interwiki-bs mw-list-item"><a href="https://bs.wikipedia.org/wiki/Teorija_ra%C4%8Dunanja" title="Teorija računanja – bosniacă" lang="bs" hreflang="bs" data-title="Teorija računanja" data-language-autonym="Bosanski" data-language-local-name="bosniacă" class="interlanguage-link-target"><span>Bosanski</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Teoria_de_la_computaci%C3%B3" title="Teoria de la computació – catalană" lang="ca" hreflang="ca" data-title="Teoria de la computació" data-language-autonym="Català" data-language-local-name="catalană" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%98%CE%B5%CF%89%CF%81%CE%AF%CE%B1_%CF%85%CF%80%CE%BF%CE%BB%CE%BF%CE%B3%CE%B9%CF%83%CE%BC%CE%BF%CF%8D" title="Θεωρία υπολογισμού – greacă" lang="el" hreflang="el" data-title="Θεωρία υπολογισμού" data-language-autonym="Ελληνικά" data-language-local-name="greacă" class="interlanguage-link-target"><span>Ελληνικά</span></a></li><li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/Theory_of_computation" title="Theory of computation – engleză" lang="en" hreflang="en" data-title="Theory of computation" data-language-autonym="English" data-language-local-name="engleză" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Teorio_de_komputado" title="Teorio de komputado – esperanto" lang="eo" hreflang="eo" data-title="Teorio de komputado" data-language-autonym="Esperanto" data-language-local-name="esperanto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computaci%C3%B3n" title="Teoría de la computación – spaniolă" lang="es" hreflang="es" data-title="Teoría de la computación" data-language-autonym="Español" data-language-local-name="spaniolă" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Konputazioaren_teoria" title="Konputazioaren teoria – bască" lang="eu" hreflang="eu" data-title="Konputazioaren teoria" data-language-autonym="Euskara" data-language-local-name="bască" class="interlanguage-link-target"><span>Euskara</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%86%D8%B8%D8%B1%DB%8C%D9%87_%D9%85%D8%AD%D8%A7%D8%B3%D8%A8%D8%A7%D8%AA" title="نظریه محاسبات – persană" lang="fa" hreflang="fa" data-title="نظریه محاسبات" data-language-autonym="فارسی" data-language-local-name="persană" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Laskettavuus" title="Laskettavuus – finlandeză" lang="fi" hreflang="fi" data-title="Laskettavuus" data-language-autonym="Suomi" data-language-local-name="finlandeză" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-gl mw-list-item"><a href="https://gl.wikipedia.org/wiki/Teor%C3%ADa_da_computaci%C3%B3n" title="Teoría da computación – galiciană" lang="gl" hreflang="gl" data-title="Teoría da computación" data-language-autonym="Galego" data-language-local-name="galiciană" class="interlanguage-link-target"><span>Galego</span></a></li><li class="interlanguage-link interwiki-he badge-Q70894304 mw-list-item" title=""><a href="https://he.wikipedia.org/wiki/%D7%AA%D7%95%D7%A8%D7%AA_%D7%94%D7%97%D7%99%D7%A9%D7%95%D7%91%D7%99%D7%95%D7%AA" title="תורת החישוביות – ebraică" lang="he" hreflang="he" data-title="תורת החישוביות" data-language-autonym="עברית" data-language-local-name="ebraică" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-hi mw-list-item"><a href="https://hi.wikipedia.org/wiki/%E0%A4%85%E0%A4%AD%E0%A4%BF%E0%A4%95%E0%A4%B2%E0%A4%A8_%E0%A4%95%E0%A4%BE_%E0%A4%B8%E0%A4%BF%E0%A4%A6%E0%A5%8D%E0%A4%A7%E0%A4%BE%E0%A4%82%E0%A4%A4" title="अभिकलन का सिद्धांत – hindi" lang="hi" hreflang="hi" data-title="अभिकलन का सिद्धांत" data-language-autonym="हिन्दी" data-language-local-name="hindi" class="interlanguage-link-target"><span>हिन्दी</span></a></li><li class="interlanguage-link interwiki-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Teorija_ra%C4%8Dunanja" title="Teorija računanja – croată" lang="hr" hreflang="hr" data-title="Teorija računanja" data-language-autonym="Hrvatski" data-language-local-name="croată" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Teori_komputasi" title="Teori komputasi – indoneziană" lang="id" hreflang="id" data-title="Teori komputasi" data-language-autonym="Bahasa Indonesia" data-language-local-name="indoneziană" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-io mw-list-item"><a href="https://io.wikipedia.org/wiki/Teorio_di_komputado" title="Teorio di komputado – ido" lang="io" hreflang="io" data-title="Teorio di komputado" data-language-autonym="Ido" data-language-local-name="ido" class="interlanguage-link-target"><span>Ido</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Teoria_della_computazione" title="Teoria della computazione – italiană" lang="it" hreflang="it" data-title="Teoria della computazione" data-language-autonym="Italiano" data-language-local-name="italiană" 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/%E8%A8%88%E7%AE%97%E7%90%86%E8%AB%96" title="計算理論 – japoneză" lang="ja" hreflang="ja" data-title="計算理論" data-language-autonym="日本語" data-language-local-name="japoneză" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-ki mw-list-item"><a href="https://ki.wikipedia.org/wiki/Computation_theory" title="Computation theory – kikuyu" lang="ki" hreflang="ki" data-title="Computation theory" data-language-autonym="Gĩkũyũ" data-language-local-name="kikuyu" class="interlanguage-link-target"><span>Gĩkũyũ</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EA%B3%84%EC%82%B0_%EC%9D%B4%EB%A1%A0" title="계산 이론 – coreeană" lang="ko" hreflang="ko" data-title="계산 이론" data-language-autonym="한국어" data-language-local-name="coreeană" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-ms mw-list-item"><a href="https://ms.wikipedia.org/wiki/Teori_pengiraan" title="Teori pengiraan – malaeză" lang="ms" hreflang="ms" data-title="Teori pengiraan" data-language-autonym="Bahasa Melayu" data-language-local-name="malaeză" class="interlanguage-link-target"><span>Bahasa Melayu</span></a></li><li class="interlanguage-link interwiki-mwl mw-list-item"><a href="https://mwl.wikipedia.org/wiki/Teorie_de_la_cumputa%C3%A7on" title="Teorie de la cumputaçon – mirandeză" lang="mwl" hreflang="mwl" data-title="Teorie de la cumputaçon" data-language-autonym="Mirandés" data-language-local-name="mirandeză" class="interlanguage-link-target"><span>Mirandés</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Teoria_oblicze%C5%84" title="Teoria obliczeń – poloneză" lang="pl" hreflang="pl" data-title="Teoria obliczeń" data-language-autonym="Polski" data-language-local-name="poloneză" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-ps mw-list-item"><a href="https://ps.wikipedia.org/wiki/%D8%AF_%D9%85%D8%AD%D8%A7%D8%B3%D8%A8%DB%90_%D8%AA%DB%8C%D9%88%D8%B1%D9%8A" title="د محاسبې تیوري – paștună" lang="ps" hreflang="ps" data-title="د محاسبې تیوري" data-language-autonym="پښتو" data-language-local-name="paștună" class="interlanguage-link-target"><span>پښتو</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Teoria_da_computa%C3%A7%C3%A3o" title="Teoria da computação – portugheză" lang="pt" hreflang="pt" data-title="Teoria da computação" data-language-autonym="Português" data-language-local-name="portugheză" 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%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2" title="Теория алгоритмов – rusă" lang="ru" hreflang="ru" data-title="Теория алгоритмов" data-language-autonym="Русский" data-language-local-name="rusă" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Teorija_ra%C4%8Dunanja" title="Teorija računanja – sârbo-croată" lang="sh" hreflang="sh" data-title="Teorija računanja" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="sârbo-croată" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Theory_of_computation" title="Theory of computation – Simple English" lang="en-simple" hreflang="en-simple" data-title="Theory of computation" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Te%C3%B3ria_algoritmov" title="Teória algoritmov – slovacă" lang="sk" hreflang="sk" data-title="Teória algoritmov" data-language-autonym="Slovenčina" data-language-local-name="slovacă" 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%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%98%D0%B0_%D0%B8%D0%B7%D1%80%D0%B0%D1%87%D1%83%D0%BD%D1%99%D0%B8%D0%B2%D0%BE%D1%81%D1%82%D0%B8" title="Теорија израчунљивости – sârbă" lang="sr" hreflang="sr" data-title="Теорија израчунљивости" data-language-autonym="Српски / srpski" data-language-local-name="sârbă" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Ber%C3%A4kningsteori" title="Beräkningsteori – suedeză" lang="sv" hreflang="sv" data-title="Beräkningsteori" data-language-autonym="Svenska" data-language-local-name="suedeză" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-tg mw-list-item"><a href="https://tg.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B7%D0%B0%D1%80%D0%B8%D1%8F%D0%B8_%D0%BC%D1%83%D2%B3%D0%BE%D1%81%D0%B8%D0%B1%D0%BE%D1%82" title="Назарияи муҳосибот – tadjică" lang="tg" hreflang="tg" data-title="Назарияи муҳосибот" data-language-autonym="Тоҷикӣ" data-language-local-name="tadjică" class="interlanguage-link-target"><span>Тоҷикӣ</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%97%E0%B8%A4%E0%B8%A9%E0%B8%8E%E0%B8%B5%E0%B8%81%E0%B8%B2%E0%B8%A3%E0%B8%84%E0%B8%B3%E0%B8%99%E0%B8%A7%E0%B8%93" title="ทฤษฎีการคำนวณ – thailandeză" lang="th" hreflang="th" data-title="ทฤษฎีการคำนวณ" data-language-autonym="ไทย" data-language-local-name="thailandeză" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tl mw-list-item"><a href="https://tl.wikipedia.org/wiki/Teorya_ng_komputasyon" title="Teorya ng komputasyon – tagalog" lang="tl" hreflang="tl" data-title="Teorya ng komputasyon" data-language-autonym="Tagalog" data-language-local-name="tagalog" class="interlanguage-link-target"><span>Tagalog</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/Algoritmalar_teorisi" title="Algoritmalar teorisi – turcă" lang="tr" hreflang="tr" data-title="Algoritmalar teorisi" data-language-autonym="Türkçe" data-language-local-name="turcă" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D1%96%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%96%D0%B2" title="Теорія алгоритмів – ucraineană" lang="uk" hreflang="uk" data-title="Теорія алгоритмів" data-language-autonym="Українська" data-language-local-name="ucraineană" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-ur mw-list-item"><a href="https://ur.wikipedia.org/wiki/%D9%86%D8%B8%D8%B1%DB%8C%DB%81_%DA%A9%D9%85%D9%BE%DB%8C%D9%88%D9%B9%DB%8C%D8%B4%D9%86" title="نظریہ کمپیوٹیشن – urdu" lang="ur" hreflang="ur" data-title="نظریہ کمپیوٹیشن" data-language-autonym="اردو" data-language-local-name="urdu" class="interlanguage-link-target"><span>اردو</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E8%AE%A1%E7%AE%97%E7%90%86%E8%AE%BA" title="计算理论 – chineză" lang="zh" hreflang="zh" data-title="计算理论" data-language-autonym="中文" data-language-local-name="chineză" class="interlanguage-link-target"><span>中文</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E9%81%8B%E7%AE%97%E7%90%86%E8%AB%96" title="運算理論 – cantoneză" lang="yue" hreflang="yue" data-title="運算理論" data-language-autonym="粵語" data-language-local-name="cantoneză" 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/Q844718#sitelinks-wikipedia" title="Modifică legăturile interlinguale" class="wbc-editpage">Modifică legăturile</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="Spații de nume"> <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/Teoria_computa%C8%9Biei" title="Vedeți conținutul paginii [a]" accesskey="a"><span>Articol</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Discu%C8%9Bie:Teoria_computa%C8%9Biei" rel="discussion" title="Discuții despre această pagină [t]" accesskey="t"><span>Discuție</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="Change language variant" > <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">română</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="Vizualizări"> <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/Teoria_computa%C8%9Biei"><span>Lectură</span></a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Teoria_computa%C8%9Biei&veaction=edit" title="Modificați această pagină cu EditorulVizual [v]" accesskey="v"><span>Modificare</span></a></li><li id="ca-edit" class="collapsible vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=edit" title="Modificați codul sursă al acestei pagini [e]" accesskey="e"><span>Modificare sursă</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=history" title="Versiunile anterioare ale paginii și autorii lor. [h]" accesskey="h"><span>Istoric</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <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="Unelte" > <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">Unelte</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">Unelte</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">mută în bara laterală</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">ascunde</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Mai multe opțiuni" > <div class="vector-menu-heading"> Acțiuni </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/Teoria_computa%C8%9Biei"><span>Lectură</span></a></li><li id="ca-more-ve-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Teoria_computa%C8%9Biei&veaction=edit" title="Modificați această pagină cu EditorulVizual [v]" accesskey="v"><span>Modificare</span></a></li><li id="ca-more-edit" class="collapsible vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=edit" title="Modificați codul sursă al acestei pagini [e]" accesskey="e"><span>Modificare sursă</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=history"><span>Istoric</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:Ce_se_leag%C4%83_aici/Teoria_computa%C8%9Biei" title="Lista tuturor paginilor wiki care conduc spre această pagină [j]" accesskey="j"><span>Ce trimite aici</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:Modific%C4%83ri_corelate/Teoria_computa%C8%9Biei" rel="nofollow" title="Schimbări recente în legătură cu această pagină [k]" accesskey="k"><span>Schimbări corelate</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:Trimite_fi%C8%99ier" title="Încărcare fișiere [u]" accesskey="u"><span>Trimite fișier</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:Pagini_speciale" title="Lista tuturor paginilor speciale [q]" accesskey="q"><span>Pagini speciale</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Teoria_computa%C8%9Biei&oldid=15748718" title="Legătură permanentă către această versiune a acestei pagini"><span>Legătură permanentă</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=info" title="Mai multe informații despre această pagină"><span>Informații despre pagină</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:Citeaz%C4%83&page=Teoria_computa%C8%9Biei&id=15748718&wpFormIdentifier=titleform" title="Informații cu privire la modul de citare a acestei pagini"><span>Citează acest articol</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fro.wikipedia.org%2Fwiki%2FTeoria_computa%25C8%259Biei"><span>Obține URL scurtat</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fro.wikipedia.org%2Fwiki%2FTeoria_computa%25C8%259Biei"><span>Descărcați codul QR</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"> Tipărire/exportare </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=Special:Carte&bookcmd=book_creator&referer=Teoria+computa%C8%9Biei"><span>Creare carte</span></a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Teoria_computa%C8%9Biei&action=show-download-screen"><span>Descărcare ca PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Teoria_computa%C8%9Biei&printable=yes" title="Versiunea de tipărit a acestei pagini [p]" accesskey="p"><span>Versiune de tipărit</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"> În alte proiecte </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Theory_of_computation" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q844718" title="Legătură către elementul asociat din depozitul de date [g]" accesskey="g"><span>Element Wikidata</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="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Aspect"> <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">Aspect</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">mută în bara laterală</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">ascunde</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">De la Wikipedia, enciclopedia liberă</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="ro" dir="ltr"><figure typeof="mw:File/Thumb"><a href="/wiki/Fi%C8%99ier:Maquina.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/250px-Maquina.png" decoding="async" width="250" height="139" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/375px-Maquina.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/500px-Maquina.png 2x" data-file-width="1800" data-file-height="1000" /></a><figcaption>Reprezentare artistică a unei <a href="/wiki/Ma%C8%99in%C4%83_Turing" title="Mașină Turing">mașini Turing</a>. Mașinile Turing sunt frecvent utilizate ca modele teoretice de calcul.</figcaption></figure> <p>În <a href="/w/index.php?title=Informatic%C4%83_teoretic%C4%83&action=edit&redlink=1" class="new" title="Informatică teoretică — pagină inexistentă">informatica teoretică</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q2878974" class="extiw" title="d:Q2878974"><span title="informatică teoretică la Wikidata">d</span></a>)</small></sup> și în <a href="/wiki/Matematic%C4%83" title="Matematică">matematică</a>, <b>teoria computației</b> este ramura care se ocupă cu cât de eficient pot fi rezolvate problemele pe un <a href="/w/index.php?title=Model_de_calcul&action=edit&redlink=1" class="new" title="Model de calcul — pagină inexistentă">model de calcul</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q2651576" class="extiw" title="d:Q2651576"><span title="model de calcul la Wikidata">d</span></a>)</small></sup>, folosind un <a href="/wiki/Algoritm" title="Algoritm">algoritm</a>. Domeniul este împărțit în trei ramuri majore: <a href="/wiki/Teoria_automatelor" title="Teoria automatelor">teoria limbajelor formale și automatelor</a>, <a href="/wiki/Teoria_calculabilit%C4%83%C8%9Bii" title="Teoria calculabilității">teoria calculabilității</a> și <a href="/wiki/Teoria_complexit%C4%83%C8%9Bii" title="Teoria complexității">teoria complexității</a>, care sunt legate de întrebarea: „<i>care sunt capabilitățile fundamentale și limitările calculatoarelor?”.</i><sup id="cite_ref-Sipser-3rd_1-0" class="reference"><a href="#cite_note-Sipser-3rd-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p><p>Pentru a efectua un studiu riguros al computației, informaticienii lucrează cu o abstracție matematică a calculatorului, numită <a href="/w/index.php?title=Model_de_calcul&action=edit&redlink=1" class="new" title="Model de calcul — pagină inexistentă">model de calcul</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q2651576" class="extiw" title="d:Q2651576"><span title="model de calcul la Wikidata">d</span></a>)</small></sup>. Există mai multe modele în uz, dar cel mai frecvent examinat este o <a href="/wiki/Ma%C8%99in%C4%83_Turing" title="Mașină Turing">mașină Turing</a>.<sup id="cite_ref-Hodges-2012_2-0" class="reference"><a href="#cite_note-Hodges-2012-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Informaticienii studiază mașina Turing, deoarece este simplu de formulat, poate fi analizată și utilizată pentru a demonstra rezultatele, și pentru că ea reprezintă ceea ce mulți consideră a fi cel mai puternic posibil model de calcul „rezonabil” (a se vedea <a href="/wiki/Teza_Church-Turing" title="Teza Church-Turing">teza Church–Turing</a>).<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Capacitatea potențial infinită a memoriei ar părea o cerință nerealizabilă, dar orice problemă <a href="/w/index.php?title=Decidabil%C4%83&action=edit&redlink=1" class="new" title="Decidabilă — pagină inexistentă">decidabilă</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q430001" class="extiw" title="d:Q430001"><span title="decidabilă la Wikidata">d</span></a>)</small></sup><sup id="cite_ref-Monk1976_4-0" class="reference"><a href="#cite_note-Monk1976-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> rezolvată de către o mașină Turing va necesita întotdeauna doar o cantitate finită de memorie. Deci, în principiu, orice problemă care poate fi rezolvată (decisă) de către o mașină Turing poate fi rezolvată de către un computer care are o cantitate finită de memorie. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Istorie">Istorie</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&veaction=edit&section=1" title="Modifică secțiunea: Istorie" class="mw-editsection-visualeditor"><span>modificare</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=edit&section=1" title="Edit section's source code: Istorie"><span>modificare sursă</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Teoria computației poate fi considerată crearea de modele de toate tipurile în domeniul informaticii. Prin urmare, se utilizează <a href="/wiki/Logic%C4%83_matematic%C4%83" title="Logică matematică">matematica și logica</a>. În ultimul secol, a devenit o disciplină academică independentă și separată de matematică. </p><p>Unii reprezentanți ai teoriei computației au fost <a href="/wiki/Alonzo_Church" title="Alonzo Church">Alonzo Church</a>, <a href="/wiki/Kurt_G%C3%B6del" title="Kurt Gödel">Kurt Gödel</a>, <a href="/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a>, <a href="/wiki/Stephen_Cole_Kleene" title="Stephen Cole Kleene">Stephen Kleene</a>, <a href="/wiki/John_von_Neumann" title="John von Neumann">John von Neumann</a> și <a href="/wiki/Claude_Shannon" title="Claude Shannon">Claude Shannon</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Ramuri">Ramuri</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&veaction=edit&section=2" title="Modifică secțiunea: Ramuri" class="mw-editsection-visualeditor"><span>modificare</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=edit&section=2" title="Edit section's source code: Ramuri"><span>modificare sursă</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Teoria_automatelor">Teoria automatelor</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&veaction=edit&section=3" title="Modifică secțiunea: Teoria automatelor" class="mw-editsection-visualeditor"><span>modificare</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=edit&section=3" title="Edit section's source code: Teoria automatelor"><span>modificare sursă</span></a><span class="mw-editsection-bracket">]</span></span></div> <table class="wikitable" style="margin-bottom: 10px; background-repeat: repeat; background-image: none; background-position: 0% 0%;"> <tbody><tr> <th>Gramatică </th> <th>Limbaje </th> <th>Automate </th> <th>Reguli de producție (constrângeri) </th></tr> <tr> <td>Tip 0 </td> <td><a href="/w/index.php?title=Recursiv_enumerabile&action=edit&redlink=1" class="new" title="Recursiv enumerabile — pagină inexistentă">Recursiv enumerabile</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1073063" class="extiw" title="d:Q1073063"><span title="Recursiv enumerabile la Wikidata">d</span></a>)</small></sup> </td> <td><a href="/wiki/Ma%C8%99in%C4%83_Turing" title="Mașină Turing">Mașină Turing</a> </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha \rightarrow \beta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>α</mi> <mo stretchy="false">→</mo> <mi>β</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha \rightarrow \beta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e2b0511d452842ec71e40223d223472b7527ca7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.434ex; height:2.509ex;" alt="{\displaystyle \alpha \rightarrow \beta }"></span> (fără restricții) </td></tr> <tr> <td>Tip 1 </td> <td><a href="/w/index.php?title=Dependente_de_context&action=edit&redlink=1" class="new" title="Dependente de context — pagină inexistentă">Dependente de context</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q908674" class="extiw" title="d:Q908674"><span title="Dependente de context la Wikidata">d</span></a>)</small></sup> </td> <td><a href="/w/index.php?title=Ma%C8%99in%C4%83_Turing_nedeterminist%C4%83_liniar_m%C4%83rginit%C4%83&action=edit&redlink=1" class="new" title="Mașină Turing nedeterministă liniar mărginită — pagină inexistentă">Mașină Turing nedeterministă liniar mărginită</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1149323" class="extiw" title="d:Q1149323"><span title="Mașină Turing nedeterministă liniar mărginită la Wikidata">d</span></a>)</small></sup> </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>α</mi> <mi>A</mi> <mi>β</mi> <mo stretchy="false">→</mo> <mi>α</mi> <mi>γ</mi> <mi>β</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1173552bcbf68bb06baf9b0a2f543dbc845caefd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.259ex; height:2.676ex;" alt="{\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }"></span> </td></tr> <tr> <td>Tip 2 </td> <td><a href="/w/index.php?title=Independente_de_context&action=edit&redlink=1" class="new" title="Independente de context — pagină inexistentă">Independente de context</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q338047" class="extiw" title="d:Q338047"><span title="Independente de context la Wikidata">d</span></a>)</small></sup> </td> <td><a href="/w/index.php?title=Automatul_cu_stiv%C4%83&action=edit&redlink=1" class="new" title="Automatul cu stivă — pagină inexistentă">Automatul cu stivă</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q751443" class="extiw" title="d:Q751443"><span title="Automatul cu stivă la Wikidata">d</span></a>)</small></sup> nedeterminist </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\rightarrow \gamma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo stretchy="false">→</mo> <mi>γ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A\rightarrow \gamma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/91998fd76701871c7df169d4e9114b5970c61877" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.62ex; height:2.676ex;" alt="{\displaystyle A\rightarrow \gamma }"></span> </td></tr> <tr> <td>Tip 3 </td> <td><a href="/w/index.php?title=Regulate&action=edit&redlink=1" class="new" title="Regulate — pagină inexistentă">Regulate</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q645527" class="extiw" title="d:Q645527"><span title="Regulate la Wikidata">d</span></a>)</small></sup> </td> <td><a href="/wiki/Automat_finit" title="Automat finit">Automatul finit</a> </td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\rightarrow a}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo stretchy="false">→</mo> <mi>a</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A\rightarrow a}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f2c4fbdf7d3a3af41e9c6b2f8e9586d9ada6317d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.587ex; height:2.176ex;" alt="{\displaystyle A\rightarrow a}"></span><br /> și<br /><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\rightarrow aB}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo stretchy="false">→</mo> <mi>a</mi> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A\rightarrow aB}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01b2bfd09f27542fbcf3811786b84f6a43fd17d3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.351ex; height:2.176ex;" alt="{\displaystyle A\rightarrow aB}"></span> </td></tr></tbody></table> <p>Teoria automatelor este studiul mașinilor abstracte (sau, mai corect, mașinilor sau sistemelor „matematice” abstracte) și problemelor de calcul care pot fi rezolvate cu ajutorul acestor mașini. Aceste mașini abstracte sunt numite „automate”, cuvânt care provine de la termenul grecesc (Αυτόματα), ceea ce înseamnă că ceva face ceva de la sine. Teoria automatelor este, de asemenea, strâns legată cea a <a href="/wiki/Limbaje_formale" class="mw-redirect" title="Limbaje formale">limbajelor formale</a>,<sup id="cite_ref-hopcroft-ullman_5-0" class="reference"><a href="#cite_note-hopcroft-ullman-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> întrucât automatele sunt adesea clasificate în funcție de clasa de limbaje formale pe care sunt în stare să o recunoască. Un automat poate fi o reprezentare finită a unui limbaj formal care poate fi o mulțime infinită. Automatele sunt folosite ca modele teoretice pentru mașinile de calcul, și sunt folosite pentru demonstrații ale calculabilității. </p> <div class="mw-heading mw-heading3"><h3 id="Teoria_limbajelor_formale">Teoria limbajelor formale</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&veaction=edit&section=4" title="Modifică secțiunea: Teoria limbajelor formale" class="mw-editsection-visualeditor"><span>modificare</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=edit&section=4" title="Edit section's source code: Teoria limbajelor formale"><span>modificare sursă</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/Fi%C8%99ier:Chomsky-hierarchy.svg" class="mw-file-description"><img alt="The Chomsky hierarchy" src="//upload.wikimedia.org/wikipedia/commons/thumb/9/9a/Chomsky-hierarchy.svg/langro-200px-Chomsky-hierarchy.svg.png" decoding="async" width="200" height="144" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/9a/Chomsky-hierarchy.svg/langro-300px-Chomsky-hierarchy.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/9a/Chomsky-hierarchy.svg/langro-400px-Chomsky-hierarchy.svg.png 2x" data-file-width="714" data-file-height="515" /></a><figcaption>Incluziunea mulțimilor descrisă de ierarhia Chomsky</figcaption></figure> <p>Teoria limbajelor este o ramură a matematicii care se ocupă cu descrierea limbajelor ca mulțimi de operațiuni peste un <a href="/wiki/Alfabet" title="Alfabet">alfabet</a>. Ea este strâns legată de teoria automatelor, întrucât automatele sunt folosite pentru a genera și a recunoaște limbaje formale. Există mai multe clase de limbaje formale, fiecare permițând specificații mai complexe de limbaj decât cea dinainte, de unde structurarea lor în <a href="/wiki/Ierarhia_Chomsky" title="Ierarhia Chomsky">ierarhia Chomsky</a>,<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> și fiecare corespunzând unei clase de automate care o recunoaște. Pentru că automatele sunt folosite ca modele de calcul, limbajele formale sunt modul preferat de specificare pentru orice problemă care trebuie să fie calculată. </p> <div class="mw-heading mw-heading3"><h3 id="Teoria_calculabilității"><span id="Teoria_calculabilit.C4.83.C8.9Bii"></span>Teoria calculabilității</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&veaction=edit&section=5" title="Modifică secțiunea: Teoria calculabilității" class="mw-editsection-visualeditor"><span>modificare</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=edit&section=5" title="Edit section's source code: Teoria calculabilității"><span>modificare sursă</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Teoria calculabilității se ocupă în principal cu întrebarea dacă o problemă este rezolvabilă de un calculator. Afirmația că <a href="/w/index.php?title=Problema_opririi&action=edit&redlink=1" class="new" title="Problema opririi — pagină inexistentă">problema opririi</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q622849" class="extiw" title="d:Q622849"><span title="problema opririi la Wikidata">d</span></a>)</small></sup> nu poate fi rezolvată de către o mașină Turing<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> este unul dintre cele mai importante rezultate din teoria calculabilității, un exemplu de problemă concretă, care este atât de ușor de formulat, dar imposibil de rezolvat folosind o mașină Turing. Mare parte din teoria calculabilității se bazează pe rezultatul problemei opririi. </p><p>Un alt pas important în teoria calculabilității a fost <a href="/w/index.php?title=Teorema_lui_Rice&action=edit&redlink=1" class="new" title="Teorema lui Rice — pagină inexistentă">teorema lui Rice</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1893717" class="extiw" title="d:Q1893717"><span title="teorema lui Rice la Wikidata">d</span></a>)</small></sup>, care prevede că pentru toate proprietățile netriviale ale funcțiilor parțiale, este <a href="/w/index.php?title=Indecidabil&action=edit&redlink=1" class="new" title="Indecidabil — pagină inexistentă">indecidabil</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q430001" class="extiw" title="d:Q430001"><span title="indecidabil la Wikidata">d</span></a>)</small></sup> dacă o mașină Turing calculează o funcție parțială cu acea proprietate.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p><p>Teoria calculabilității este strâns legată de ramura <a href="/wiki/Logic%C4%83_matematic%C4%83" title="Logică matematică">logicii matematice</a> denumită <a href="/wiki/Teoria_calculabilit%C4%83%C8%9Bii" title="Teoria calculabilității">teoria recursivității</a>, care elimină restricția de a studia numai modele de calcul, reductibile la modelul Turing.<sup id="cite_ref-davis_9-0" class="reference"><a href="#cite_note-davis-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> Mulți matematicieni și teoreticieni ai calculabilității care studiază teoria recursivității o denumesc și pe ea „teoria calculabilității”. </p> <div class="mw-heading mw-heading3"><h3 id="Teoria_complexității_computaționale"><span id="Teoria_complexit.C4.83.C8.9Bii_computa.C8.9Bionale"></span>Teoria complexității computaționale</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&veaction=edit&section=6" title="Modifică secțiunea: Teoria complexității computaționale" class="mw-editsection-visualeditor"><span>modificare</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=edit&section=6" title="Edit section's source code: Teoria complexității computaționale"><span>modificare sursă</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/Fi%C8%99ier:Complexity_subsets_pspace.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/6e/Complexity_subsets_pspace.svg/250px-Complexity_subsets_pspace.svg.png" decoding="async" width="250" height="227" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/6e/Complexity_subsets_pspace.svg/375px-Complexity_subsets_pspace.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/6e/Complexity_subsets_pspace.svg/500px-Complexity_subsets_pspace.svg.png 2x" data-file-width="485" data-file-height="441" /></a><figcaption>O reprezentare a relației dintre clasele de complexitate</figcaption></figure> <p><a href="/wiki/Teoria_complexit%C4%83%C8%9Bii" title="Teoria complexității">Teoria complexității</a> consideră nu numai dacă o problemă poate fi rezolvată de un calculator, ci și cât de eficient poate fi ea rezolvată. Sunt analizate două aspecte majore: complexitatea în timp și complexitatea în spațiu, adică de câți pași este nevoie pentru a efectua un calcul și, respectiv, de cât de multă memorie este necesară pentru a efectua acest calcul. </p><p>Pentru a analiza de cât timp și spațiu are nevoie un anumit <a href="/wiki/Algoritm" title="Algoritm">algoritm</a>, informaticienii exprimă timpul și spațiul necesar pentru a rezolva problema în funcție de mărimea problemei de la intrare. De exemplu, găsirea unui anumit număr într-o listă lungă de numere devine mai greu pe măsură ce lista de numere crește. Dacă am spune că există <i>n</i> numere în listă, atunci, dacă lista nu este sortată sau indexată în vreun fel, s-ar putea să fie nevoie să se caute fiecare număr, în scopul de a găsi numărul căutat. Se poate spune, deci, că, în scopul de a rezolva această problemă, calculatorul are nevoie să efectueze o serie de pași care crește liniar cu dimensiunea problemei. </p><p>Pentru a simplifica această problemă, informaticienii au adoptat <a href="/wiki/Nota%C8%9Bia_Big_O" title="Notația Big O">notația Big O</a>, care permite compararea funcțiilor într-un mod care garantează că anumite aspecte constructive ale unei mașini fizice pot fi ignorate, expresia fiind relevantă numai pentru <a href="/w/index.php?title=Analiz%C4%83_asimptotic%C4%83&action=edit&redlink=1" class="new" title="Analiză asimptotică — pagină inexistentă">comportamentul asimptotic</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q752718" class="extiw" title="d:Q752718"><span title="analiză asimptotică la Wikidata">d</span></a>)</small></sup> pe măsură ce problemele devin mai mari. Deci, în exemplul anterior s-ar putea spune că problema necesită <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34109fe397fdcff370079185bfdb65826cb5565a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}"></span> pași pentru a fi rezolvată. </p><p>Poate cea mai importantă problemă deschisă în toată <a href="/wiki/Informatic%C4%83" title="Informatică">informatica</a> este întrebarea dacă o anumită clasă largă de probleme notate <a href="/wiki/NP_(teoria_complexit%C4%83%C8%9Bii)" title="NP (teoria complexității)">NP</a> pot fi rezolvate în mod eficient. <a href="/wiki/Clasele_de_complexitate_P_%C8%99i_NP" title="Clasele de complexitate P și NP">Problema P versus NP</a> este una dintre cele șapte <a href="/w/index.php?title=Probleme_ale_Premiului_Mileniului&action=edit&redlink=1" class="new" title="Probleme ale Premiului Mileniului — pagină inexistentă">probleme ale Premiului Mileniului</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q727000" class="extiw" title="d:Q727000"><span title="probleme ale Premiului Mileniului la Wikidata">d</span></a>)</small></sup> declarate de <a href="/w/index.php?title=Clay_Mathematics_Institute&action=edit&redlink=1" class="new" title="Clay Mathematics Institute — pagină inexistentă">Clay Mathematics Institute</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q857975" class="extiw" title="d:Q857975"><span title="Clay Mathematics Institute la Wikidata">d</span></a>)</small></sup> în anul 2000. <a rel="nofollow" class="external text" href="http://www.claymath.org/sites/default/files/pvsnp.pdf">Descrierea oficială a problemei</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150904090304/http://www.claymath.org/sites/default/files/pvsnp.pdf">Arhivat</a> în <time datetime="2015-09-04">4 septembrie 2015</time>, la <a href="/wiki/Wayback_Machine" class="mw-redirect" title="Wayback Machine">Wayback Machine</a>. a fost făcută de laureatul <a href="/wiki/Premiul_Turing" title="Premiul Turing">premiului Turing</a>, <a href="/wiki/Stephen_Cook" title="Stephen Cook">Stephen Cook</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Modele_de_calcul">Modele de calcul</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&veaction=edit&section=7" title="Modifică secțiunea: Modele de calcul" class="mw-editsection-visualeditor"><span>modificare</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=edit&section=7" title="Edit section's source code: Modele de calcul"><span>modificare sursă</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>În afară de <a href="/wiki/Ma%C8%99in%C4%83_Turing" title="Mașină Turing">mașina Turing</a>, există și alte modele de calcul echivalente. </p> <dl><dt><a href="/w/index.php?title=Calculul_lambda&action=edit&redlink=1" class="new" title="Calculul lambda — pagină inexistentă">Calculul Lambda</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q242028" class="extiw" title="d:Q242028"><span title="calculul lambda la Wikidata">d</span></a>)</small></sup></dt> <dd>Un calcul constă dintr-o expresie lambda inițială (sau două, dacă se dorește separarea funcției de intrare), plus o secvență finită de termeni lambda, fiecare dedus din cel anterior termen printr-o aplicare a unei reduceri Beta.</dd> <dt><a href="/w/index.php?title=Logica_combinatoric%C4%83&action=edit&redlink=1" class="new" title="Logica combinatorică — pagină inexistentă">Logica combinatorică</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1481571" class="extiw" title="d:Q1481571"><span title="Logica combinatorică la Wikidata">d</span></a>)</small></sup></dt> <dd>este un concept care are multe similitudini cu calculul calculul <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>λ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b43d0ea3c9c025af1be9128e62a18fa74bedda2a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.176ex;" alt="{\displaystyle \lambda }"></span>, dar există și diferențe importante (de exemplu, combinatorul de punct fix <b>Y</b> are formă normală în logica combinatorică, dar nu și în calculul <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>λ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b43d0ea3c9c025af1be9128e62a18fa74bedda2a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.176ex;" alt="{\displaystyle \lambda }"></span>). Logica combinatorică a fost dezvoltată cu mari ambiții: de a înțelege natura paradoxurilor, de a face bazele matematicii mai economice (conceptual), de a elimina noțiunea de variabilă (clarificând astfel rolul acestora în matematică).</dd></dl> <dl><dt><a href="/w/index.php?title=Func%C8%9Biile_%CE%BC-recursive&action=edit&redlink=1" class="new" title="Funcțiile μ-recursive — pagină inexistentă">Funcțiile μ-recursive</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q284164" class="extiw" title="d:Q284164"><span title="Funcțiile μ-recursive la Wikidata">d</span></a>)</small></sup></dt> <dd>un calcul constă dintr-o funcție miu-recursivă, <i>adică</i> șirul său de definiție, orice valoare de intrare(e) și un șir de funcții recursive care apar în șirul de definiție cu intrări și ieșiri. Astfel, dacă în șirul de definiție al unei funcții recursive <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}"></span> apar funcțiile <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6ca91363022bd5e4dcb17e5ef29f78b8ef00b59" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.255ex; height:2.843ex;" alt="{\displaystyle g(x)}"></span> și <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(x,y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>h</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h(x,y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7235c6799c7d4112231c9941bd428fe6a4111fe4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.667ex; height:2.843ex;" alt="{\displaystyle h(x,y)}"></span>, atunci ar putea apărea termeni de forma „g(5)=7” sau „h(3,2)=10”. Fiecare element din acest șir trebuie să fie o aplicație a unei funcții de bază sau să rezulte din elementele menționate de mai sus, prin utilizarea <a href="/w/index.php?title=Compunerii&action=edit&redlink=1" class="new" title="Compunerii — pagină inexistentă">compunerii</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q13461925" class="extiw" title="d:Q13461925"><span title="compunerii la Wikidata">d</span></a>)</small></sup>, <a href="/w/index.php?title=Recursivit%C4%83%C8%9Bii_primitive&action=edit&redlink=1" class="new" title="Recursivității primitive — pagină inexistentă">recursivității primitive</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1570472" class="extiw" title="d:Q1570472"><span title="recursivității primitive la Wikidata">d</span></a>)</small></sup> sau <a href="/w/index.php?title=%CE%9C-recursivit%C4%83%C8%9Bii&action=edit&redlink=1" class="new" title="Μ-recursivității — pagină inexistentă">μ-recursivității</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q284164" class="extiw" title="d:Q284164"><span title="μ-recursivității la Wikidata">d</span></a>)</small></sup>. De exemplu, dacă <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=h(x,g(x))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>h</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <mi>g</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)=h(x,g(x))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8c6cce0a24b4df2a31c2c214940795920f1ea777" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.283ex; height:2.843ex;" alt="{\displaystyle f(x)=h(x,g(x))}"></span>, atunci pentru a apărea „f(5)=3”, trebuie să apară mai întâi termeni ca „g(5)=6” și „h(5,6)=3”. Calculul se termină doar dacă ultimul termen dă valoarea funcției recursive aplicată asupra intrării.</dd></dl> <dl><dt><a href="/w/index.php?title=Algoritm_Markov&action=edit&redlink=1" class="new" title="Algoritm Markov — pagină inexistentă">Algoritm Markov</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1900936" class="extiw" title="d:Q1900936"><span title="Algoritm Markov la Wikidata">d</span></a>)</small></sup></dt> <dd>un <a href="/w/index.php?title=Sistem_de_rescriere_a_%C8%99irurilor&action=edit&redlink=1" class="new" title="Sistem de rescriere a șirurilor — pagină inexistentă">sistem de rescriere a șirurilor</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1378504" class="extiw" title="d:Q1378504"><span title="sistem de rescriere a șirurilor la Wikidata">d</span></a>)</small></sup> care folosește reguli ca cele <a href="/wiki/Gramatic%C4%83" title="Gramatică">gramaticale</a> pentru a funcționa pe <a href="/w/index.php?title=%C8%98ir_de_caractere&action=edit&redlink=1" class="new" title="Șir de caractere — pagină inexistentă">șiruri</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q184754" class="extiw" title="d:Q184754"><span title="șir de caractere la Wikidata">d</span></a>)</small></sup> de simboluri.</dd></dl> <dl><dt><a href="/w/index.php?title=Ma%C8%99in%C4%83_cu_regi%C8%99tri&action=edit&redlink=1" class="new" title="Mașină cu regiștri — pagină inexistentă">Mașină cu regiștri</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1930388" class="extiw" title="d:Q1930388"><span title="Mașină cu regiștri la Wikidata">d</span></a>)</small></sup></dt> <dd>este o idealizare a unui calculator, de interes teoretic. Există mai multe variante. În cele mai multe dintre ele, fiecare registru poate reține un număr natural (de dimensiuni nelimitate), iar instrucțiunile sunt simple (și puține la număr), de exemplu, există doar decrementarea (combinată cu saltul condiționat) și incrementarea (și oprirea). Lipsa unui suport de stocare externă finit (sau în creștere dinamică; așa cum se observă la mașina Turing) poate fi înțeleasă prin înlocuirea rolului său cu tehnici de <a href="/w/index.php?title=Numerotare_G%C3%B6del&action=edit&redlink=1" class="new" title="Numerotare Gödel — pagină inexistentă">numerotare Gödel</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1451046" class="extiw" title="d:Q1451046"><span title="numerotare Gödel la Wikidata">d</span></a>)</small></sup>: faptul că fiecare registru reține un număr natural permite posibilitatea de a reprezenta ceva complicat (de exemplu, un șir sau o matrice etc.) printr-un număr natural mare corespunzător — lipsa de ambiguitate atât a reprezentării cât și a interpretării poate fi stabilită prin bazele acestor tehnici din <a href="/wiki/Teoria_numerelor" title="Teoria numerelor">teoria numerelor</a>.</dd></dl> <p>În plus față de modelele de calcul generale, există și unele modele de calcul mai simple, utile pentru aplicații speciale, restricționate. <a href="/wiki/Expresie_regulat%C4%83" title="Expresie regulată">Expresiile regulate</a>, de exemplu, specifică modele de șiruri de caractere în mai multe contexte, de la software-uri de productivitate la birou și până la <a href="/wiki/Limbaj_de_programare" title="Limbaj de programare">limbaje de programare</a>. Un alt formalism matematic echivalent cu expresiile regulate, <a href="/wiki/Automat_finit" title="Automat finit">automatele finite</a>, este utilizat în proiectarea circuitelor și în unele tipuri de rezolvare a problemelor. <a href="/w/index.php?title=Gramaticile_independente_de_context&action=edit&redlink=1" class="new" title="Gramaticile independente de context — pagină inexistentă">Gramaticile independente de context</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q338047" class="extiw" title="d:Q338047"><span title="Gramaticile independente de context la Wikidata">d</span></a>)</small></sup> specifică sintaxa limbajelor de programare. <a href="/w/index.php?title=Automatele_nedeterministe_cu_stiv%C4%83&action=edit&redlink=1" class="new" title="Automatele nedeterministe cu stivă — pagină inexistentă">Automatele nedeterministe cu stivă</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q751443" class="extiw" title="d:Q751443"><span title="Automatele nedeterministe cu stivă la Wikidata">d</span></a>)</small></sup> sunt un alt formalism echivalent cu gramaticile independente de context. <a href="/w/index.php?title=Func%C8%9Biile_recursive_primitive&action=edit&redlink=1" class="new" title="Funcțiile recursive primitive — pagină inexistentă">Funcțiile recursive primitive</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1570472" class="extiw" title="d:Q1570472"><span title="Funcțiile recursive primitive la Wikidata">d</span></a>)</small></sup> sunt o subclasă a funcțiilor recursive. </p><p>Diferitele modele de calcul au capacitatea de a îndeplini diferite sarcini. O modalitate de a măsura puterea unui model de calcul este de a studia clasa de <a href="/wiki/Limbaje_formale" class="mw-redirect" title="Limbaje formale">limbaje formale</a> pe care o poate genera modelul; într-un asemenea mod se obține <a href="/wiki/Ierarhia_Chomsky" title="Ierarhia Chomsky">ierarhia Chomsky</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Referințe"><span id="Referin.C8.9Be"></span>Referințe</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&veaction=edit&section=8" title="Modifică secțiunea: Referințe" class="mw-editsection-visualeditor"><span>modificare</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=edit&section=8" title="Edit section's source code: Referințe"><span>modificare sursă</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-Sipser-3rd-1"><b><a href="#cite_ref-Sipser-3rd_1-0">^</a></b> <span class="reference-text"><cite class="citation book"><a href="/w/index.php?title=Michael_Sipser&action=edit&redlink=1" class="new" title="Michael Sipser — pagină inexistentă">Michael Sipser</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q93104" class="extiw" title="d:Q93104"><span title="Michael Sipser la Wikidata">d</span></a>)</small></sup> (<time datetime="2013">2013</time>). <i>Introduction to the Theory of Computation 3rd</i>. Cengage Learning. <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/978-1-133-18779-0" title="Special:Referințe în cărți/978-1-133-18779-0">978-1-133-18779-0</a>. <q>central areas of the theory of computation: automata, computability, and complexity. (Page 1)</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+the+Theory+of+Computation+3rd&rft.pub=Cengage+Learning&rft.date=2013&rft.isbn=978-1-133-18779-0&rft.au=%3AMichael+Sipser%3Csup%3E%3Csmall%3E%E2%81%A0%28%3Cspan+title%3D%22Michael+Sipser+la+Wikidata%22%3Ed%3C%2Fspan%3E%29%3C%2Fsmall%3E%3C%2Fsup%3E&rfr_id=info%3Asid%2Fro.wikipedia.org%3ATeoria+computa%C8%9Biei" class="Z3988"><span style="display:none;"> </span></span><style data-mw-deduplicate="TemplateStyles:r16236537">.mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"„""”""«""»"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}</style></span> </li> <li id="cite_note-Hodges-2012-2"><b><a href="#cite_ref-Hodges-2012_2-0">^</a></b> <span class="reference-text"><cite class="citation book"><a href="/w/index.php?title=Andrew_Hodges&action=edit&redlink=1" class="new" title="Andrew Hodges — pagină inexistentă">Andrew Hodges</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q450154" class="extiw" title="d:Q450154"><span title="Andrew Hodges la Wikidata">d</span></a>)</small></sup> (<time datetime="2012">2012</time>). <i>Alan Turing: The Enigma (THE CENTENARY EDITION)</i>. Princeton University Press. <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/978-0-691-15564-7" title="Special:Referințe în cărți/978-0-691-15564-7">978-0-691-15564-7</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Alan+Turing%3A+The+Enigma+%28THE+CENTENARY+EDITION%29&rft.pub=Princeton+University+Press&rft.date=2012&rft.isbn=978-0-691-15564-7&rft.au=%3AAndrew+Hodges%3Csup%3E%3Csmall%3E%E2%81%A0%28%3Cspan+title%3D%22Andrew+Hodges+la+Wikidata%22%3Ed%3C%2Fspan%3E%29%3C%2Fsmall%3E%3C%2Fsup%3E&rfr_id=info%3Asid%2Fro.wikipedia.org%3ATeoria+computa%C8%9Biei" class="Z3988"><span style="display:none;"> </span></span> <span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|autor=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|nume=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>)</span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r16236537"></span> </li> <li id="cite_note-3"><b><a href="#cite_ref-3">^</a></b> <span class="reference-text"><span class="citation audio-visual"> <a rel="nofollow" class="external text" href="http://videolectures.net/turing100_rabin_turing_church_goedel/"><i>Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View</i></a>. 1 iunie 2012<span class="printonly">. <a rel="nofollow" class="external free" href="http://videolectures.net/turing100_rabin_turing_church_goedel/">http://videolectures.net/turing100_rabin_turing_church_goedel/</a></span>.</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Turing%2C+Church%2C+G%C3%B6del%2C+Computability%2C+Complexity+and+Randomization%3A+A+Personal+View&rft.date=June+2012&rft_id=http%3A%2F%2Fvideolectures.net%2Fturing100_rabin_turing_church_goedel%2F&rfr_id=info:sid/ro.wikipedia.org:Teoria_computa%C8%9Biei"><span style="display: none;"> </span></span></span> </li> <li id="cite_note-Monk1976-4"><b><a href="#cite_ref-Monk1976_4-0">^</a></b> <span class="reference-text"><cite class="citation book">Donald Monk (<time datetime="1976">1976</time>). <i>Mathematical Logic</i>. Springer-Verlag. <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/9780387901701" title="Special:Referințe în cărți/9780387901701">9780387901701</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Mathematical+Logic&rft.pub=Springer-Verlag&rft.date=1976&rft.isbn=9780387901701&rft.au=Donald+Monk&rfr_id=info%3Asid%2Fro.wikipedia.org%3ATeoria+computa%C8%9Biei" class="Z3988"><span style="display:none;"> </span></span> <span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|autor=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|nume=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>)</span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r16236537"></span> </li> <li id="cite_note-hopcroft-ullman-5"><b><a href="#cite_ref-hopcroft-ullman_5-0">^</a></b> <span class="reference-text"><cite class="citation book"><a href="/wiki/John_Hopcroft" title="John Hopcroft">Hopcroft, John E.</a> and <a href="/w/index.php?title=Jeffrey_David_Ullman&action=edit&redlink=1" class="new" title="Jeffrey David Ullman — pagină inexistentă">Jeffrey David Ullman</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q92794" class="extiw" title="d:Q92794"><span title="Jeffrey David Ullman la Wikidata">d</span></a>)</small></sup> (<time datetime="2006">2006</time>). <i><a href="/w/index.php?title=Introduction_to_Automata_Theory,_Languages,_and_Computation&action=edit&redlink=1" class="new" title="Introduction to Automata Theory, Languages, and Computation — pagină inexistentă">Introduction to Automata Theory, Languages, and Computation</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q7486248" class="extiw" title="d:Q7486248"><span title="Introduction to Automata Theory, Languages, and Computation la Wikidata">d</span></a>)</small></sup>. 3rd ed</i>. Reading, MA: Addison-Wesley. <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/978-0-321-45536-9" title="Special:Referințe în cărți/978-0-321-45536-9">978-0-321-45536-9</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=%3AIntroduction+to+Automata+Theory%2C+Languages%2C+and+Computation%3Csup%3E%3Csmall%3E%E2%81%A0%28%3Cspan+title%3D%22Introduction+to+Automata+Theory%2C+Languages%2C+and+Computation+la+Wikidata%22%3Ed%3C%2Fspan%3E%29%3C%2Fsmall%3E%3C%2Fsup%3E.+3rd+ed&rft.pub=Reading%2C+MA%3A+Addison-Wesley.&rft.date=2006&rft.isbn=978-0-321-45536-9&rft.au=Hopcroft%2C+John+E.+and+%3AJeffrey+David+Ullman%3Csup%3E%3Csmall%3E%E2%81%A0%28%3Cspan+title%3D%22Jeffrey+David+Ullman+la+Wikidata%22%3Ed%3C%2Fspan%3E%29%3C%2Fsmall%3E%3C%2Fsup%3E&rfr_id=info%3Asid%2Fro.wikipedia.org%3ATeoria+computa%C8%9Biei" class="Z3988"><span style="display:none;"> </span></span> <span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|autor=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|nume=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>)</span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r16236537"></span> </li> <li id="cite_note-6"><b><a href="#cite_ref-6">^</a></b> <span class="reference-text"><cite class="citation journal"><a href="/wiki/Ierarhia_Chomsky" title="Ierarhia Chomsky">Ierarhia Chomsky</a> (<time datetime="1956">1956</time>). <a rel="nofollow" class="external text" href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1056813&tag=1">„Three models for the description of language”</a>. <i>Information Theory, IRE Transactions on</i>. IEEE. <b>2</b> (3): 113–124. <a href="/wiki/Digital_object_identifier" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1956.1056813">10.1109/TIT.1956.1056813</a><span class="reference-accessdate">. Accesat în <time datetime="2015-01-06">6 ianuarie 2015</time></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Information+Theory%2C+IRE+Transactions+on&rft.atitle=Three+models+for+the+description+of+language&rft.volume=2&rft.issue=3&rft.pages=113-124&rft.date=1956&rft_id=info%3Adoi%2F10.1109%2FTIT.1956.1056813&rft.au=Ierarhia+Chomsky&rft_id=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D1056813%26tag%3D1&rfr_id=info%3Asid%2Fro.wikipedia.org%3ATeoria+computa%C8%9Biei" class="Z3988"><span style="display:none;"> </span></span> <span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|accessdate=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|access-date=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>); </span><span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|DOI=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|doi=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>)</span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r16236537"></span> </li> <li id="cite_note-7"><b><a href="#cite_ref-7">^</a></b> <span class="reference-text"><cite class="citation journal"><a href="/wiki/Alan_Turing" title="Alan Turing">Alan Turing</a> (<time datetime="1937">1937</time>). <a rel="nofollow" class="external text" href="http://www.turingarchive.org/browse.php/B/12">„On computable numbers, with an application to the Entscheidungsproblem”</a>. <i>Proceedings of the <a href="/w/index.php?title=London_Mathematical_Society&action=edit&redlink=1" class="new" title="London Mathematical Society — pagină inexistentă">London Mathematical Society</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1810244" class="extiw" title="d:Q1810244"><span title="London Mathematical Society la Wikidata">d</span></a>)</small></sup></i>. IEEE. <b>2</b> (42): 230–265. <a href="/wiki/Digital_object_identifier" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1112%2Fplms%2Fs2-42.1.230">10.1112/plms/s2-42.1.230</a><span class="reference-accessdate">. Accesat în <time datetime="2015-01-06">6 ianuarie 2015</time></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+the+%3ALondon+Mathematical+Society%3Csup%3E%3Csmall%3E%E2%81%A0%28%3Cspan+title%3D%22London+Mathematical+Society+la+Wikidata%22%3Ed%3C%2Fspan%3E%29%3C%2Fsmall%3E%3C%2Fsup%3E&rft.atitle=On+computable+numbers%2C+with+an+application+to+the+Entscheidungsproblem&rft.volume=2&rft.issue=42&rft.pages=230-265&rft.date=1937&rft_id=info%3Adoi%2F10.1112%2Fplms%2Fs2-42.1.230&rft.au=Alan+Turing&rft_id=http%3A%2F%2Fwww.turingarchive.org%2Fbrowse.php%2FB%2F12&rfr_id=info%3Asid%2Fro.wikipedia.org%3ATeoria+computa%C8%9Biei" class="Z3988"><span style="display:none;"> </span></span> <span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|accessdate=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|access-date=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>); </span><span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|DOI=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|doi=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>)</span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r16236537"><sup>[<i><a href="/wiki/Wikipedia:Leg%C4%83turi_externe" title="Wikipedia:Legături externe">nefuncțională</a></i>]</sup></span> </li> <li id="cite_note-8"><b><a href="#cite_ref-8">^</a></b> <span class="reference-text"><cite class="citation journal">Henry Gordon Rice (<time datetime="1953">1953</time>). „Classes of Recursively Enumerable Sets and Their Decision Problems”. <i>Transactions of the <a href="/wiki/American_Mathematical_Society" title="American Mathematical Society">American Mathematical Society</a></i>. American Mathematical Society. <b>74</b> (2): 358–366. <a href="/wiki/Digital_object_identifier" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F1990888">10.2307/1990888</a>. <a href="/wiki/JSTOR" title="JSTOR">JSTOR</a> <a rel="nofollow" class="external text" href="//www.jstor.org/stable/1990888">1990888</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Transactions+of+the+American+Mathematical+Society&rft.atitle=Classes+of+Recursively+Enumerable+Sets+and+Their+Decision+Problems&rft.volume=74&rft.issue=2&rft.pages=358-366&rft.date=1953&rft_id=info%3Adoi%2F10.2307%2F1990888&rft_id=%2F%2Fwww.jstor.org%2Fstable%2F1990888&rft.au=Henry+Gordon+Rice&rfr_id=info%3Asid%2Fro.wikipedia.org%3ATeoria+computa%C8%9Biei" class="Z3988"><span style="display:none;"> </span></span> <span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|JSTOR=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|jstor=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>); </span><span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|DOI=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|doi=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>)</span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r16236537"></span> </li> <li id="cite_note-davis-9"><b><a href="#cite_ref-davis_9-0">^</a></b> <span class="reference-text"><cite class="citation book"><a href="/w/index.php?title=Martin_Davis&action=edit&redlink=1" class="new" title="Martin Davis — pagină inexistentă">Martin Davis</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1239172" class="extiw" title="d:Q1239172"><span title="Martin Davis la Wikidata">d</span></a>)</small></sup> (<time datetime="2004">2004</time>). <i>The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed)</i>. Dover Publications. <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/978-0486432281" title="Special:Referințe în cărți/978-0486432281">978-0486432281</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+undecidable%3A+Basic+papers+on+undecidable+propositions%2C+unsolvable+problems+and+computable+functions+%28Dover+Ed%29&rft.pub=Dover+Publications&rft.date=2004&rft.isbn=978-0486432281&rft.au=%3AMartin+Davis%3Csup%3E%3Csmall%3E%E2%81%A0%28%3Cspan+title%3D%22Martin+Davis+la+Wikidata%22%3Ed%3C%2Fspan%3E%29%3C%2Fsmall%3E%3C%2Fsup%3E&rfr_id=info%3Asid%2Fro.wikipedia.org%3ATeoria+computa%C8%9Biei" class="Z3988"><span style="display:none;"> </span></span> <span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|autor=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|nume=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>)</span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r16236537"></span> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="Lectură_suplimentară"><span id="Lectur.C4.83_suplimentar.C4.83"></span>Lectură suplimentară</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&veaction=edit&section=9" title="Modifică secțiunea: Lectură suplimentară" class="mw-editsection-visualeditor"><span>modificare</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=edit&section=9" title="Edit section's source code: Lectură suplimentară"><span>modificare sursă</span></a><span class="mw-editsection-bracket">]</span></span></div> <dl><dt>Manualele pentru informaticieni</dt></dl> <p>(Există mai multe manuale în acest domeniu; această listă este inerent incompletă.) </p> <ul><li><a href="/wiki/John_Hopcroft" title="John Hopcroft">Hopcroft, John E.</a>, și Jeffrey D. Ullman (2006). <i>Introducere în teoria automatelor, a limbajelor formale și a calculabilitatății. 3rd ed</i> Reading, MA: Addison-Wesley. <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/9780321455369" class="internal mw-magiclink-isbn">ISBN 978-0-321-45536-9</a> Una dintre lucrările standard de referință în domeniu.</li> <li><cite class="citation book"><a href="/w/index.php?title=Michael_Sipser&action=edit&redlink=1" class="new" title="Michael Sipser — pagină inexistentă">Michael Sipser</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q93104" class="extiw" title="d:Q93104"><span title="Michael Sipser la Wikidata">d</span></a>)</small></sup> (<time datetime="2013">2013</time>). <i>Introduction to the Theory of Computation</i> (ed. 3rd). Cengage Learning. <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/978-1-133-18779-0" title="Special:Referințe în cărți/978-1-133-18779-0">978-1-133-18779-0</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+the+Theory+of+Computation&rft.edition=3rd&rft.pub=Cengage+Learning&rft.date=2013&rft.isbn=978-1-133-18779-0&rft.au=%3AMichael+Sipser%3Csup%3E%3Csmall%3E%E2%81%A0%28%3Cspan+title%3D%22Michael+Sipser+la+Wikidata%22%3Ed%3C%2Fspan%3E%29%3C%2Fsmall%3E%3C%2Fsup%3E&rfr_id=info%3Asid%2Fro.wikipedia.org%3ATeoria+computa%C8%9Biei" class="Z3988"><span style="display:none;"> </span></span> <span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|autor=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|nume=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>)</span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r16236537"></li> <li><cite class="citation book"><a href="/w/index.php?title=Eitan_Gurari&action=edit&redlink=1" class="new" title="Eitan Gurari — pagină inexistentă">Eitan Gurari</a> (<time datetime="1989">1989</time>). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20070107040625/http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html"><i>An Introduction to the Theory of Computation</i></a>. Computer Science Press. <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/0-7167-8182-4" title="Special:Referințe în cărți/0-7167-8182-4">0-7167-8182-4</a>. Arhivat din <a rel="nofollow" class="external text" href="http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html">original</a> la <time datetime="2007-01-07">7 ianuarie 2007</time><span class="reference-accessdate">. Accesat în <time datetime="2017-05-26">26 mai 2017</time></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=An+Introduction+to+the+Theory+of+Computation&rft.pub=Computer+Science+Press&rft.date=1989&rft.isbn=0-7167-8182-4&rft.au=Eitan+Gurari&rft_id=http%3A%2F%2Fwww.cse.ohio-state.edu%2F~gurari%2Ftheory-bk%2Ftheory-bk.html&rfr_id=info%3Asid%2Fro.wikipedia.org%3ATeoria+computa%C8%9Biei" class="Z3988"><span style="display:none;"> </span></span> <span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|autor=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|nume=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>)</span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r16236537"></li> <li>Hein, James L. (1996) <i>Theory of Computation.</i> Sudbury, MA: Jones & Bartlett. <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/9780867204971" class="internal mw-magiclink-isbn">ISBN 978-0-86720-497-1</a> O introducere sumară în domeniu, adecvată pentru studenții de anul al doilea la informatică.</li> <li>Taylor, R. Grigorie (1998). <i> Models of Computation and Formal Languages.</i> New York: Oxford University Press. <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/9780195109832" class="internal mw-magiclink-isbn">ISBN 978-0-19-510983-2</a> Un manual neobișnuit de ușor de citit, adecvat pentru studenții din ultimii ani ai ciclului de diplomă sau licență sau pentru cei care încep studiile postuniversitare.</li> <li>Lewis, F. D. (2007). <i>Essentials of theoretical computer science</i> Un manual care acoperă subiecte de limbaje formale, automate și gramatici. Accentul pare a fi pe prezentarea unei imagini de ansamblu a rezultatelor și a aplicațiilor lor, mai degrabă decât pe furnizarea de demonstrații ale rezultatelor.</li> <li><a href="/w/index.php?title=Martin_Davis&action=edit&redlink=1" class="new" title="Martin Davis — pagină inexistentă">Martin Davis</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q1239172" class="extiw" title="d:Q1239172"><span title="Martin Davis la Wikidata">d</span></a>)</small></sup>, Ron Sigal, Elaine J. Weyuker, <i>Computability, complexity, and languages: fundamentals of theoretical computer science</i>, ed. a 2, Academic Press, 1994, <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/0122063821" class="internal mw-magiclink-isbn">ISBN 0-12-206382-1</a>. Acoperă o gamă mai largă de subiecte decât cele mai multe cărți introductive, între care semantica programelor și teoria cuantificării. Destinată studenților din ciclurile postuniversitare.</li></ul> <dl><dt>Cărți de teoria computabilității din perspectivă matematică (mai largă)</dt></dl> <ul><li>Hartley Rogers Jr (1987). <i>Theory of Recursive Functions and Effective Computability</i>, MIT Press. <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/0262680521" class="internal mw-magiclink-isbn">ISBN 0-262-68052-1</a></li> <li><cite class="citation book"><a href="/w/index.php?title=S._Barry_Cooper&action=edit&redlink=1" class="new" title="S. Barry Cooper — pagină inexistentă">S. Barry Cooper</a><sup><small>⁠(<a href="https://www.wikidata.org/wiki/Q7387391" class="extiw" title="d:Q7387391"><span title="S. Barry Cooper la Wikidata">d</span></a>)</small></sup> (<time datetime="2004">2004</time>). <i>Computability Theory</i>. Chapman and Hall/CRC. <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/1-58488-237-9" title="Special:Referințe în cărți/1-58488-237-9">1-58488-237-9</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computability+Theory&rft.pub=Chapman+and+Hall%2FCRC&rft.date=2004&rft.isbn=1-58488-237-9&rft.au=%3AS.+Barry+Cooper%3Csup%3E%3Csmall%3E%E2%81%A0%28%3Cspan+title%3D%22S.+Barry+Cooper+la+Wikidata%22%3Ed%3C%2Fspan%3E%29%3C%2Fsmall%3E%3C%2Fsup%3E&rfr_id=info%3Asid%2Fro.wikipedia.org%3ATeoria+computa%C8%9Biei" class="Z3988"><span style="display:none;"> </span></span> <span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|autor=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|nume=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>)</span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r16236537">.</li> <li>Carl H. Smith, <i>A recursive introduction to the theory of computation</i>, Springer, 1994, <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/0387943323" class="internal mw-magiclink-isbn">ISBN 0-387-94332-3</a>. Un manual scurt potrivit pentru studenții la informatică din ciclul postuniversitar.</li></ul> <dl><dt>Perspectivă istorică</dt></dl> <ul><li><cite class="citation book"><a href="/w/index.php?title=Richard_L._Epstein&action=edit&redlink=1" class="new" title="Richard L. Epstein — pagină inexistentă">Richard L. Epstein</a> and <a href="/w/index.php?title=Walter_A._Carnielli&action=edit&redlink=1" class="new" title="Walter A. Carnielli — pagină inexistentă">Walter A. Carnielli</a> (<time datetime="2000">2000</time>). <i>Computability: Computable Functions, Logic, and the Foundations of Mathematics, with Computability: A Timeline (2nd ed.)</i>. Wadsworth/Thomson Learning. <a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Special:Referin%C8%9Be_%C3%AEn_c%C4%83r%C8%9Bi/0-534-54644-7" title="Special:Referințe în cărți/0-534-54644-7">0-534-54644-7</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computability%3A+Computable+Functions%2C+Logic%2C+and+the+Foundations+of+Mathematics%2C+with+Computability%3A+A+Timeline+%282nd+ed.%29&rft.pub=Wadsworth%2FThomson+Learning&rft.date=2000&rft.isbn=0-534-54644-7&rft.au=Richard+L.+Epstein+and+Walter+A.+Carnielli&rfr_id=info%3Asid%2Fro.wikipedia.org%3ATeoria+computa%C8%9Biei" class="Z3988"><span style="display:none;"> </span></span> <span style="font-size:100%" class="error citation-comment">Mai multe valori specificate pentru <code style="color:inherit; border:inherit; padding:inherit;">|autor=</code> și <code style="color:inherit; border:inherit; padding:inherit;">|nume=</code> (<a href="/wiki/Ajutor:Erori_CS1#redundant_parameters" title="Ajutor:Erori CS1">ajutor</a>)</span><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r16236537">.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Legături_externe"><span id="Leg.C4.83turi_externe"></span>Legături externe</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&veaction=edit&section=10" title="Modifică secțiunea: Legături externe" class="mw-editsection-visualeditor"><span>modificare</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Teoria_computa%C8%9Biei&action=edit&section=10" title="Edit section's source code: Legături externe"><span>modificare sursă</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://toc.csail.mit.edu/">Theory of Computation</a> la <a href="/wiki/Massachusetts_Institute_of_Technology" title="Massachusetts Institute of Technology">MIT</a></li> <li><a rel="nofollow" class="external text" href="http://toc.seas.harvard.edu/">Theory of Computation</a> la <a href="/wiki/Universitatea_Harvard" title="Universitatea Harvard">Harvard</a></li> <li><a rel="nofollow" class="external text" href="http://www.cis.upenn.edu/~giorgi/cl.html">Logica computabilității</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110411024825/http://www.cis.upenn.edu/~giorgi/cl.html">Arhivat</a> în <time datetime="2011-04-11">11 aprilie 2011</time>, la <a href="/wiki/Wayback_Machine" class="mw-redirect" title="Wayback Machine">Wayback Machine</a>. - o teoria a calculului interactiv. Principala resursă web pe acest subiect.</li></ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Adus de la <a dir="ltr" href="https://ro.wikipedia.org/w/index.php?title=Teoria_computației&oldid=15748718">https://ro.wikipedia.org/w/index.php?title=Teoria_computației&oldid=15748718</a></div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Special:Categorii" title="Special:Categorii">Categorie</a>: <ul><li><a href="/wiki/Categorie:Informatic%C4%83_teoretic%C4%83" title="Categorie:Informatică teoretică">Informatică teoretică</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Categorii ascunse: <ul><li><a href="/wiki/Categorie:Pagini_cu_cit%C4%83ri_cu_argumente_redundante" title="Categorie:Pagini cu citări cu argumente redundante">Pagini cu citări cu argumente redundante</a></li><li><a href="/wiki/Categorie:Pagini_cu_leg%C4%83turi_externe_nefunc%C8%9Bionale" title="Categorie:Pagini cu legături externe nefuncționale">Pagini cu legături externe nefuncționale</a></li><li><a href="/wiki/Categorie:Webarchive_template_wayback_links" title="Categorie:Webarchive template wayback links">Webarchive template wayback links</a></li><li><a href="/wiki/Categorie:Pagini_ce_folosesc_leg%C4%83turi_automate_c%C4%83tre_ISBN" title="Categorie:Pagini ce folosesc legături automate către ISBN">Pagini ce folosesc legături automate către ISBN</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"> Ultima editare a paginii a fost efectuată la 18 iunie 2023, ora 20:12.</li> <li id="footer-info-copyright">Acest text este disponibil sub licența <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.ro">Creative Commons cu atribuire și distribuire în condiții identice</a>; pot exista și clauze suplimentare. Vedeți detalii la <a class="external text" href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use">Termenii de utilizare</a>.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Politica de confidențialitate</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:Despre">Despre Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:Termeni">Termeni</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Cod de conduită</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Dezvoltatori</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/ro.wikipedia.org">Statistici</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Declarație cookie</a></li> <li id="footer-places-mobileview"><a href="//ro.m.wikipedia.org/w/index.php?title=Teoria_computa%C8%9Biei&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Versiune mobilă</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-694cf4987f-x7kgg","wgBackendResponseTime":129,"wgPageParseReport":{"limitreport":{"cputime":"0.385","walltime":"0.835","ppvisitednodes":{"value":1574,"limit":1000000},"postexpandincludesize":{"value":51312,"limit":2097152},"templateargumentsize":{"value":1212,"limit":2097152},"expansiondepth":{"value":14,"limit":100},"expensivefunctioncount":{"value":0,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":38401,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 609.036 1 -total"," 72.30% 440.340 44 Format:Ill-wd"," 19.76% 120.365 8 Format:Citat_carte"," 10.62% 64.693 1 Format:Cite_book"," 4.28% 26.076 3 Format:Citat_revistă"," 3.16% 19.237 1 Format:Cite_video"," 2.39% 14.543 1 Format:Citation/core"," 1.54% 9.372 2 Format:Webarchive"," 0.34% 2.068 1 Format:Legătură_nefuncțională"," 0.32% 1.947 1 Format:Citation/make_link"]},"scribunto":{"limitreport-timeusage":{"value":"0.226","limit":"10.000"},"limitreport-memusage":{"value":3953230,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-74dc4d995d-892r4","timestamp":"20241104115306","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Teoria computa\u021biei","url":"https:\/\/ro.wikipedia.org\/wiki\/Teoria_computa%C8%9Biei","sameAs":"http:\/\/www.wikidata.org\/entity\/Q844718","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q844718","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2017-05-26T08:32:43Z","dateModified":"2023-06-18T18:12:04Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/3\/3d\/Maquina.png"}</script> </body> </html>