Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 20 for “"Turing Machines"”.
-
Turing machines, computers and artificial intelligence
… with current digital equipment. The Church -Turing thesis and the specific properties of Turing machines are examined and some of the philosophical 'in principle' objections, such as the application of Gödel's incompleteness theorem, are discussed. It is argued that the misinterpretation of …
-
Succinct Cryptography via Propositional Proofs
… indistinguishability obfuscation (IO) for Turing machines? In particular, can we construct an obfuscated program whose size is independent of the input length? • Can we construct succinct non-interactive arguments (SNARGs) for all of NP? While the problems seem unrelated at first glance, …
-
Remodeling Rationality: An Inquiry into Unorthodox Modes of Logic and Computation
… of mathematical logic from Brazil, nonbinary Turing machines from postcolonial India, and frameworks of information science from postrevolutionary Cuba. Part II analyzes contemporary developments in the field of artificial intelligence (AI), particularly attempts to incorporate ethics and …
-
Inverted theory networks
… systems and in particular, simulate universal Turing machines. The regulating priuciple of natural selection is formalised together with its necessary and sufficient conditions. It is proven that there exists inverted theory networks (an analogous construct to theory networks) that satisfy all …
-
Exploring Computational Models: Analysis, Extensions, and Novel Approaches in Automata Theory
… finite automata, pushdown automata, and Turing machines. Motivated by the trade-off between expressive power and structural simplicity, it introduces a novel model called Counter-Based Finite Automata (CBFA). The proposed model extends deterministic finite automata by incorporating …
-
A calculus for composable, computational cryptography
… computational model underlying UC—interactive Turing machines (ITMs)—by adapting ITMs to a subset of the π-calculus through an affine typing discipline. In other words, well-typed ILC programs are expressible as ITMs. In turn, ILC’s strong confluence property enables reasoning about …
-
Model-checking problems, machines and parameterized complexity
… <br>tractable algorithms of random access machines whose use of <br>nondeterminism is bounded in terms of the parameters. By <br>further tuning the nondeterminism that the random access machines can use, <br>say, allowing alternating, or restricting the access to <br>the guessed numbers, we …
-
Polycommit: Building Better Habits Through Gamification
<p>Computer-assisted learning is older than Turing machines, and constantly evolves as technology improves. While some teachers are resistant to using technology in the classroom, “e-learning” techniques are becoming more common in almost every school, from K-12 to universities. As technology …
-
Pattern synthesis and perturbation in tessellation automata
… assistance. Next, computational equivalence of Turing Machines and tessellation automata is demonstrated. This shows the powerful nature of tessellation automata. Following this, the existence of cyclic patterns with unique subpatterns is proven. These results are relied upon heavily for the …
-
A relatively small turing machine whose behavior is independent of set theory
… an explicit description of a 340,943-state Turing machine Z with 1 tape and a 2-symbol alphabet whose behavior cannot be proved in ZFC, assuming ZFC is consistent. The machine is based on work of Harvey Friedman on independent statements involving order-invariant graphs. Ill In doing so, I …
-
Transitive Closure Logic and Multihead Automata with Nested Pebbles
… that are decidable by some deterministic Turing machine using a logarithmic amount of memory space. An analogous result holds for transitive closure logic and nondeterministic Turing machines. This thesis concerns the k-ary fragments of these two logics. In each k-ary fragment, the arities …
-
The computational complexity of prefix classes of logical theories
… added unary predicates. By a direct coding of Turing machines we get that for $m\geq2$ the formulas in $\Pi\sb{m}$ have an $NSPACE$(exp$\sb{m}(d\sb{m}n$/log $n$)) lower bound. A careful analysis of a finite automata decision procedure for this theory gives that for $m\geq0$ the $\Sigma\sb{m+1}$ …
-
On instabilities and trust in deep learning
… discussions about AI’s potential to pass the Turing Test. Despite these successes, AI systems remain fragile, prone to hallucinations and adversarial examples, which expose the vulnerabilities in their decision-making processes. This thesis explores foundational issues in AI, particularly LLMs …
-
Constructions, Lower Bounds, and New Directions in Cryptography and Computational Complexity
… observe [Coo71] that logarithmic space-bounded Turing Machines, equipped with an unbounded stack, henceforth called Stack Machines, together with an external random tape of polynomial length characterize RP; BPP an so on. By parametrizing on the number of passes over the random tape we provide a …
-
Expressiveness of Concurrent Languages
… of computability strictly less expressive than Turing Machines. Namely, grammars of types 1,2 and 3 in the Chomsky Hierarchy. We then move to asynchronous languages and we study full abstraction for two Linda-like languages. Linda can be considered as the asynchronous version of CCS plus a …
-
ON THE FOUNDATIONS OF COMPUTABILITY THEORY
The principal motivation for this work is the observation that there are significant deficiencies in the foundations of conventional computability theory. This thesis examines the problems with conventional computability theory, including its failure to address discrepancies between theory and …
-
Designing visually rich mathmatical investing tools for repetitive geometric artifacts
… the importance of automata (and in one case 2D Turing Macliines) was demonstrated through the versatile and flexible use in each of the prototypes. The automata’s computation power was harnessed to describe the geometric artifacts and in some cases the automata’s expressive power was harnessed …
-
The complexity of joint computation
… models: query algorithms, circuits, and Turing machines. We significantly improve and extend past results on limits to efficient joint computation for multiple independent tasks; identify barriers to progress towards better circuit lower bounds for multiple-output operators; and begin an …
-
Teaching Formal Languages through Visualizations, Machine Simulations, Auto-Graded Exercises, and Programmed Instruction
The material taught in a Formal Languages course is mathematical in nature and requires students to practice proofs and algorithms to understand the content. Traditional Formal Languages textbooks are heavy on prose, and homework typically consists of solving many paper exercises. Some instructors …