Undecidability

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 (...) of information, the concept of arithmetic logical entropy can be used. The Turing machine and its equivalent, general recursive functions can be understood through the λ calculus and the Turing/Church thesis. However, there are certain recursive functions that cannot be fully understood or predicted by other algorithms due to the loss of information during logical-arithmetic operations. In other words, the behaviour of these functions cannot be completely determined at every stage of the computation due to a lack of information in their definition. While there are some cases where the behaviour of recursive functions is highly predictable, the lack of information in most cases makes it impossible for algorithms to determine if a program will halt or not. This inability to predict the outcome of the computation is the essence of the halting problem of the Turing machine. Even in cases where more information is available about the program, it is still difficult to determine with certainty if the program will halt or not. This also highlights the importance of the Turing oracle machine, which introduces information from outside the computation to compensate for the lack of information and ultimately decide the result of the computation. (shrink)

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.

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.

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.

According to Thomasson’s Easy Ontology, all existential questions have straightforward answers and are solvable by conceptual and empirical work. So there is no need for traditional metaphysics to solve them. First, I give some counterexamples to this thesis from incomplete and undecidable theories. Then I discuss some possible responses, I consider a wider sense of conceptual analysis and argue that even in this sense Easy ontology is not able to resolve the problem and must sacrifice either easiness or answerability. Finally, (...) I will argue that although traditional metaphysics does not make the undecidable sentences answerable, it can still make sense of them and helps us to understand why there are unanswerable questions at all. (shrink)

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 (...) undecidability result is proved directly from the notion itself of an effective procedure, without reliance on any (partly) mathematical lemma, conjecture, or thesis invoking recursiveness or Turing-computability. In fact, there is no reliance on anything very mathematical. The proof does not even appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of an effective procedure. Though the result that effectiveness is undecidable is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure invariably terminates with the correct verdict. (shrink)

In this paper we explore the following question: how weak can a logic be for Rosser's essential undecidability result to be provable for a weak arithmetical theory? It is well known that Robinson's Q is essentially undecidable in intuitionistic logic, and P. Hajek proved it in the fuzzy logic BL for Grzegorczyk's variant of Q which interprets the arithmetic operations as non-total non-functional relations. We present a proof of essential undecidability in a much weaker substructural logic and for a much (...) weaker arithmetic theory, a version of Robinson's R (with arithmetic operations also interpreted as mere relations). Our result is based on a structural version of the undecidability argument introduced by Kleene and we show that it goes well beyond the scope of the Boolean, intuitionistic, or fuzzy logic. (shrink)

We study computable PAC (CPAC) learning as introduced by Agarwal et al. (2020). First, we consider the main open question of finding characterizations of proper and improper CPAC learning. We give a characterization of a closely related notion of strong CPAC learning, and provide a negative answer to the COLT open problem posed by Agarwal et al. (2021) whether all decidably representable VC classes are improperly CPAC learnable. Second, we consider undecidability of (computable) PAC learnability. We give a simple general (...) argument to exhibit such ndecidability, and initiate a study of the arithmetical complexity of learnability. We briefly discuss the relation to the undecidability result of Ben-David et al. (2019), that motivated the work of Agarwal et al. (shrink)

Rybakov proved that the admissible rules of $\mathsf {IPC}$ are decidable. We give a proof of the same theorem, using the same core idea, but couched in the many notions that have been developed in the mean time. In particular, we illustrate how the argument can be interpreted as using refinements of the notions of exactness and extendibility.

This textbook is a logic manual which includes an elementary course and an advanced course. It covers more than most introductory logic textbooks, while maintaining a comfortable pace that students can follow. The technical exposition is clear, precise and follows a paced increase in complexity, allowing the reader to get comfortable with previous definitions and procedures before facing more difficult material. The book also presents an interesting overall balance between formal and philosophical discussion, making it suitable for both philosophy and (...) more formal/science oriented students. This textbook is of great use to undergraduate philosophy students, graduate philosophy students, logic teachers, undergraduates and graduates in mathematics, computer science or related fields in which logic is required. (shrink)

