| dbo:abstract
|
- في نظرية القابلية للحساب، تعرف أطروحة تشرش-تورنغ Church-Turing Thesis، أو حدسية تشرش-تورنغ Church-Turing Conjecture، على أنها فرضية Hypothesis حول طبيعة الدوال الحسابية Computable functions. تنص الفرضية على أن الأعداد الطبيعية تكون قابلة للحساب بعقل إنساني وبخوارزمية، مع تجاهل القيود على الموارد، إذا وفقط كانت محسوبة باستخدام آلة تورنغ. الأطروحة سميت على عالم الرياضيات الأمريكي وعالم الرياضيات البريطاني آلان تورنغ. قبل التعريف الدقيق لنظرية الحاسوبية، علماء الرياضيات غالباً ماكانوا يستخدمون المصطلح غير الرسمي للحساب الفعال Effectively calculable لوصف الوظائف المحسوبة بأساليب ورقة وقلم رصاص. في الثلاثينات من القرن الماضي، بذلت محاولات مستقلة عدة لإضفاء الطابع الرسمي على مفهوم الحاسوبية. في نظرية الحوسبة، أطروحة تشرش - تورينغ (المعروفة أيضًا باسم أطروحة الحوسبة، أطروحة تورينج - تشيرش، تخمين تشيرش - تورينج، وأطروحة تشيرش، وتخمين تشيرش، وأطروحة تورينج) هي أطروحة حول الطبيعة من الوظائف الحسابية. تنص على أنه يمكن حساب دالة على الأعداد الطبيعية بطريقة فعالة إذا وفقط إذا كانت قابلة للحساب بواسطة آلة تورينج. تمت تسمية الأطروحة على اسم عالم الرياضيات الأمريكي ألونزو تشيرش وعالم الرياضيات البريطاني آلان تورينج. قبل التعريف الدقيق للوظيفة الحسابية، غالبًا ما استخدم علماء الرياضيات المصطلح غير الرسمي القابل للحساب بشكل فعال لوصف الوظائف التي يمكن حسابها بطرق الورق والقلم. في الثلاثينيات من القرن الماضي، جرت عدة محاولات مستقلة لإضفاء الطابع الرسمي على مفهوم الحوسبة:
* في عام 1933، قام كورت جودل، مع جاك هيربراند، بإضفاء الطابع الرسمي على تعريف فئة الوظائف العودية العامة: أصغر فئة من الوظائف (مع العديد من الحجج بشكل تعسفي) التي يتم إغلاقها تحت التكوين والتكرار والتقليل، وتتضمن صفرًا، وكل التوقعات.
* في عام 1936، أنشأ ألونزو تشيرش طريقة لتحديد الوظائف تسمى حساب التفاضل والتكامل. داخل حساب التفاضل والتكامل λ، حدد ترميزًا للأعداد الطبيعية يسمى أرقام تشيرش. تسمى الوظيفة على الأرقام الطبيعية تكامل لامدا (بالإنجليزية: λ-computable) إذا كان من الممكن تمثيل الوظيفة المقابلة في أرقام تشيرش بمصطلح λ-calculus.
* أيضًا في عام 1936، قبل تعلم عمل تشرش، ابتكر آلان تورينج نموذجًا نظريًا للآلات، تسمى الآن آلات تورينج، والتي يمكنها إجراء حسابات من المدخلات عن طريق التلاعب بالرموز الموجودة على شريط. بالنظر إلى تشفير مناسب للأرقام الطبيعية كتسلسل من الرموز، فإن الوظيفة الموجودة على الأرقام الطبيعية تسمى تورينغ القابلة للحساب إذا كانت بعض آلات تورينغ تحسب الوظيفة المقابلة على الأرقام الطبيعية المشفرة. أثبتت تشيرش وكلين وتورينغ [11] أن هذه الفئات الثلاثة المحددة رسميًا للوظائف الحسابية تتطابق: الوظيفة قابلة للحساب λ إذا وفقط إذا كانت تورينغ قابلة للحساب، وإذا وفقط إذا إنه تكراري عام. وقد دفع هذا علماء الرياضيات وعلماء الكمبيوتر إلى الاعتقاد بأن مفهوم الحوسبة يتميز بدقة بهذه العمليات المكافئة الثلاث. المحاولات الرسمية الأخرى لوصف القدرة الحسابية عززت هذا الاعتقاد لاحقًا (انظر أدناه). من ناحية أخرى، تنص أطروحة تشيرش - تورينغ على أن الفئات الثلاث المحددة رسميًا للوظائف الحسابية تتوافق مع المفهوم غير الرسمي لوظيفة قابلة للحساب بشكل فعال. على الرغم من أن الأطروحة تحظى بقبول شبه عالمي، إلا أنه لا يمكن إثباتها رسميًا لأن مفهوم إمكانية الحساب الفعال لا يتم تعريفه إلا بشكل غير رسمي. منذ نشأتها، نشأت اختلافات في الأطروحة الأصلية، بما في ذلك عبارات حول ما يمكن أن يتحقق جسديًا بواسطة الكمبيوتر في عالمنا (أطروحة تشيرش - تورنج المادية) وما يمكن حسابه بكفاءة (أطروحة تشيرش - تورينج (نظرية التعقيد)). لا تعود هذه الاختلافات إلى تشيرش أو تورينج، ولكنها تنشأ من العمل اللاحق في نظرية التعقيد والفيزياء الرقمية. الأطروحة لها أيضًا آثار على فلسفة العقل. (ar)
- La Tesi de Church-Turing, simplificant, es pot enunciar així: "Tot algorisme o procediment efectiu és Turing-computable". (ca)
- 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 stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.“ Diese These ist nicht beweisbar, da der Begriff „intuitiv berechenbare Funktion“ nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auf irgendeine Weise berechnet 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 wird es möglich, von einer Funktion nachzuweisen, dass sie nicht berechenbar ist. (de)
- V teorii vyčíslitelnosti se pojmy Churchova–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 dispozici dostatek času a paměti. Požadavky kladené na algoritmus: 1.
* 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ů. 2.
* Algoritmus vždy po konečném počtu kroků vrátí výsledek. 3.
* Algoritmus může provádět i člověk s tužkou a papírem. 4.
* Spuštění algoritmu nepotřebuje lidskou inteligenci, kromě 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 (např. Turingovým strojem) 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.) (cs)
- La Ĉurĉa tezo (aŭ Ĉurĉ-Turinga tezo) estas tezo pri komputeblaj funkcioj. Simple dirite, ĝi asertas ke ĉiu funkcio kiu estas algoritme komputebla (en intuicia senco de "algoritme komputebla") estas komputebla de Turinga aŭtomato. Ĉar ĝi parolas pri intuicia nocio, ĝi ne estas matematike preciza tezo kaj sekve ne pruveblas. La tezo estiĝis, ĉar diversaj formaligoj de la ideo de algoritma komputebleco estis pruveble egalvaloraj. Ĝi estis unue vortigita de Alonzo Ĉurĉo. (eo)
- In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing. Before the precise definition of computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods. In the 1930s, several independent attempts were made to formalize the notion of computability:
* In 1933, Kurt Gödel, with Jacques Herbrand, formalized the definition of the class of general recursive functions: the smallest class of functions (with arbitrarily many arguments) that is closed under composition, recursion, and minimization, and includes zero, successor, and all projections.
* In 1936, Alonzo Church created a method for defining functions called the λ-calculus. Within λ-calculus, he defined an encoding of the natural numbers called the Church numerals. A function on the natural numbers is called λ-computable if the corresponding function on the Church numerals can be represented by a term of the λ-calculus.
* Also in 1936, before learning of Church's work, Alan Turing created a theoretical model for machines, now called Turing machines, that could carry out calculations from inputs by manipulating symbols on a tape. Given a suitable encoding of the natural numbers as sequences of symbols, a function on the natural numbers is called Turing computable if some Turing machine computes the corresponding function on encoded natural numbers. Church, Kleene, and Turing proved that these three formally defined classes of computable functions coincide: a function is λ-computable if and only if it is Turing computable, and if and only if it is general recursive. This has led mathematicians and computer scientists to believe that the concept of computability is accurately characterized by these three equivalent processes. Other formal attempts to characterize computability have subsequently strengthened this belief (see ). On the other hand, the Church–Turing thesis states that the above three formally-defined classes of computable functions coincide with the informal notion of an effectively calculable function. Although the thesis has near-universal acceptance, it cannot be formally proven, as the concept of effective calculability is only informally defined. Since its inception, variations on the original thesis have arisen, including statements about what can physically be realized by a computer in our universe (physical Church-Turing thesis) and what can be efficiently computed. These variations are not due to Church or Turing, but arise from later work in complexity theory and digital physics. The thesis also has implications for the philosophy of mind (see ). (en)
- En teoría de la computabilidad, la tesis de Church-Turing formula hipotéticamente la equivalencia entre los conceptos de función computable y máquina de Turing, que expresado en lenguaje corriente vendría a ser "todo algoritmo es equivalente a una máquina de Turing". No es un teorema matemático, es una afirmación formalmente indemostrable que, no obstante, tiene una aceptación prácticamente universal. (es)
- La thèse de Church — du nom du mathématicien Alonzo Church — est une thèse concernant la définition de la notion de calculabilité. Dans une forme dite « physique », elle affirme que la notion physique de la calculabilité, définie comme étant tout traitement systématique réalisable par un processus physique ou mécanique, peut être exprimée par un ensemble de règles de calcul, défini de plusieurs façons dont on a pu démontrer mathématiquement qu'elles sont équivalentes. Dans sa forme dite « psychologique », elle affirme que la notion intuitive de calculabilité, qui est liée à ce qu'un être humain considère comme effectivement calculable ou non, peut également être exprimée par ces mêmes ensembles de règles de calcul formelles. Stephen Kleene fut le premier à nommer « thèse de Church » (en 1943 et 1952) ce que ce dernier présentait comme une définition de la calculabilité effective. Elle est également connue sous le nom plus récent 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é), ce sont cependant l'article d'Alan 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. (fr)
- Nella teoria della calcolabilità la tesi di Church-Turing è un'ipotesi che afferma: «Se un problema è umanamente calcolabile, allora esisterà una macchina di Turing in grado di risolverlo (cioè di calcolarlo)». Più formalmente possiamo dire che la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing. (it)
- チャーチ＝チューリングのテーゼ (Church-Turing thesis) もしくはチャーチのテーゼ (Church's thesis) とは、「計算できる関数」という直観的な概念を、帰納的関数と呼ばれる数論的関数のクラスと同一視しようという主張である。テーゼの代わりに提唱（ていしょう）あるいは定立（ていりつ）の語が用いられることもある。このクラスはチューリングマシンで実行できるプログラムのクラス、ラムダ記法で定義できる関数のクラスとも一致する。よって簡単にはテーゼは、計算が可能な関数とは、その計算を実行できるような有限のアルゴリズムが存在するような関数、よっておおよそコンピュータで実行できる関数と同じだと主張する。 (ja)
- 처치-튜링 논제(Church-Turing thesis)는 계산 가능한 함수에 대한 논제(thesis)이다. 간단히 요약하면, 어떤 함수는 튜링 기계가 계산할 수 있으면, 그리고 그 때만 알고리즘으로 계산 가능하다는 명제이다. 알론조 처치와 앨런 튜링의 이름을 따 지어졌다. 튜링 기계는 모든 범용 프로그래밍 언어로 번역될 수 있으므로, 이것은 어떤 컴퓨터에게든 충분한 시간과 메모리가 주어진다면 존재하는 모든 알고리즘의 결과를 출력할 수 있다는 명제와 동치이다. 처음 이 명제가 나왔을 때에는 "효과적으로 계산할 수 있는 (effectively computable) 함수"와 같이 비형식적인 표현을 사용했기 때문에 이 명제를 논리적으로 증명하는 것은 불가능했다. 이후 수학자들은 모호한 말 대신 계산 가능한 함수를 사용한다. 실제로 증명되거나 반증된 적은 없으며, 영원히 증명할 수 없을 것이라고 주장하는 학자도 있다. 다만 현재까지 인간이 발명한 모든 종류의 계산법(양자 컴퓨터를 포함하여)이 적절한 형태의 튜링 기계로 표현될 수 있음이 알려져 있다. (ko)
- 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 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. Hipotezę zaproponował po raz pierwszy Stephen Cole Kleene w 1943 roku, lecz została ona potwierdzona niezależnie przez Alonzo Churcha i Alana Turinga w 1936 roku. Najważniejszą konsekwencją tej tezy jest to, że ogólne rozwiązanie problemu rozstrzygalności, postawionego przez Davida Hilberta w 1928 roku, jest niemożliwe. (pl)
- De Church-Turing-hypothese (Engels: Church-Turing thesis) 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. (nl)
- Inom matematik och beräkningsteori innebär Church-Turings hypotespåståendet att en matematisk funktion är effektivt beräkningsbar om och endast om den kan beräknas med hjälp av en algoritm på en Turingmaskin, d.v.s. om beräkningarna kan utföras med någon annan godtycklig manuell eller mekanisk metod, så kan de också utföras av en sådan maskin. Tesen formulerades först av 1943 men är uppkallad efter Alonzo Church och Alan Turing. Flera försök gjordes under 1920- och 30-talen för att formalisera begreppet beräkningsbarhet:
* Amerikanske matematikern Alonzo Church skapade en metod för att definiera funktioner s.k. lambdakalkyl (λ-kalkyl),
* Brittiske matematikern Alan Turing skapade en teoretisk modell för en maskin, som nu kallas en universell Turingmaskin som kunde utföra beräkningar utifrån olika indata,
* Church skapade tillsammans med matematikern och logikern en formell definition av en klass av funktioner vars värden kan beräknas genom rekursion. Alla tre beräkningsprocesserna (rekursion, λ-kalkyl och Turingmaskinen) visade sig vara likvärdiga - de definierar samma klass av funktioner.Detta har lett matematiker och datavetare att anamma begreppet beräkningsbarhet som precist karaktäriserat av dessa tre likvärdiga processer - Om någon metod (algoritm) existerar för att utföra en beräkning, så kan samma beräkning också utföras av en Turingmaskin, en rekursivt definierbar funktion eller genom en λ-funktion. Church-Turing hypotesen har numera en mycket spridd acceptans, men trots detta är den grundläggande premissen bakom hypotesen - idén om vad det innebär för en funktion för att vara effektivt beräkningsbar - något vag och intuitiv, och hypotesen kan därför inte formellt bevisas utan förblir en hypotes. (sv)
- Те́зис Чёрча — Тью́ринга — это гипотеза, постулирующая эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга. В связи с интуитивностью исходного понятия алгоритмической вычислимости, данный тезис носит характер суждения об этом понятии и его невозможно строго доказать или опровергнуть. Перед точным определением вычислимой функции математики часто использовали неофициальный термин, «эффективно вычислимый» для описания функций, которые можно вычислить с помощью бумажно-карандашных методов. Тезис был высказан Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов. Существенен для многих областей науки и философии науки, в том числе для математической логики, теории доказательств, информатики, кибернетики. (ru)
- 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: 1.
* 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. 2.
* O algoritmo sempre produz resultado em um número finito de passos. 3.
* O algoritmo pode, a princípio, ser executado por um ser humano com apenas papel e lápis. 4.
* 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 e que todos os computadores são "iguais", variando apenas a capacidade de processamento. (pt)
- 邱奇-图灵论题（英語：Church–Turing thesis，又称邱奇-图灵猜想，邱奇论题，邱奇猜想，图灵论题）是一个关于可计算性理论的假设。该假设论述了关于函数特性的，可有效计算的函数值（用更现代的表述来说--在算法上可计算的)。简单来说，邱奇-图灵论题认为“任何在算法上可计算的问题同样可由图灵机计算”。 20世纪上半叶，对可计算性进行公式化表示的尝试有：
* 美国数学家阿隆佐·邱奇创建了称为λ演算的方法来定义函数。
* 英国数学家阿兰·图灵创建了可对输入进行运算的理论机器模型，现在被称为通用图灵机。
* 邱奇以及数学家斯蒂芬·科尔·克莱尼和逻辑学家一起定义了一类函数， 这种函数的值可使用递归方法计算。 这三个理论在直觉上似乎是等价的--它们都定义了同一类函数。因此，计算机科学家和数学家们相信，可计算性的精确定义已经出现。邱奇-图灵论题的非正式表述说：如果某个算法是可行的，那这个算法同样可以被图灵机，以及另外两个理论所实现。 虽然这三个理论被證明是等价的，但是其中的前提假设--“能够有效计算”是一个模糊的定义。因此，虽然这个假说已接近完全，但仍然不能由公式证明。 (zh)
- Теза Черча — твердження, згідно з яким, клас алгоритмічно-обчислюваних функцій збігається з класом частково-рекурсивних функцій, функцій обчислюваних за Тюрінгом та інших формальних уточнень інтуїтивного поняття алгоритм. З неї випливає, що якщо функція належить до класу певної формалізації алгоритмічно-обчислюваної функції, то вона є алгоритмічно-обчислювана. Теза не доводиться. А еквівалентність класів формалізмів підлягає доведенню, що і було зроблено. Названа на честь американського математика Алонзо Черча. Також виділяють тезу Черча-Тюрінга. (uk)
|
| rdfs:comment
|
- La Tesi de Church-Turing, simplificant, es pot enunciar així: "Tot algorisme o procediment efectiu és Turing-computable". (ca)
- La Ĉurĉa tezo (aŭ Ĉurĉ-Turinga tezo) estas tezo pri komputeblaj funkcioj. Simple dirite, ĝi asertas ke ĉiu funkcio kiu estas algoritme komputebla (en intuicia senco de "algoritme komputebla") estas komputebla de Turinga aŭtomato. Ĉar ĝi parolas pri intuicia nocio, ĝi ne estas matematike preciza tezo kaj sekve ne pruveblas. La tezo estiĝis, ĉar diversaj formaligoj de la ideo de algoritma komputebleco estis pruveble egalvaloraj. Ĝi estis unue vortigita de Alonzo Ĉurĉo. (eo)
- En teoría de la computabilidad, la tesis de Church-Turing formula hipotéticamente la equivalencia entre los conceptos de función computable y máquina de Turing, que expresado en lenguaje corriente vendría a ser "todo algoritmo es equivalente a una máquina de Turing". No es un teorema matemático, es una afirmación formalmente indemostrable que, no obstante, tiene una aceptación prácticamente universal. (es)
- Nella teoria della calcolabilità la tesi di Church-Turing è un'ipotesi che afferma: «Se un problema è umanamente calcolabile, allora esisterà una macchina di Turing in grado di risolverlo (cioè di calcolarlo)». Più formalmente possiamo dire che la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing. (it)
- チャーチ＝チューリングのテーゼ (Church-Turing thesis) もしくはチャーチのテーゼ (Church's thesis) とは、「計算できる関数」という直観的な概念を、帰納的関数と呼ばれる数論的関数のクラスと同一視しようという主張である。テーゼの代わりに提唱（ていしょう）あるいは定立（ていりつ）の語が用いられることもある。このクラスはチューリングマシンで実行できるプログラムのクラス、ラムダ記法で定義できる関数のクラスとも一致する。よって簡単にはテーゼは、計算が可能な関数とは、その計算を実行できるような有限のアルゴリズムが存在するような関数、よっておおよそコンピュータで実行できる関数と同じだと主張する。 (ja)
- 처치-튜링 논제(Church-Turing thesis)는 계산 가능한 함수에 대한 논제(thesis)이다. 간단히 요약하면, 어떤 함수는 튜링 기계가 계산할 수 있으면, 그리고 그 때만 알고리즘으로 계산 가능하다는 명제이다. 알론조 처치와 앨런 튜링의 이름을 따 지어졌다. 튜링 기계는 모든 범용 프로그래밍 언어로 번역될 수 있으므로, 이것은 어떤 컴퓨터에게든 충분한 시간과 메모리가 주어진다면 존재하는 모든 알고리즘의 결과를 출력할 수 있다는 명제와 동치이다. 처음 이 명제가 나왔을 때에는 "효과적으로 계산할 수 있는 (effectively computable) 함수"와 같이 비형식적인 표현을 사용했기 때문에 이 명제를 논리적으로 증명하는 것은 불가능했다. 이후 수학자들은 모호한 말 대신 계산 가능한 함수를 사용한다. 실제로 증명되거나 반증된 적은 없으며, 영원히 증명할 수 없을 것이라고 주장하는 학자도 있다. 다만 현재까지 인간이 발명한 모든 종류의 계산법(양자 컴퓨터를 포함하여)이 적절한 형태의 튜링 기계로 표현될 수 있음이 알려져 있다. (ko)
- De Church-Turing-hypothese (Engels: Church-Turing thesis) 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. (nl)
- 邱奇-图灵论题（英語：Church–Turing thesis，又称邱奇-图灵猜想，邱奇论题，邱奇猜想，图灵论题）是一个关于可计算性理论的假设。该假设论述了关于函数特性的，可有效计算的函数值（用更现代的表述来说--在算法上可计算的)。简单来说，邱奇-图灵论题认为“任何在算法上可计算的问题同样可由图灵机计算”。 20世纪上半叶，对可计算性进行公式化表示的尝试有：
* 美国数学家阿隆佐·邱奇创建了称为λ演算的方法来定义函数。
* 英国数学家阿兰·图灵创建了可对输入进行运算的理论机器模型，现在被称为通用图灵机。
* 邱奇以及数学家斯蒂芬·科尔·克莱尼和逻辑学家一起定义了一类函数， 这种函数的值可使用递归方法计算。 这三个理论在直觉上似乎是等价的--它们都定义了同一类函数。因此，计算机科学家和数学家们相信，可计算性的精确定义已经出现。邱奇-图灵论题的非正式表述说：如果某个算法是可行的，那这个算法同样可以被图灵机，以及另外两个理论所实现。 虽然这三个理论被證明是等价的，但是其中的前提假设--“能够有效计算”是一个模糊的定义。因此，虽然这个假说已接近完全，但仍然不能由公式证明。 (zh)
- Теза Черча — твердження, згідно з яким, клас алгоритмічно-обчислюваних функцій збігається з класом частково-рекурсивних функцій, функцій обчислюваних за Тюрінгом та інших формальних уточнень інтуїтивного поняття алгоритм. З неї випливає, що якщо функція належить до класу певної формалізації алгоритмічно-обчислюваної функції, то вона є алгоритмічно-обчислювана. Теза не доводиться. А еквівалентність класів формалізмів підлягає доведенню, що і було зроблено. Названа на честь американського математика Алонзо Черча. Також виділяють тезу Черча-Тюрінга. (uk)
- في نظرية القابلية للحساب، تعرف أطروحة تشرش-تورنغ Church-Turing Thesis، أو حدسية تشرش-تورنغ Church-Turing Conjecture، على أنها فرضية Hypothesis حول طبيعة الدوال الحسابية Computable functions. تنص الفرضية على أن الأعداد الطبيعية تكون قابلة للحساب بعقل إنساني وبخوارزمية، مع تجاهل القيود على الموارد، إذا وفقط كانت محسوبة باستخدام آلة تورنغ. الأطروحة سميت على عالم الرياضيات الأمريكي وعالم الرياضيات البريطاني آلان تورنغ. قبل التعريف الدقيق لنظرية الحاسوبية، علماء الرياضيات غالباً ماكانوا يستخدمون المصطلح غير الرسمي للحساب الفعال Effectively calculable لوصف الوظائف المحسوبة بأساليب ورقة وقلم رصاص. في الثلاثينات من القرن الماضي، بذلت محاولات مستقلة عدة لإضفاء الطابع الرسمي على مفهوم الحاسوبية. (ar)
- V teorii vyčíslitelnosti se pojmy Churchova–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 dispozici dostatek času a paměti. Požadavky kladené na algoritmus: (cs)
- 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 stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.“ (de)
- In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing. Before the precise definition of computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods. In the 1930s, several independent attempts were made to formalize the notion of computability: (en)
- La thèse de Church — du nom du mathématicien Alonzo Church — est une thèse concernant la définition de la notion de calculabilité. Dans une forme dite « physique », elle affirme que la notion physique de la calculabilité, définie comme étant tout traitement systématique réalisable par un processus physique ou mécanique, peut être exprimée par un ensemble de règles de calcul, défini de plusieurs façons dont on a pu démontrer mathématiquement qu'elles sont équivalentes. (fr)
- 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. (pl)
- 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: Um exemplo de tal método é o algoritmo de Euclides para a determinação do máximo divisor comum de dois números naturais. (pt)
- Inom matematik och beräkningsteori innebär Church-Turings hypotespåståendet att en matematisk funktion är effektivt beräkningsbar om och endast om den kan beräknas med hjälp av en algoritm på en Turingmaskin, d.v.s. om beräkningarna kan utföras med någon annan godtycklig manuell eller mekanisk metod, så kan de också utföras av en sådan maskin. Tesen formulerades först av 1943 men är uppkallad efter Alonzo Church och Alan Turing. Flera försök gjordes under 1920- och 30-talen för att formalisera begreppet beräkningsbarhet: (sv)
- Те́зис Чёрча — Тью́ринга — это гипотеза, постулирующая эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга. В связи с интуитивностью исходного понятия алгоритмической вычислимости, данный тезис носит характер суждения об этом понятии и его невозможно строго доказать или опровергнуть. Перед точным определением вычислимой функции математики часто использовали неофициальный термин, «эффективно вычислимый» для описания функций, которые можно вычислить с помощью бумажно-карандашных методов. (ru)
|
