# Undecidability

Edited by Jordan Bohall (University of Illinois, Urbana-Champaign)
Related

Contents
23 found
Order:
1. The Turing machine halting problem can be explained by several factors, including arithmetic logic irreversibility and memory erasure, which contribute to computational uncertainty due to information loss during computation. Essentially, this means that an algorithm can only preserve information about an input, rather than generate new information. This uncertainty arises from characteristics such as arithmetic logical irreversibility, Landauer's principle, and memory erasure, which ultimately lead to a loss of information and an increase in entropy. To measure this uncertainty and loss (...)

Export citation

Bookmark
2. The conventional notion of a formal system is adapted to conform to the sound deductive inference model operating on finite strings. Finite strings stipulated to have the semantic property of Boolean true provide the sound deductive premises. Truth preserving finite string transformation rules provide valid the deductive inference. Conclusions of sound arguments are derived from truth preserving finite string transformations applied to true premises.

Export citation

Bookmark
3. The halting theorem counter-examples present infinitely nested simulation (non-halting) behavior to every simulating halt decider. The pathological self-reference of the conventional halting problem proof counter-examples is overcome. The halt status of these examples is correctly determined. A simulating halt decider remains in pure simulation mode until after it determines that its input will never reach its final state. This eliminates the conventional feedback loop where the behavior of the halt decider effects the behavior of its input.

Export citation

Bookmark
4. Introduction to mathematical logic. Part 2.Textbook for students in mathematical logic and foundations of mathematics. Platonism, Intuition, Formalism. Axiomatic set theory. Around the Continuum Problem. Axiom of Determinacy. Large Cardinal Axioms. Ackermann's Set Theory. First order arithmetic. Hilbert's 10th problem. Incompleteness theorems. Consequences. Connected results: double incompleteness theorem, unsolvability of reasoning, theorem on the size of proofs, diophantine incompleteness, Loeb's theorem, consistent universal statements are provable, Berry's paradox, incompleteness and Chaitin's theorem. Around Ramsey's theorem.

Export citation

Bookmark   2 citations
5. The Decision Problem for Effective Procedures.Nathan Salmón - 2023 - Logica Universalis 17 (2):161-174.
The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined even if it is not sufficiently formal and precise to belong to mathematics proper (in a narrow sense)—and even if (as many have asserted) for that reason the Church–Turing thesis is unprovable. It is proved logically that the class of effective procedures is not decidable, i.e., that no effective procedure is possible for ascertaining whether a given procedure is effective. This (...)

Export citation

Bookmark   1 citation
6. 'Godel's Way'에서 세 명의 저명한 과학자들은 부정성, 불완전성, 임의성, 계산성 및 파라불일치와 같은 문제에 대해 논의합니다. 나는 완전히 다른 해결책을 가지고 두 가지 기본 문제가 있다는 비트 겐슈타인의 관점에서 이러한 문제에 접근. 과학적 또는 경험적 문제가 있다, 관찰 하 고 철학적 문제 언어를 어떻게 이해할 수 있는 (수학 및 논리에 특정 질문을 포함) 에 대 한 조사 해야 하는 세계에 대 한 사실,우리가 실제로 특정 컨텍스트에서 단어를 사용 하는 방법을 보고 하 여 결정 될 필요가. 우리가 어떤 언어 게임을 하고 (...)

Export citation

Bookmark
7. ¿Cómo utilizar el Teorema de Herbrand para decidir la validez de razonamientos en lenguaje de primer orden, en conformidad con el Teorema de Indecidibilidad de Church?Franklin Galindo & María Alejandra Morgado - 2019 - Apuntes Filosóficos: Revista Semestral de la Escuela de Filosofía 18 (55):67-86.
This article’s objetive is to present four application examples of Herbrand’s theorem to decide the validity of reasoning on first order language, in accordance whit Church’s Undecidability’s theorem. Also, to tell which is the principal problem around it. The logical resolution calculus will be worked on this article, which is a method used in artificial intelligence.