We study the decidability of k-provability in \—the relation ‘being provable in \ with at most k steps’—and the decidability of the proof-skeleton problem—the problem of deciding if a given formula has a proof that has a given skeleton. The decidability of k-provability for the usual Hilbert-style formalisation of \ is still an open problem, but it is known that the proof-skeleton problem is undecidable for that theory. Using new methods, we present a characterisation of some numbers k for which (...) k-provability is decidable, and we present a characterisation of some proof-skeletons for which one can decide whether a formula has a proof whose skeleton is the considered one. These characterisations are natural and parameterised by unification algorithms. (shrink)

We show that the set of natural numbers has an exponential diophantine definition in the rationals. It follows that the corresponding decision problem is undecidable.

'Godel's Way'에서 세 명의 저명한 과학자들은 부정성, 불완전성, 임의성, 계산성 및 파라불일치와 같은 문제에 대해 논의합니다. 나는 완전히 다른 해결책을 가지고 두 가지 기본 문제가 있다는 비트 겐슈타인의 관점에서 이러한 문제에 접근. 과학적 또는 경험적 문제가 있다, 관찰 하 고 철학적 문제 언어를 어떻게 이해할 수 있는 (수학 및 논리에 특정 질문을 포함) 에 대 한 조사 해야 하는 세계에 대 한 사실,우리가 실제로 특정 컨텍스트에서 단어를 사용 하는 방법을 보고 하 여 결정 될 필요가. 우리가 어떤 언어 게임을 하고 (...) 있는지 명확히 알 면, 이 주제는 다른 언어와 마찬가지로 평범한 과학적이고 수학적 질문으로 보입니다. 비트겐슈타인의 통찰력은 거의 동등하지 않았고 결코 능가하지 않았으며, 그가 블루와 브라운 북을 지시했을 때 80 년 전과 마찬가지로 오늘날과 관련이 있습니다. 완성된 책이 아닌 일련의 노트가 실패했음에도 불구하고, 이것은 반세기 이상 물리학, 수학, 철학의 출혈 가장자리에서 일해온 이 세 명의 유명한 학자들의 작품의 독특한 원천입니다. 다 코스타와 도리아는 울퍼트에 의해 인용된다 (그들은 보편적 인 계산에 쓴 이후 울퍼트와 야노프스키의 '이성의 외부 한계'에 대한 내 리뷰에, 대한 내 리뷰) 그리고 그의 많은 업적 중, 다 코스타는 파라 불일치의 선구자입니다. 현대 의 두 systems보기에서인간의 행동에 대한 포괄적 인 최신 프레임 워크를 원하는 사람들은 내 책을 참조 할 수 있습니다'철학의 논리적 구조, 심리학, 민d와 루드비히 비트겐슈타인과 존 Searle의언어' 2nd ed (2019). 내 글의 더 많은 관심있는 사람들은 '이야기 원숭이를 볼 수 있습니다-철학, 심리학, 과학, 종교와 운명 행성에 정치 - 기사 및 리뷰 2006-2019 3 rd 에드 (2019) 및 21st 세기 4번째 에드 (2019) 및 기타에서 자살 유토피아 망상. (shrink)

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.

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. (...) I discuss Wittgenstein's views on incompleteness, paraconsistency and undecidability and the work of Wolpert on the limits to computation. To sum it up: The Universe According to Brooklyn---Good Science, Not So Good Philosophy. -/- Those wishing a comprehensive up to date framework for human behavior from the modern two systems view may consult my book ‘The Logical Structure of Philosophy, Psychology, Mind and Language in Ludwig Wittgenstein and John Searle’ 2nd ed (2019). Those interested in more of my writings may see ‘Talking Monkeys--Philosophy, Psychology, Science, Religion and Politics on a Doomed Planet--Articles and Reviews 2006-2019 3rd ed (2019) and Suicidal Utopian Delusions in the 21st Century 4th ed (2019) . (shrink)

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

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 (...) étudiants du comportement des temps modernes, Ludwig Wittgenstein et John Searle, sur la structure logique de l'intentionnalité (esprit, langue, comportement), en prenant comme point de départ La découverte fondamentale de Wittgenstein, à savoir que tous les problèmes véritablement « philosophiques » sont les mêmes, les confusions sur la façon d'utiliser la langue dans un contexte particulier, et donc toutes les solutions sont les mêmes— en regardant comment la langue peut être utilisée dans le contexte en cause afin que sa vérité (Conditions de satisfaction ou COS) sont claires. Le problème fondamental est que l'on peut dire n'importe quoi, mais on ne peut pas signifier (état clair COS pour) toute déclaration arbitraire et le sens n'est possible que dans un contexte très spécifique. Je dissé que quelques écrits de quelques-uns des principaux commentateurs sur ces questions d'un point de vue wittgensteinien dans le cadre de la perspective moderne des deux systèmes de pensée (popularisé comme «penser vite, penser lentement»), en utilisant une nouvelle table de intentionnalité et la nomenclature de nouveaux systèmes doubles. Je montre qu'il s'agit d'un puissant heuristique pour décrire la vraie nature de ces questions scientifiques, physiques ou mathématiques putatives qui sont vraiment mieux abordés comme des problèmes philosophiques standard de la façon dont la langue doit être utilisée (jeux de langue dans Wittgenstein terminologie). (shrink)

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 (...) computação, e mesmo independente das leis da física, para que eles se apliquem em computadores, física e comportamento humano. Eles fazem uso da diagonalização de cantor, o paradoxo mentiroso e worldlines (linhas do mundo) para fornecer o que pode ser o teorema final na teoria da máquina de Turing, e, aparentemente, fornecer insights sobre a impossibilidade, incompletude, os limites da computação, e do universo como computador, em todos os universos possíveis e todos os seres ou mecanismos, gerando, entre outras coisas, um princípio de incerteza mecânica não quântica e uma prova de monoteísmo. Há umas conexões óbvias ao trabalho clássico de Chaitin, Solomonoff, Komolgarov e Wittgenstein e à noção que nenhum programa (e assim nenhum dispositivo) pode gerar uma seqüência (ou dispositivo) com maior complexidade do que possui. Pode-se dizer que este corpo de trabalho implica ateísmo, uma vez que não pode haver qualquer entidade mais complexa do que o universo físico e do ponto de vista Wittgensteiniano, ' mais complexo ' é sem sentido (não tem condições de satisfação, ou seja, criador de verdade ou teste). Mesmo um ' Deus ' (ou seja, um ' dispositivo ' com tempo ilimitado/espaço e energia) não pode determinar se um determinado ' número ' é ' aleatório ', nem encontrar uma determinada maneira de mostrar que uma determinada ' fórmula ', ' teorema ' ou ' sentença ' ou ' Device ' (todos estes sendo linguagem complexa jogos) faz parte de um determinado «sistema». Aqueles que desejam um quadro até à data detalhado para o comportamento humano da opinião moderna dos dois sistemas consultar meu livros Falando Macacos 3ª Ed (2019), A Estrutura Lógica da Filosofia, Psicologia, Mente e Linguagem em Ludwig Wittgenstein e John Searle 2a Ed (2019), Suicídio Pela Democracia,4aEd(2019), Entendendo as Conexões entre Ciência, Filosofia, Psicologia, Religião, Política e Economia Artigos e Análises 2006-2019 (2019), Ilusões Utópicas Suicidas no 21St século 5a Ed (2019), A Estrutura Lógica do Comportamento Humano (2019), e A Estrutura Lógica da Consciência (2019) y outras. (shrink)

