| dbpprop:abstract
|
- In computability theory the Church–Turing thesis (also known as Church's thesis, Church's conjecture and Turing's thesis) is a combined hypothesis ("thesis") about the nature of effectively calculable (computable) functions by recursion (Church's Thesis), by mechanical device equivalent to a Turing machine (Turing's Thesis) or by use of Church's λ-calculus. The three computational processes (recursion, λ-calculus, and Turing machine) were shown to be equivalent by Alonzo Church, Stephen Kleene, J.B. Rosser (1934–6) and Alan Turing (1936–7). However, even though the three processes proved to be equivalent, the fundamental premise behind the theses—the notion of what it means for a function to be "effectively calculable" (computable) is "a somewhat vague intuitive one". Thus, as they stand, the "theses" remain hypotheses and cannot be proven. Informally the Church–Turing thesis states that if an algorithm (a procedure that terminates) exists then there is an equivalent Turing machine, recursively-definable function, or applicable λ-function, for that algorithm. Today the thesis has near-universal acceptance.
- Die Church-Turing-These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet: Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen. Diese These ist nicht beweisbar, da der Begriff intuitiv berechenbare Funktion nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auch von einem Menschen ausgerechnet werden könnten. Damit setzt man insbesondere keine Vorstellung voraus, welche Funktionen auf den natürlichen Zahlen berechenbar sind. Es wird in der Informatik üblicherweise angenommen, dass die These stimmt. Dadurch kann es ermöglicht werden, von einer Funktion nachzuweisen, dass sie nicht berechenbar ist.
- V teorii vyčíslitelnosti se pojmy Church-Turingova teze, Churchova teze a Turingova teze označuje hypotéza o povaze a výpočetní síle mechanických strojů počítajících matematické funkce. Teze je pojmenována po Alonzu Churchovi a Alanu Turingovi. Hypotéza říká, že každý možný výpočet lze úspěšně uskutečnit algoritmem běžícím na počítači, je-li k disposici dostatek času a paměti. Algoritmus musí splňovat následující požadavky: Algoritmus se skládá z konečného počtu instrukcí, které jsou přesně definovány použitím konečného počtu symbolů. Algoritmus vždy vrátí výsledek po konečném počtu kroků. Algoritmus může provádět i člověk s tužkou a papírem. Spuštění algoritmu nepotřebuje lidskou inteligenci, s výjimkou té, která je třeba na pochopení a vykonání instrukcí. Tento popis algoritmu je sice intuitivně zřejmý, ale postrádá formální zázemí, jelikož není přesně popsáno, co znamená „přesně definovaná instrukce“ a co je „lidská inteligence potřebná na pochopení instrukcí“. Neformálně řečeno hypotéza tvrdí, že naše chápaní algoritmu je správné: vše, co lze počítačem vypočítat, lze vypočítat pomocí algoritmu a naopak. Navíc říká, že naše počítače jsou stejně „schopné“ jako jakékoli jiné stroje, které lze sestrojit. (Toto tvrzení ale nebere v úvahu rychlost a velikost paměti, což jsou v praxi velice důležité faktory)
- Tesis de Church: "(Church-Turing) A function of positive integers is effectively calculable only if recursive. " Cuya traducción sería: Una función de enteros positivos es efectivamente calculable sólo si es recursiva. Y debido a que hay una variedad de formulaciones de la tesis de Church-Turing, usaremos, en general, una formulación simple y aceptada como dicha tesis, que se obtiene a partir de las revisiones conjuntas entre Alonzo Church y Alan M. Turing de sus respectivos trabajos: Versión de la Tesis de Church-Turing más utilizada: Todo algoritmo o procedimiento efectivo es Turing-computable. Otra versión simplificada de la anterior es: Todo lo que es computable es Turing-computable.
- La thèse de Church - du nom du mathématicien Alonzo Church - est le principe de base de la calculabilité. Dans sa forme la plus ordinaire, elle affirme que tout traitement réalisable mécaniquement peut être accompli par un ordinateur (plus précisément dans sa forme idéalisée qu'est une machine de Turing). Dans une forme plus élaborée, elle affirme qu'un concept intuitif, la calculabilité effective, coïncide avec un concept formel et mathématique, la calculabilité, défini de plusieurs façons dont on a pu démontrer mathématiquement qu'elles sont équivalentes. Stephen Kleene a appelé le premier « thèse de Church » (en 1943 et 1952) ce que ce dernier présentait comme une définition de la calculabilité effective. Elle est connue plus récemment sous le nom de thèse de Church-Turing terminologie proposée par certains spécialistes dans les années 1990, bien que Church soit sans nul doute le premier, au début des années 1930, à avoir pensé pouvoir définir formellement la calculabilité intuitive (par la λ-définissabilité). Cependant c'est l'article de Turing de 1936 et son modèle mécanique de calculabilité, qui ont définitivement emporté l'adhésion, selon Gödel, Kleene et Church lui-même.
- A számításelméletben a Church–Turing-tézis az 1930-as években megfogalmazott sejtés, mely szerint minden formalizálható probléma, ami megoldható algoritmussal, az megoldható Turing-géppel vagy lambda-kalkulussal is; azaz a Turing-gép a feladatmegoldó eljárások legáltalánosabb és a fenti értelemben legerősebb példája. A sejtést azért nem tételnek, hanem csak (hipo)tézisnek nevezik, mert nem matematikai tétel, ugyanis a „feladatmegoldó eljárás” nem mint definiált matematikai fogalom szerepel). Ugyanakkor szintén a harmincas években a „feladatmegoldó eljárás” fogalmát számtalan alakban sikerült formálisan megfoghatóvá tenni, de kiderült, hogy ezek a megfogalmazások is ekvivalensek a Turing-gépre épülő eljárásfogalommal. Ez azt jelenti, hogy a Turing-gép egy univerzális algoritmikus modell. Maga a Turing-gép tekinthető az algoritmus egy definíciójának. A tézis összefügg az erős mesterséges intelligencia elvi létével illetve lehetetlenségével is. Nem ismerünk olyan algoritmikus rendszert, amelyről tudnánk, hogy erősebb a Turing-gépnél, és a legtöbb algoritmikus rendszerre bizonyított, hogy gyengébb, vagy ekvivalens. A bizonyítottan Turing-ekvivalens algoritmikus rendszerek a következők: asszociatív kalkulusok rekurzív függvények osztálya a lambda-kalkulus függvény-osztálya formális nyelvek legáltalánosabb, kötetlen osztálya C, LISP, Java, Prolog, Pascal stb. nyelven írt nem interaktív programok
- Nella teoria della calcolabilità la tesi di Church-Turing è un'ipotesi che afferma: "se un problema è intuitivamente calcolabile, allora esisterà una macchina di Turing (o un dispositivo equivalente, come il computer) in grado di risolverlo. " Più formalmente possiamo dire che la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing.
- チャーチ＝チューリングのテーゼ (Church-Turing thesis) もしくはチャーチのテーゼ (Church's thesis) とは、「計算できる関数」という直観的な概念を、帰納的関数と呼ばれる数論的関数のクラスと同一視しようという主張である。 テーゼの代わりに提唱 (ていしょう) あるいは定立 (ていりつ) の語が用いられることもある。 このクラスはチューリング・マシンで実行できるプログラムのクラス、ラムダ記法で定義できる関数のクラスとも一致する。 よって簡単にはテーゼは、計算が可能な関数とは、その計算を実行できるような有限のアルゴリズムが存在するような関数、よっておおよそコンピュータで実行できる関数と同じだと主張する。
- De Stelling van Church en Turing is een stelling in de berekenbaarheidstheorie, geformuleerd door Alonzo Church en Alan Turing. Deze stelling is eigenlijk een hypothese, aangezien deze nooit bewezen zal kunnen worden. Enkele afgeleide hypotheses zijn zelfs al ontkracht.
- Hipoteza Churcha-Turinga (zwana również Tezą Churcha-Turinga) jest hipotezą określającą możliwości komputerów i innych maszyn obliczeniowych. Mówi ona, że każdy problem, dla którego przy nieograniczonej pamięci oraz zasobach istnieje efektywny algorytm jego rozwiązywania, da się rozwiązać na maszynie Turinga. Hipoteza jest niemożliwa do sprawdzenia matematycznie, ponieważ łączy w sobie zarówno ścisłe, jak i nieprecyzyjne sformułowania, których interpretacja może zależeć od konkretnej osoby. Dlatego traktowana jest bardziej jako aksjomat lub swoiste prawo. Mniej formalnie, hipoteza pozwala dokładniej sformułować pojęcie samego algorytmu, mówiąc jednocześnie, że komputery są w stanie go wykonać. Co więcej, wszystkie komputery mają jednakowe możliwości, jeśli chodzi o zdolność do ich wykonywania, a nie dostępne zasoby, oraz że nie jest możliwe zbudowanie komputera o zdolności do rozwiązywania większej liczby problemów, niż najprostsza maszyna Turinga. Hipoteza została zaproponowana po raz pierwszy przez Stephena Kleene'ego w 1943 roku, lecz została nazwana od Alonzo Churcha i Alana Turinga.
- Na teoria da computabilidade, a Tese de Church-Turing ou Tese de Church, assim nomeada em referência a Alonzo Church e Alan Turing, é uma hipótese sobre a natureza de artefatos mecânicos de cálculo, como computadores, e sobre que tipo de algoritmos eles podem executar. Geralmente assume-se que um algoritmo deve satisfazer os seguintes requisitos: O algoritmo consiste de um conjunto finito de instruções simples e precisas, que são descritas com um número finito de símbolos. O algoritmo sempre produz resultado em um número finito de passos. O algoritmo pode, a princípio, ser executado por um ser humano com apenas papel e lápis. A execução do algoritmo não requer inteligência do ser humano além do necessário para entender e executar as instruções. Um exemplo de tal método é o algoritmo de Euclides para a determinação do máximo divisor comum de dois números naturais. A noção de algoritmo é intuitivamente clara mas não é definida formalmente, pois não está claro o que quer dizer "instruções simples e precisas", e o que significa "inteligência necessária para executar as instruções". Informalmente a tese enuncia que nossa noção de algoritmo pode ser formalizada (sob a forma de funções computáveis) e que computadores podem executar esses algoritmos. Além disso, qualquer computador pode, teoricamente, executar qualquer algoritmo, isto é, o poder computacional teórico de cada computador é o mesmo e não é possível construir um artefato de cálculo mais poderoso que um computador. A tese pode ser considerada uma lei física, já que não pode ser matematicamente demonstrada.
- Те́зис Чёрча — Тью́ринга — фундаментальное утверждение для многих областей науки, таких, как теория вычислимости, информатика, теоретическая кибернетика и др. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов. В самой общей форме оно гласит, что любая интуитивно вычислимая функция является частично вычислимой, или, что тоже самое, может быть вычислена некоторой машиной Тьюринга. Тезис Чёрча — Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает «равенство» между строго формализованным понятием частично вычислимой функции и неформальным понятием «интуитивно вычислимой функции». Физический тезис Чёрча — Тьюринга гласит: Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.
- Теза Черча — твердження, згідно з яким, клас алгоритмічно-обчислюваних функцій збігається з класом частково-рекурсивних функцій, функцій обчислюваних за Тюрінгом та інших формальних уточнень інтуїтивного поняття алгоритм. З неї випливає, що якщо функція належить до класу певної формалізації алгоритмічно-обчислюваної функції, то вона є алгоритмічно-обчислювана. Теза не доводиться. А еквівалентність класів формалізмів підлягає доведенню, що і було зроблено. Названа на честь американського математика Алонзо Черча. Також виділяють тезу Черча-Тюрінга.
- 邱奇-图灵论题（The Church-Turing thesis）是计算机科学中以数学家阿隆佐·邱奇(Alonzo Church)和阿兰·图灵命名的论题。该论题最基本的观点表明，所有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机，反之任何一台图灵机也都可以翻译成大部分编程语言程序，所以该论题和以下说法等价：常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真，也被称为邱奇论题或邱奇猜想和图灵论题。
|
| rdfs:comment
|
- In computability theory the Church–Turing thesis (also known as Church's thesis, Church's conjecture and Turing's thesis) is a combined hypothesis ("thesis") about the nature of effectively calculable (computable) functions by recursion (Church's Thesis), by mechanical device equivalent to a Turing machine (Turing's Thesis) or by use of Church's λ-calculus.
- Die Church-Turing-These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet: Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen. Diese These ist nicht beweisbar, da der Begriff intuitiv berechenbare Funktion nicht exakt formalisiert werden kann.
- V teorii vyčíslitelnosti se pojmy Church-Turingova teze, Churchova teze a Turingova teze označuje hypotéza o povaze a výpočetní síle mechanických strojů počítajících matematické funkce. Teze je pojmenována po Alonzu Churchovi a Alanu Turingovi. Hypotéza říká, že každý možný výpočet lze úspěšně uskutečnit algoritmem běžícím na počítači, je-li k disposici dostatek času a paměti.
- Tesis de Church: "(Church-Turing) A function of positive integers is effectively calculable only if recursive. " Cuya traducción sería: Una función de enteros positivos es efectivamente calculable sólo si es recursiva. Y debido a que hay una variedad de formulaciones de la tesis de Church-Turing, usaremos, en general, una formulación simple y aceptada como dicha tesis, que se obtiene a partir de las revisiones conjuntas entre Alonzo Church y Alan M.
- La thèse de Church - du nom du mathématicien Alonzo Church - est le principe de base de la calculabilité. Dans sa forme la plus ordinaire, elle affirme que tout traitement réalisable mécaniquement peut être accompli par un ordinateur (plus précisément dans sa forme idéalisée qu'est une machine de Turing).
- A számításelméletben a Church–Turing-tézis az 1930-as években megfogalmazott sejtés, mely szerint minden formalizálható probléma, ami megoldható algoritmussal, az megoldható Turing-géppel vagy lambda-kalkulussal is; azaz a Turing-gép a feladatmegoldó eljárások legáltalánosabb és a fenti értelemben legerősebb példája.
- Nella teoria della calcolabilità la tesi di Church-Turing è un'ipotesi che afferma: "se un problema è intuitivamente calcolabile, allora esisterà una macchina di Turing (o un dispositivo equivalente, come il computer) in grado di risolverlo. " Più formalmente possiamo dire che la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing.
- De Stelling van Church en Turing is een stelling in de berekenbaarheidstheorie, geformuleerd door Alonzo Church en Alan Turing. Deze stelling is eigenlijk een hypothese, aangezien deze nooit bewezen zal kunnen worden. Enkele afgeleide hypotheses zijn zelfs al ontkracht.
- Hipoteza Churcha-Turinga (zwana również Tezą Churcha-Turinga) jest hipotezą określającą możliwości komputerów i innych maszyn obliczeniowych. Mówi ona, że każdy problem, dla którego przy nieograniczonej pamięci oraz zasobach istnieje efektywny algorytm jego rozwiązywania, da się rozwiązać na maszynie Turinga.
- Na teoria da computabilidade, a Tese de Church-Turing ou Tese de Church, assim nomeada em referência a Alonzo Church e Alan Turing, é uma hipótese sobre a natureza de artefatos mecânicos de cálculo, como computadores, e sobre que tipo de algoritmos eles podem executar. Geralmente assume-se que um algoritmo deve satisfazer os seguintes requisitos: O algoritmo consiste de um conjunto finito de instruções simples e precisas, que são descritas com um número finito de símbolos.
- Те́зис Чёрча — Тью́ринга — фундаментальное утверждение для многих областей науки, таких, как теория вычислимости, информатика, теоретическая кибернетика и др. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.
- Теза Черча — твердження, згідно з яким, клас алгоритмічно-обчислюваних функцій збігається з класом частково-рекурсивних функцій, функцій обчислюваних за Тюрінгом та інших формальних уточнень інтуїтивного поняття алгоритм.
|
![[RDF Data]](/statics/sw-cube.png)