Export citation

Bookmark
8. I give a detailed review of 'The Outer Limits of Reason' by Noson Yanofsky from a unified perspective of Wittgenstein and evolutionary psychology. I indicate that the difficulty with such issues as paradox in language and math, incompleteness, undecidability, computability, the brain and the universe as computers etc., all arise from the failure to look carefully at our use of language in the appropriate context and hence the failure to separate issues of scientific fact from issues of how language works. (...)

Export citation

Bookmark
9. Último sermón de la iglesia del naturalismo fundamentalista por el pastor Hofstadter. Al igual que su mucho más famoso (o infame por sus incesantemente errores filosóficos) trabajo Godel, Escher, Bach, tiene una plausibilidad superficial, pero si se entiende que se trata de un científico rampante que mezcla problemas científicos reales con los filosóficos (es decir, el sólo los problemas reales son los juegos de idiomas que debemos jugar) entonces casi todo su interés desaparece. Proporciono un marco para el análisis basado (...)

Export citation

Bookmark
10. On pense généralement que l'impossibilité, l'incomplétdulité, la paracohérence, l'indécidabilité, le hasard, la calcul, le paradoxe, l'incertitude et les limites de la raison sont des questions scientifiques physiques ou mathématiques disparates ayant peu ou rien dans terrain d'entente. Je suggère qu'ils sont en grande partie des problèmes philosophiques standard (c.-à-d., jeux de langue) qui ont été la plupart du temps résolus par Wittgenstein plus de 80 ans. Je fournis un bref résumé de quelques-unes des principales conclusions de deux des plus éminents (...)

Export citation

Bookmark
11. 关于在柴廷、维特根斯坦、霍夫施塔特、沃尔珀特、多里亚、达科斯塔、戈德尔、西尔、罗迪赫、贝托、弗洛伊德、贝托、弗洛伊德、莫亚尔-沙罗克和亚诺夫斯基.Michael Richard Starks - 2019 - Las Vegas, NV USA: Reality Press.
人们普遍认为，不可能性、不完整性、不一致性、不可度、随机性、可预见性、悖论、不确定性和理性极限是完全不同的科学物理或数学问题，在常见。我认为，它们主要是标准的哲学问题（即语言游戏），这些问题大多在80 多年前由维特根斯坦解决。 -/- "在这种情况下，我们'想说'当然不是哲学，而是它的原材料。因此，例如，数学家倾向于对数学事实的客观性和现实性说的，不是数学哲学，而是哲学处理的东西。维特根斯坦 PI 234 -/- "哲学家们经常看到科学的方法，他们不可抗拒地试图以科学的方式提问和回答问题。这种倾向是形而上学的真正源泉，将哲学家带入完全的黑暗之中。 维特根斯坦 -/- 我简要地总结了现代两位最杰出的学生路德维希·维特根斯坦和约翰·西尔关于故意的逻辑结构（思想、语言、行为）的一些主要发现，作为我的起点Wittgenstein 的基本发现——所有真正的"哲学"问题都是相同的——关于在特定上下文中如何使用语言的困惑，因此所有解决方案都是一样的——研究如何在相关上下文中使用语言，使其真实性条件（满意度或 COS 条件）是明确的。基本问题是，人们可以说什么，但一个人不能意味着（状态明确COS）任何任意的话语和意义只有在非常具体的上下文中才可能。 -/- 在两种思想体系的现代视角（被推广为"思维快，思维慢"）的框架内，我从维特根斯坦人的角度剖析了一些主要评论员关于这些问题的一些著作，并采用了一个新的表意向性和新的双系统命名法。 我表明，这是一个强大的启发式描述这些假定的科学，物理或数学问题的真实性质，这是真正最好的处理作为标准哲学问题，如何使用语言（语言游戏在维特根斯坦的术语）。 -/- 我的论点是，这里突出特征的意向表（理性、思想、思想、语言、个性等）或多或少地准确地描述了，或者至少作为启发式，我们思考和行为的方式，所以它包含不只是哲学和心理学，但其他一切（历史，文学，数学，政治等） 。特别要注意，我（以及西尔、维特根斯坦和其他人）认为，故意和理性包括有意识的审议语言系统2和无意识的自动预语言系统1行为或反射。 .