معمولا تصور می شود که عدم امکان ، بی کامل بودن ، پارامونشتها ، Undecidability ، اتفاقی ، قابلیت های مختلف ، پارادوکس ، عدم قطعیت و محدودیت های دلیل ، مسائل فیزیکی و ریاضی علمی و یا با داشتن کمی یا هیچ چیز در مشترک. من پیشنهاد می کنم که آنها تا حد زیادی مشکلات فلسفی استاندارد (به عنوان مثال ، بازی های زبان) که عمدتا توسط ویتگنشتاین بیش از 80 سال پیش حل و فصل شد. -/- "آنچه ما (...) وسوسه می گویند" در چنین موردی است ، البته ، نه فلسفه ، اما آن مواد خام است. بنابراین ، برای مثال ، چه ریاضیدان تمایل به در مورد عینیت و واقعیت حقایق ریاضی می گویند ، فلسفه ریاضیات نیست ، اما چیزی برای درمان فلسفی است. ویتگنشتاین PI ۲۳۴ -/- "فلاسفه به طور مداوم به روش علم قبل از چشم خود را ببینید و irresistibly وسوسه به درخواست و پاسخ به سوالات در علم راه می کند. این گرایش ، منبع واقعی متافیزیک است و فیلسوف را به تاریکی کامل هدایت می کند.» ویتگنشتاین -/- من ارائه خلاصه ای از برخی از یافته های عمده ای از دو نفر از برجسته ترین دانش آموزان از رفتار دوران مدرن ، لودویگ ویتگنشتاین و جان سرل ، در ساختار منطقی از قصدمندی (ذهن ، زبان ، رفتار) ، با توجه به عنوان نقطه شروع من کشف بنیادی ویتگنشتاین-که همه مشکلات فلسفی آن یکسان هستند-ابهامات در مورد چگونگی استفاده از زبان در یک چارچوب خاص ، و به همین ترتیب تمام راه حل ها یکسان هستند-به دنبال چگونه زبان را می توان در زمینه مورد استفاده قرار گیرد به طوری که حقیقت آن شرایط (شرایط رضایت یا COS) روشن است. مشکل اساسی این است که می توان هر چیزی می گویند، اما یکی نمی تواند به معنای (دولت از COS برای) هر گفته های خودسرانه و معنی تنها در یک زمینه بسیار خاص ممکن است. -/- من برخی از نوشته های چند تن از مفسران عمده در این مسائل از نظر Wittgensteinian در چارچوب دیدگاه مدرن از دو سیستم اندیشه (به عنوان "فکر سریع ، تفکر آهسته ') ، استفاده از جدول جدید قصدمندی سیستم های جدید دوگانه نامگذاری. من نشان می دهم که این یک اکتشافی قدرتمند برای توصیف ماهیت واقعی این مسائل علمی ، فیزیکی یا ریاضی است که واقعا بهترین هستند به عنوان مشکلات فلسفی استاندارد چگونه زبان مورد استفاده قرار گیرد (بازی های زبان در ویتگنشتاین اصطلاحات). -/- این مشاجره من است که جدول از معنایی (عقلانیت ، ذهن ، فکر ، زبان ، شخصیت و غیره) که ویژگی های برجسته در اینجا توصیف بیشتر یا کمتر با دقت ، و یا حداقل به عنوان یک اکتشافی برای ، چگونه ما فکر می کنیم و رفتار ، و پس از آن را شامل نمی صرفا فلسفه و روانشناسی ، اما هر چیز دیگری (تاریخ ، ادبیات ، ریاضیات ، سیاست و غیره). توجه داشته باشید به خصوص که قصدمندی و عقلانیت به عنوان من (همراه با سرل ، ویتگنشتاین و دیگران) آن را مشاهده کنید ، شامل هر دو آگاهانه سیستم زبانی ، 2 و ناخودآگاه خودکار سیستم پیش زبانی 1 اقدامات یا رفلکس. (shrink)

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 (...) tentang objektivitas dan realitas fakta matematika, bukan filsafat matematika, tetapi sesuatu untuk pengobatan filosofis. " Wittgenstein PI 234 -/- "Filsuf terus melihat metode ilmu di depan mata mereka dan tak tertahankan tergoda untuk bertanya dan menjawab pertanyaan dalam cara ilmu tidak. Kecenderungan ini adalah sumber nyata metafisika dan memimpin filsuf menjadi gelap gulita. " Wittgenstein -/- Aku memberikan ringkasan singkat dari beberapa temuan utama dari dua siswa yang paling terkemuka perilaku zaman modern, Ludwig Wittgenstein dan John Searle, pada struktur Logis intensionality (pikiran, bahasa, perilaku), mengambil sebagai titik awal Penemuan fundamental Wittgenstein – bahwa semua masalah ' filosofis ' adalah sama — kebingungan tentang bagaimana menggunakan bahasa dalam konteks tertentu, sehingga semua solusi sama — melihat bagaimana bahasa dapat digunakan dalam konteks yang menjadi masalah sehingga kebenaranNya kondisi (kondisi kepuasan atau COS) jelas. Masalah dasar adalah bahwa seseorang dapat mengatakan apa-apa, tetapi orang tidak dapat berarti (negara yang jelas cos untuk) sembarang ucapan dan makna hanya mungkin dalam konteks yang sangat spesifik. -/- Saya membedah beberapa tulisan dari beberapa komentator utama pada isu ini dari sudut pandang Wittgensteinian dalam kerangka perspektif modern dari dua sistem pemikiran (Dipopulerkan sebagai ' berpikir cepat, berpikir lambat '), mempekerjakan meja baru intensionality dan baru sistem ganda nomenklatur. Saya menunjukkan bahwa ini adalah heuristik yang kuat untuk menggambarkan sifat sebenarnya dari hal ini ilmiah, fisik atau matematika masalah yang benar-benar terbaik didekati sebagai masalah filosofis standar bagaimana bahasa yang akan digunakan (permainan bahasa di Wittgenstein's terminologi). -/- Ini adalah pendapat saya bahwa tabel intensionality (rasionalitas, pikiran, pikiran, bahasa, kepribadian dll) yang fitur mencolok di sini menggambarkan lebih atau kurang akurat, atau setidaknya berfungsi sebagai heuristic untuk, bagaimana kita berpikir dan berperilaku, dan sehingga mencakup tidak hanya filsafat dan psikologi, tetapi segala sesuatu yang lain (sejarah, sastra, matematika, politik dll). Perhatikan terutama bahwa intensionalitas dan rasionalitas sebagai I (bersama dengan Searle, Wittgenstein dan lain-lain) melihatnya, mencakup baik sistem linguistik pertimbangan sadar 2 dan tidak disadari otomatis sistem prelinguistik 1 tindakan atau refleks. (shrink)

