Apologies if the title is confusing, but I couldn’t think of better phrasing in short text.

Whenever we define / specify a certain automaton (such as a finite state machine or a turing machine) by defining all of its States, transition function, etc., this feels awfully similar to defining an algorithm. For example, I can define a machine that can tell if a number is divisible by 3. It is very similar to writing an algorithm and the steps to solving the problem.

Now I understand that the two aren’t exactly equivalent. But would it be incorrect to say that the specification of a machine is a type of algorithm, since we’re defining the steps it takes to solve a problem (how to respond to a specific state or input to solve a specific problem)?

You are viewing a single thread.
View all comments
12 points

Yes, that’s essencially the church-turing-thesis

https://en.wikipedia.org/wiki/Church–Turing_thesis

permalink
report
reply
5 points

That’s the only church I’ll trust

permalink
report
parent
reply

Programming

!programming@programming.dev

Create post

Welcome to the main community in programming.dev! Feel free to post anything relating to programming here!

Cross posting is strongly encouraged in the instance. If you feel your post or another person’s post makes sense in another community cross post into it.

Hope you enjoy the instance!

Rules

Rules

  • Follow the programming.dev instance rules
  • Keep content related to programming in some way
  • If you’re posting long videos try to add in some form of tldr for those who don’t want to watch videos

Wormhole

Follow the wormhole through a path of communities !webdev@programming.dev



Community stats

  • 3.1K

    Monthly active users

  • 1.8K

    Posts

  • 30K

    Comments