Export citation

Bookmark
12. Eu li muitas discussões recentes sobre os limites da computação e do universo como computador, na esperança de encontrar alguns comentários sobre o trabalho surpreendente do físico polimatemático e teórico da decisão David Wolpert, mas não encontrei uma única citação e assim que eu apresento este muito breve Resumo. Wolpert provou alguma impossibilidade impressionante ou teoremas da incompletude (1992 a 2008-Veja arxiv dot org) nos limites à inferência (computação) que são tão gerais que são independentes do dispositivo que faz a (...)

Export citation

Bookmark
13. معمولا تصور می شود که عدم امکان ، بی کامل بودن ، پارامونشتها ، Undecidability ، اتفاقی ، قابلیت های مختلف ، پارادوکس ، عدم قطعیت و محدودیت های دلیل ، مسائل فیزیکی و ریاضی علمی و یا با داشتن کمی یا هیچ چیز در مشترک. من پیشنهاد می کنم که آنها تا حد زیادی مشکلات فلسفی استاندارد (به عنوان مثال ، بازی های زبان) که عمدتا توسط ویتگنشتاین بیش از 80 سال پیش حل و فصل شد. -/- "آنچه ما (...)

Export citation

Bookmark
14. Hal ini sering berpikir bahwa kemustahilan, ketidaklengkapan, Paraconsistency, Undecidability, Randomness, komputasi, Paradox, ketidakpastian dan batas alasan yang berbeda ilmiah fisik atau matematika masalah memiliki sedikit atau tidak ada dalam Umum. Saya menyarankan bahwa mereka sebagian besar masalah filosofis standar (yaitu, Permainan bahasa) yang sebagian besar diselesaikan oleh Wittgenstein lebih dari 80years yang lalu. -/- "Apa yang kita ' tergoda untuk mengatakan ' dalam kasus seperti ini, tentu saja, bukan filsafat, tetapi bahan baku. Jadi, misalnya, apa yang seorang matematikawan cenderung mengatakan (...)

Export citation

Bookmark
15. El Programa original de David Hilbert y el Problema de la Decibilidad.Franklin Galindo & Ricardo Da Silva - 2017 - Episteme NS: Revista Del Instituto de Filosofía de la Universidad Central de Venezuela 37 (1):1-23.
En este artículo realizamos una reconstrucción del Programa original de Hilbert antes del surgimiento de los teoremas limitativos de la tercera década del siglo pasado. Para tal reconstrucción empezaremos por mostrar lo que Torretti llama los primeros titubeos formales de Hilbert, es decir, la defensa por el método axiomático como enfoque fundamentante. Seguidamente, mostraremos como estos titubeos formales se establecen como un verdadero programa de investigación lógico-matemático y como dentro de dicho programa la inquietud por la decidibilidad de los problemas (...)

Export citation

Bookmark
16. Wolpert, Chaitin and Wittgenstein on impossibility, incompleteness, the limits of computation, theism and the universe as computer-the ultimate Turing Theorem.Michael Starks - 2017 - Philosophy, Human Nature and the Collapse of Civilization Michael Starks 3rd Ed. (2017).
I have read many recent discussions of the limits of computation and the universe as computer, hoping to find some comments on the amazing work of polymath physicist and decision theorist David Wolpert but have not found a single citation and so I present this very brief summary. Wolpert proved some stunning impossibility or incompleteness theorems (1992 to 2008-see arxiv.org) on the limits to inference (computation) that are so general they are independent of the device doing the computation, and even (...)