Ú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 (...) en la psicología evolutiva y el trabajo de Wittgenstein (ya actualizado en mis escritos más recientes). -/- Aquellos que deseen un marco completo hasta la fecha para el comportamiento humano de la moderna dos sistemas punta de vista puede consultar mi libro 'La estructura lógica de la filosofía, la psicología, la mente y lenguaje En Ludwig Wittgenstein y John Searle ' 2a ED (2019). Los interesados en más de mis escritos pueden ver 'Monos parlantes--filosofía, psicología, ciencia, religión y política en un planeta condenado--artículos y reseñas 2006-2019 3a ED (2019) y Delirios utópicos suicidas en el siglo 21 4a Ed (2019) y otras. -/- "Podría ser justamente preguntado qué importancia tiene la prueba de Gödel para nuestro trabajo. Para un pedazo de matemáticas no puede resolver problemas del tipo que nos molesten. --La respuesta es que la situación, en la que tal prueba nos trae, es de interés para nosotros. ' ¿Qué vamos a decir ahora? ' --Ese es nuestro tema. Sin embargo, extraña que suene, mi tarea en lo que concierne a la prueba de Gödelparece meramente consistir en aclarar lo que tal proposición como: "Supongamos que esto se puede demostrar" significa en matemáticas. " Wittgenstein "Comentarios sobre los fundamentos de las matemáticas" p337 (1956) (escrito en 1937). (shrink)

