Seeking Clarification on Computability, Functional Graphs…
0 reactions
Seeking Clarification on Computability, Functional Graphs, and the Motivation for Automata Theory
I’ve recently begun studying the Theory of Computation (TOC) and have some foundational questions regarding the relationship between functions, algorithms, and formal models. I would appreciate some insight into the following:
1) Function Graphs vs. Computability: If we define a function f by its graph G = \{(a, b) \mid b = f(a)\}, the existence of an algorithm to compute f implies we can decide membership in G. If I take f(x) = x + 3 and test the tuple (1, 2), it is clearly not in the graph. Does the existence of tuples not in the graph impact the "computability" of the function itself, or is the algorithm's "failure" to find (1, 2) in the graph actually a successful decision?
2) The "Why" of TOC: Beyond the abstract math, what is the fundamental goal of proving whether a function is computable? Is it primarily to find the boundaries of what physical hardware can ever achieve?
3) Encoding and String Sets: My lecturer transitioned from talking about graphs of functions to "sets of strings." How is the membership problem of a tuple (a, b) in a graph formally mapped onto the membership problem of a string in a language L?
4)The Necessity of Automata: Why must we use abstract models (like Finite Automata or Turing Machines) to prove the existence of an algorithm rather than just using high-level pseudocode or existing programming languages?
#technology
source
I’ve recently begun studying the Theory of Computation (TOC) and have some foundational questions regarding the relationship between functions, algorithms, and formal models. I would appreciate some insight into the following:
1) Function Graphs vs. Computability: If we define a function f by its graph G = \{(a, b) \mid b = f(a)\}, the existence of an algorithm to compute f implies we can decide membership in G. If I take f(x) = x + 3 and test the tuple (1, 2), it is clearly not in the graph. Does the existence of tuples not in the graph impact the "computability" of the function itself, or is the algorithm's "failure" to find (1, 2) in the graph actually a successful decision?
2) The "Why" of TOC: Beyond the abstract math, what is the fundamental goal of proving whether a function is computable? Is it primarily to find the boundaries of what physical hardware can ever achieve?
3) Encoding and String Sets: My lecturer transitioned from talking about graphs of functions to "sets of strings." How is the membership problem of a tuple (a, b) in a graph formally mapped onto the membership problem of a string in a language L?
4)The Necessity of Automata: Why must we use abstract models (like Finite Automata or Turing Machines) to prove the existence of an algorithm rather than just using high-level pseudocode or existing programming languages?
#technology
source
| 1,000 mlx | |
| 3 | |
| 0 |