Export citation

Bookmark
17. Pluralism and the Liar.Cory Wright - 2017 - In Bradley Armour-Garb (ed.), Reflections on the Liar. Oxford University Press. pp. 347–373.
Pluralists maintain that there is more than one truth property in virtue of which bearers are true. Unfortunately, it is not yet clear how they diagnose the liar paradox or what resources they have available to treat it. This chapter considers one recent attempt by Cotnoir (2013b) to treat the Liar. It argues that pluralists should reject the version of pluralism that Cotnoir assumes, discourse pluralism, in favor of a more naturalized approach to truth predication in real languages, which should (...)

Export citation

Bookmark   1 citation
18. Fourteen Arguments in Favour of a Formalist Philosophy of Real Mathematics.Karlis Podnieks - 2015 - Baltic Journal of Modern Computing 3 (1):1-15.
The formalist philosophy of mathematics (in its purest, most extreme version) is widely regarded as a “discredited position”. This pure and extreme version of formalism is called by some authors “game formalism”, because it is alleged to represent mathematics as a meaningless game with strings of symbols. Nevertheless, I would like to draw attention to some arguments in favour of game formalism as an appropriate philosophy of real mathematics. For the most part, these arguments have not yet been used or (...)

Export citation

Bookmark
19. The gödel paradox and Wittgenstein's reasons.Francesco Berto - 2009 - Philosophia Mathematica 17 (2):208-219.
An interpretation of Wittgenstein’s much criticized remarks on Gödel’s First Incompleteness Theorem is provided in the light of paraconsistent arithmetic: in taking Gödel’s proof as a paradoxical derivation, Wittgenstein was drawing the consequences of his deliberate rejection of the standard distinction between theory and metatheory. The reasoning behind the proof of the truth of the Gödel sentence is then performed within the formal system itself, which turns out to be inconsistent. It is shown that the features of paraconsistent arithmetics match (...)

Export citation

Bookmark   9 citations
20. Three concepts of decidability for general subsets of uncountable spaces.Matthew W. Parker - 2003 - Theoretical Computer Science 351 (1):2-13.
There is no uniquely standard concept of an effectively decidable set of real numbers or real n-tuples. Here we consider three notions: decidability up to measure zero [M.W. Parker, Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system, Phil. Sci. 70(2) (2003) 359–382], which we abbreviate d.m.z.; recursive approximability [or r.a.; K.-I. Ko, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991]; and decidability ignoring boundaries [d.i.b.; W.C. Myrvold, The decision problem for entanglement, in: R.S. (...)

Export citation

Bookmark   3 citations
21. Undecidability in Rn: Riddled basins, the KAM tori, and the stability of the solar system.Matthew W. Parker - 2003 - Philosophy of Science 70 (2):359-382.
Some have suggested that certain classical physical systems have undecidable long-term behavior, without specifying an appropriate notion of decidability over the reals. We introduce such a notion, decidability in (or d- ) for any measure , which is particularly appropriate for physics and in some ways more intuitive than Ko's (1991) recursive approximability (r.a.). For Lebesgue measure , d- implies r.a. Sets with positive -measure that are sufficiently "riddled" with holes are never d- but are often r.a. This explicates Sommerer (...)

Export citation

Bookmark   3 citations
22. Undecidability in the Spatialized Prisoner's Dilemma.Patrick Grim - 1997 - Theory and Decision 42 (1):53-80.
n the spatialized Prisoner’s Dilemma, players compete against their immediate neighbors and adopt a neighbor’s strategy should it prove locally superior. Fields of strategies evolve in the manner of cellular automata (Nowak and May, 1993; Mar and St. Denis, 1993a,b; Grim 1995, 1996). Often a question arises as to what the eventual outcome of an initial spatial configuration of strategies will be: Will a single strategy prove triumphant in the sense of progressively conquering more and more territory without opposition, or (...)