The present paper has three objectives: Presenting an actualization of a proof of the decidability of monadic predicates logic in the contemporary model theory context; Show examples of decidable and undecidable fragments inside First order logic, offering an original proof of the following theorem: Any formula of First of order logic is decidable if its prenex normal form is in the following form: ∀x1,…,∀xn∃y1,…,∃ymφ; Presenting a theorem that characterizes the validity of First order logic by the tautologicity of Propositional logic, (...) said result is interesting since immediately arises the doubt of how to conciliate said characterization with Alonzo Church’s Undecidability Theorem for First Order Logic. (shrink)

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 (...) matemáticos y en específico la decidibilidad de la Lógica de primer orden cobra peso. Luego pasamos a analizar como la inquietud por la decibilidad toma lugar dentro del pensamiento filosófico-matemático de Hilbert presentándose como uno de los grandes problemas a los cuales la metamatemática debe encontrar una solución, esto lo hacemos mostrando un contraste con autores, como John von Neumann y Roberto Torretti, quienes de alguna u otra manera no interpretan el problema de la decidibilidad de la Lógica de primer orden como un problema de peso dentro del programa original de Hilbert. Finalmente argumentamos que el resultado meta-teórico de Church puede entenderse como una refutación del optimismo intelectual que permea a todo el programa original de Hilbert. (shrink)

Church's Undecidability Theorem is one of the meta-theoretical results of the mid-third decade of the last century, which along with other limiting theorems such as those of Gödel and Tarski have generated endless reflections and analyzes, both within the framework of the formal sciences, that is, mathematics, logic and theoretical computation, as well as outside them, especially the philosophy of mathematics, philosophy of logic and philosophy of mind. We propose, as a general purpose of this article, to formulate Church's Undecidability (...) Theorem and present the main ideas of its demonstration. In order to carry out the first objective, we need to introduce and explain the notions of recursive function and numbering used by Gödel, which will allow to formally and rigorously enunciate Church's Theorem. After we enunciate Church's Theorem of Unspeakability in a formal and rigorous manner, we will present the main ideas of the proof of Church's Undecidability Theorem for First Order Logic, which uses Robinson's axiomatic system for arithmetic and four facts about himself: In Robinson's system for arithmetic recursive functions are representable Robinson's system is undecidable, The number of axioms proper to the Robinson system is finite and The logical calculation of the Robinson system is equal to the calculation of the first-order logic. (shrink)

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 (...) independent of the laws of physics, so they apply across computers, physics, and human behavior. They make use of Cantor's diagonalization, the liar paradox and worldlines to provide what may be the ultimate theorem in Turing Machine Theory, and seemingly provide insights into impossibility, incompleteness, the limits of computation,and the universe as computer, in all possible universes and all beings or mechanisms, generating, among other things,a non- quantum mechanical uncertainty principle and a proof of monotheism. There are obvious connections to the classic work of Chaitin, Solomonoff, Komolgarov and Wittgenstein and to the notion that no program (and thus no device) can generate a sequence (or device) with greater complexity than it possesses. One might say this body of work implies atheism since there cannot be any entity more complex than the physical universe and from the Wittgensteinian viewpoint, ‘more complex’ is meaningless (has no conditions of satisfaction, i.e., truth-maker or test). Even a ‘God’ (i.e., a ‘device’ with limitless time/space and energy) cannot determine whether a given ‘number’ is ‘random’ nor can find a certain way to show that a given ‘formula’, ‘theorem’ or ‘sentence’ or ‘device’ (all these being complex language games) is part of a particular ‘system’. -/- Those wishing a comprehensive up to date framework for human behavior from the modern two systems view may consult my article The Logical Structure of Philosophy, Psychology, Mind and Language as Revealed in Wittgenstein and Searle 59p(2016). For all my articles on Wittgenstein and Searle see my e-book ‘The Logical Structure of Philosophy, Psychology, Mind and Language in Wittgenstein and Searle 367p (2016). Those interested in all my writings in their most recent versions may consult my e-book Philosophy, Human Nature and the Collapse of Civilization - Articles and Reviews 2006-2016’ 662p (2016). -/- All of my papers and books have now been published in revised versions both in ebooks and in printed books. -/- Talking Monkeys: Philosophy, Psychology, Science, Religion and Politics on a Doomed Planet - Articles and Reviews 2006-2017 (2017) https://www.amazon.com/dp/B071HVC7YP. -/- The Logical Structure of Philosophy, Psychology, Mind and Language in Ludwig Wittgenstein and John Searle--Articles and Reviews 2006-2016 (2017) https://www.amazon.com/dp/B071P1RP1B. -/- Suicidal Utopian Delusions in the 21st century: Philosophy, Human Nature and the Collapse of Civilization - Articles and Reviews 2006-2017 (2017) https://www.amazon.com/dp/B0711R5LGX . (shrink)

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 (...) be a desideratum on any successful pluralist conception. Appealing to determination pluralism instead, which focuses on truth properties, it then proposes an alternative treatment to the Liar that shows liar sentences to be undecidable. (shrink)

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 (...) were neglected in past discussions. (shrink)

The signature of the formal language of mereotopology contains two predicates $P$ and $C$, which stand for “being a part of” and “contact,” respectively. This paper will deal with the decidability issue of the mereotopological theories which can be formed by the axioms found in the literature. Three main results to be given are as follows: all axiomatized mereotopological theories are separable; all mereotopological theories up to $\mathbf{ACEMT}$, $\mathbf{SACEMT}$, or $\mathbf{SACEMT}^{\prime}$ are finitely inseparable; all axiomatized mereotopological theories except $\mathbf{SAX}$, $\mathbf{SAX}^{\prime}$, (...) or $\mathbf{S\overline{B}X}^{\prime}$, where $\mathbf{X}$ is strictly stronger than $\mathbf{CEMT}$, are undecidable. Then it can also be easily seen that all axiomatized mereotopological theories proved to be undecidable here are neither essentially undecidable nor strongly undecidable but are hereditarily undecidable. Result will be shown by constructing strongly undecidable mereotopological structures based on two-dimensional Euclidean space, and it will be pointed out that the same construction cannot be carried through if the language is not rich enough. (shrink)

The signature of the formal language of mereology contains only one binary predicate which stands for the relation “being a part of” and it has been strongly suggested that such a predicate must at least define a partial ordering. Mereological theories owe their origin to Leśniewski. However, some more recent authors, such as Simons as well as Casati and Varzi, have reformulated mereology in a way most logicians today are familiar with. It turns out that any theory which can be (...) formed by using the reformulated mereological axioms or axiom schemas is in a sense a subtheory of the elementary theory of Boolean algebras or of the theory of infinite atomic Boolean algebras. It is known that the theory of partial orderings is undecidable while the elementary theory of Boolean algebras and the theory of infinite atomic Boolean algebras are decidable. In this paper, I will look into the behaviors in terms of decidability of those mereological theories located in between. More precisely, I will give a comprehensive picture of the said issue by offering solutions to the open problems which I have raised in some of my papers published previously. (shrink)

How do we prove true but unprovable propositions? Gödel produced a statement whose undecidability derives from its ad hoc construction. Concrete or mathematical incompleteness results are interesting unprovable statements of formal arithmetic. We point out where exactly the unprovability lies in the ordinary ‘mathematical’ proofs of two interesting formally unprovable propositions, the Kruskal-Friedman theorem on trees and Girard's normalization theorem in type theory. Their validity is based on robust cognitive performances, which ground mathematics in our relation to space and time, (...) such as symmetries and order, or on the generality of Herbrand's notion of ‘prototype proof’. (shrink)

Quite a few results concerning the decidability of mereological theories have been given in my previous paper. But many mereological theories are still left unaccounted for. In this paper I will refine a general method for proving the undecidability of a theory and then by making use of it, I will show that most mereological theories that are strictly weaker than CEM are finitely inseparable and hence undecidable. The same results might be carried over to some extensions of those weak (...) theories by adding the fusion axiom schema. Most of the proofs to be presented in this paper take finite lattices as the base models when applying the refined method. However, I shall also point out the limitation of this kind of reduction and make some observations and conjectures concerning the decidability of stronger mereological theories. (shrink)

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 (...) with some intuitions underlying Wittgenstein’s philosophy of mathematics, such as its strict finitism and the insistence on the decidability of any mathematical question. (shrink)

Mereological theories are theories based on a binary predicate ‘being a part of’. It is believed that such a predicate must at least define a partial ordering. A mereological theory can be obtained by adding on top of the basic axioms of partial orderings some of the other axioms posited based on pertinent philosophical insights. Though mereological theories have aroused quite a few philosophers’ interest recently, not much has been said about their meta-logical properties. In this paper, I will look (...) into whether those theories are decidable or not. Besides, since theories of Boolean algebras are in some sense upper bounds of mereological theories which can be found in the literature, I shall also make some observations about the possibility of getting mereological theories beyond Boolean algebras. (shrink)

Full proofs of the Gödel incompleteness theorems are highly intricate affairs. Much of the intricacy lies in the details of setting up and checking the properties of a coding system representing the syntax of an object language (typically, that of arithmetic) within that same language. These details are seldom illuminating and tend to obscure the core of the argument. For this reason a number of efforts have been made to present the essentials of the proofs of Gödel’s theorems without getting (...) mired in syntactic or computational details. One of the most important of these efforts was made by Löb [8] in connection with his analysis of sentences asserting their own provability. Löb formulated three conditions (now known as the Hilbert-Bernays-Löb derivability conditions), on the provability predicate in a formal system which are jointly sufficient to yield the Gödel’s second incompleteness theorem for it. A key role in Löb’s analysis is played by (a special case of) what later became known as the diagonalization or fixed point property of formal systems, a property which had already, in essence, been exploited by Gödel in his original proofs of the incompleteness theorems. The fixed point property plays a central role in Lawvere’s [7] category-theoretic account of incompleteness phenomena (see also [10]). Incompleteness theorems have also been subjected to intensive investigation within the framework of modal logic (see, e.g.[4], [5]). In this formulation the modal operator takes up the role previously played by the provability predicate, and the derivability conditions on the latter are translated into algebraic conditions (the so-called GL, i.e., Gödel–Löb, conditions) on the former. My purpose here is to present a framework for incompleteness phenomena, fully compatible with intuitionistic or constructive principles, in which the idea of a coding system is retained, only in a 2 simple, but very general form, a form wholly free of syntactical notions. As codes we shall take the elements of an arbitrary given nonempty set, possibly, but not necessarily, the set of natural numbers.. (shrink)

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. (...) Cohen et al. (Eds.), Potentiality, Entanglement, and Passion-at-a-Distance: Quantum Mechanical Studies fo Abner Shimony, Vol. 2, Kluwer Academic Publishers, Great Britain, 1997, pp. 177–190]. Unlike some others in the literature, these notions apply not only to certain nice sets, but to general sets in Rn and other appropriate spaces. We consider some motivations for these concepts and the logical relations between them. It has been argued that d.m.z. is especially appropriate for physical applications, and on Rn with the standard measure, it is strictly stronger than r.a. [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]. Here we show that this is the only implication that holds among our three decidabilities in that setting. Under arbitrary measures, even this implication fails. Yet for intervals of non-zero length, and more generally, convex sets of non-zero measure, the three concepts are equivalent. (shrink)

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 (...) and Ott's (1996) claim of uncomputable behavior in a system with riddled basins of attraction. Furthermore, it clarifies speculations that the stability of the solar system (and similar systems) may be undecidable, for the invariant tori established by KAM theory form sets that are not d-. (shrink)

We consider a seemingly popular justification (we call it the Re-flexivity Defense) for the third derivability condition of the Hilbert-Bernays-Löb generalization of Godel's Second Incompleteness Theorem (G2). We argue that (i) in certain settings (rouglily, those where the representing theory of an arithmetization is allowed to be a proper subtheory of the represented theory), use of the Reflexivity Defense to justify the tliird condition induces a fourth condition, and that (ii) the justification of this fourth condition faces serious obstacles. We (...) conclude that, in the types of settings mentioned, the Reflexivity Defense does not justify the usual ‘reading’ of G2—namely, that the consistency of the represented theory is not provable in the representing theory. (shrink)

In the spatialized Prisoner's Dilemma, players compete against their immediate neighbors and adopt a neighbor's strategy should it prove locally superior. 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 (...) will an equilibrium of some small number of strategies emerge? Here it is shown, for finite configurations of Prisoner's Dilemma strategies embedded in a given infinite background, that such questions are formally undecidable: there is no algorithm or effective procedure which, given a specification of a finite configuration, will in all cases tell us whether that configuration will or will not result in progressive conquest by a single strategy when embedded in the given field. The proof introduces undecidability into decision theory in three steps: by (1) outlining a class of abstract machines with familiar undecidability results, by (2) modelling these machines within a particular family of cellular automata, carrying over undecidability results for these, and finally by (3) showing that spatial configurations of Prisoner's Dilemma strategies will take the form of such cellular automata. (shrink)

In this paper the modal operator "x is provable in Peano Arithmetic" is incorporated into first-order theories. A provability extension of a theory is defined. Presburger Arithmetic of addition, Skolem Arithmetic of multiplication, and some first order theories of partial consistency statements are shown to remain decidable after natural provability extensions. It is also shown that natural provability extensions of a decidable theory may be undecidable.

A proof is presented that a form of incompleteness in Quantum Mechanics follows directly from the use of unbounded operators. It is then shown that the problems that arise for such operators are not connected to the non- commutativity of many pairs of operators in Quantum Mechanics and hence are an additional source of incompleteness to that which allegedly flows from the..

Because formal systems of symbolic logic inherently express and represent the deductive inference model formal proofs to theorem consequences can be understood to represent sound deductive inference to true conclusions without any need for other representations such as model theory.