Turing complete что это
Posted on 23 November 2021, by Kevin Mora
A Turing Complete system is one where a computer program can discover the solution (although, with no guarantees regarding runtime or memory).
Alan Turing created a machine able to take a program, run it, and show some result. In those days, Turing and other early computer scientists would have to build a specific machine each time they wanted to solve a specific problem (e.g., a colossal machine with the size of a car able to exclusively add numbers, nothing else). If by any chance you wanted to substract, multiply or divide integers, you’d have to create another colossal machine for each operation – machines with a single purpose, as opposed to now that we have a single machine that can be forever reprogrammed.
For that reason, he created the «Universal Turing Machine,» able to take any program and run it. Programming languages are similar to those machines (although virtual) – they take programs and run them. A programing language is called «Turing complete,» if it can run any program (irrespective of the language) that a Turing machine can given enough time and memory.
As an illustration, suppose there is a software that adds 10 numbers. This program can be easily run on a Turing machine, but assume that for some reason your programming language is unable to perform the same addition. As a result, it would be «Turing imperfect». On the other hand, if it is Turing complete if it can execute any program that the all-purpose Turing computer can execute.
Most modern programming languages are all Turing complete because they each implement all the features required to run programs like addition, multiplication, if-else conditions, return statements, ways to store/retrieve/erase data and so on. The purpose of this simplification is to make theory issues (like halting problems, complexity classes, and other issues that theoretical computer science is interested in) simple to think about. One specific advantage is that it is typically very simple to test whether a particular computer or language can simulate a Turing machine by simply programming the Turing machine in question in that language.
A Turing machine can take decisions based on what it sees in memory – the «language» that only supports +, -, *, and / on integers is not Turing complete because it can’t make a choice based on its input, but a Turing machine can. Therfore, these machines can run forever – if we took Java, C++, or Python and removed the ability to do any sort of loop, GOTO, or function call, it wouldn’t be Turing complete because it can’t perform an arbitrary computation that never finishes. A Turing computer can use infinite memory – take for instance Java; it has no limitations that prevent it from using infinite memory, and it is still a Turing complete language even though we are unable to construct a true Turing machine due to space limitations. That’s why regular expressions aren’t Turing complete.
A language that only allows you to access memory through push and pop operations to a stack wouldn’t be Turing complete because a Turing computer has random access memory. These machines can also mimic any other Turing machine; given the right «program,» a Turing machine can take the «program» of another Turing machine and simulate it using any input. It wouldn’t be Turing complete if a Python program couldn’t be implemented in a language. If you had a language that was forbidden from implementing a Python interpreter, it wouldn’t be Turing complete.
Keep in mind that neither time nor storage can ever be limitless; they are both unbounded. Every unique computable run will have a maximal value for them, but there is no upper bound on the size of that value. It is glossed over that a real computer will eventually run out of RAM; this is obviously a limit for any physical computer, but it is also clear and unrelated to the machine’s theoretical «computing capacity.» Additionally, we are not at all concerned with how long it truly takes. As a result, our tiny machine is completely impractical because it can utilize any quantity of time or space.
Therefore, a Turing machine is a device with infinite random access memory and a finite «program» that specifies when it should read, write, and move across that memory, when it should end with a specific outcome, and what it should do next.
There is some possibility that a black hole could be used as a computing device – an extremely fragile and dangerous one. The solution is read back as Hawking radiation after being encoded as infalling matter – a truly unrealistic and bizarre technique of universal computation.
Игра в раннем доступе
Приобретите игру и начните играть — примите участие в ее развитии
Примечание: данная игра в раннем доступе находится на стадии разработки. Она может измениться в будущем, а может остаться в текущем состоянии, так что, если вам не по вкусу то, что игра может предложить сейчас, рекомендуем дождаться её дальнейшего развития. Узнать больше
Почему ранний доступ?
“Player feedback is crucial for puzzle games. Each level starts with an idea I want the player to realize on their own, but it takes a lot of trial and error to figure out how to get the difficulty of each level right.
As for the sandbox part of the game, I also want to experiment with what set of tools lets players get most creative.”
Сколько примерно эта игра будет в раннем доступе?
Чем планируемая полная версия будет отличаться от версии в раннем доступе?
Каково текущее состояние версии в раннем доступе?
Изменится ли цена игры после выхода из раннего доступа?
Как вы планируете вовлекать сообщество в разработку игры?
Этот продукт не поддерживает ваш язык. Пожалуйста, перед покупкой ознакомьтесь со списком поддерживаемых языков.
Купить Turing Complete
Сообщайте об ошибках и оставляйте отзывы в обсуждениях этой игры
Об этой игре
-= LEARN =-
Everything in a computer can be constructed from a basic component called a NAND gate. You will be challenged through a series of puzzles, to discover the path from NAND gates to arithmetic, memory and all the way to full CPU architectures. If you complete this game, you will have a deep understanding of how assembly, CPU instruction sets and basic components are related. And you will understand how programming concepts like if statements, loops and functions actually work in assembly and hardware.
-= BUILD =-
The game is built on a powerful simulator, that gives you total freedom in how you solve levels or create your own computers. Wire up screens, timers, sound, keyboard input and network components to create whatever you want. You can even design a unique assembly language for your computer.
Turing complete что это
A lot of really hard work has gone into the next upcoming patch. It has taken a long time to get this one ready though (and it still isn’t done yet), so some new players are asking if the game is abandoned. It certainly isn’t!
Here is a quick preview of what is going on behind the scenes:
This update brings a verilog exporter to the game. Verilog is an industry standard hardware description language. With your favorite architecture exported to verilog format, you can theoretically simulate it with other simulators, simulate it on an FPGA (basically circuit simulation hardware) and presumably even get it produced as a chip if you can afford it. However if you are excited to try this out but don’t have experience with industry tools, be warned that they are far from as polished from an ease of use perspective, as games like this are. Things can be painful to set up sometimes.
In other news, here are some of the things that were added since last update:
— Added a "Ticks Per Second" counter
— Added UI scaling
— Improved multi select
— Enabled reordering of the left side IO list by drag and drop
— Added bidirectional pins and tri state pins to that IO list
— Deleted the Stack component, created a new version of the "Negative numbers" level and more small iterations like that.
— Also I fixed a ton of long standing bugs
At the moment I am working on improving the programming language that the levels of the game are defined in. Once its updated, players will be able to write and share their own levels / level packs (with full server verified scoring), which will be very exciting. This might take a while though and it is hard to predict exactly how long, since I want to try to do some things I don’t have much experience with. I will post more when I figure it out.
Color blind mode was finally added. The red "OFF" color is replaced by purple, since green / purple should be differentiable for all major forms of colorblindness. Also the purple is brighter so it can be distinguished from contrast as well. Color blind mode can be enabled it in the options menu.
If you have colorblindness, let me know how well it works!
Check out the schematic hub, it is finally live and there are already a few really cool things uploaded.
Players who have 10 total upvotes or more between all their uploads on the 10th of August will get a badge on their profile.
It is finally time to add the feature that I have earlier referred to as "sharing". This will be in the form of an in game interface called the Schematics Hub, where players will be able to upload architectures or custom components and explore what others have uploaded. Players will be able to upvote, downvote or comment on other architectures and custom components.
You can expect this update within 1 or 2 weeks. After it has released, there will be a limited time opportunity to earn a new badge, more about that here:
I originally announced that I would be working on this new feature a couple of months ago, but the preparations for it ended up taking a long time. Specifically, I wanted to make an effort not to break shared schematics, so I ended up spending a lot of time agonizing over the details of many of the components. As an example of how far in the weeds I went to try and get everything right, I ended up creating a custom font (with the help of some community members) for the console, so that I wont have to break ascii art in the future. The most time consuming components to get right were the network component, the console and the different RAM options, which ended up taking about one or two weeks each. They were time consuming, not because their implementations were difficult, but because I learned something new after each implementation that made me want to revisit how they worked.
In any case, I can’t 100% guarantee that I wont break working schematics from when the Schematics Hub goes live, but I do feel fairly optimistic about it.
Turing Complete now has a new synthwave soundtrack. As with all music, not everyone is going to like it but I personally can’t stop listening to it!
You can also find it on Spotify:
https://open.spotify.com/album/1NV5KxX785RrwA5RWIz0j8?si=LlUK4wveTpaMeBT9Mh8r1g
Progress towards sharing
Meanwhile work towards in-game sharing is continuing. Mostly I have been tying up loose ends (like translation) and trying to get to a stable set of components in the game. The goal is to get components stable enough so that shared schematics will never have to be broken by a new update. After finishing these things, actually adding the sharing functionality shouldn’t take too long. You can expect more news about this within a few weeks.
The following was done since the realism patch 3 weeks ago:
— Fixed levels, scores, achievements and other things that were broken as a result of the realism patch.
— 16 bit and 32 bit components were introduced, as well as a 2 bit decoder and word sized NAND, NOR and XNOR.
— The component menu was reworked which was needed to accommodate all the new components. Custom components in the menu are now nested according to the players save folder structure.
— The old 64 bit RAM was replaced by 3 new RAM components, which all have their cost scale with their configurable size. The first RAM has a high gate cost, the second has a high delay cost. The third has a high delay cost, but its delay is amortized over several ticks. This means it effectually adds very little delay to the circuit, making it cheap in both gates and delay, but reading from it takes several ticks to complete. In future levels, more advanced score optimizing builds will likely use a slow cheap RAM for main memory, but cache results with a smaller fast RAM. All 3 RAM components have configurable size and word width.
— ROM was added. This component can only be written to in the sandbox, but its memory is not reset on level change or reset. It can be used for lookup tables in scored levels (where you cannot write to it). For creative builds that don’t care about scored levels, this component can also be used as a hard disk in the sandbox. Like the RAM, the ROM component has configurable size and word width.
For a while now I have been working on removing some of the common critiques people had regarding the realism of the game. The main changes have been adding latches and the big change you can watch explained in this video.
It is in a video format, because I wanted to explain the changes thoroughly and I fear the blog post would have been too long.
Because I wanted to announce this large change properly and not have players guess it ahead of time, I wasn’t able to really let players know I was working towards this goal of realism and why. But since the cat is now out of the bag, I am excited to once again be able to share the short term roadmap for the game.
With this change, the realism modifications I wanted to make are pretty much done (there may or may not be an option for having an explicit clock at some point, but this would not affect scoring and might be better suited for user generated levels). The next goal is to finally implement in-game sharing. I imagine 3 types of sharing.
1. Architectures: These would be fully fledged machines you can download to your own computer. I imagine this being useful for fantasy game consoles, real world architectures or community architectures. Other players will then be able to share programs for each architecture. So user A can make a game for the fantasy console of user B and so on.
2. Demos: Read only schematics for neat stand alone programs, like the game of life, a mandelbrot explorer or games.
3. Custom components: A way to share custom components or packs of custom components.
All this would take place through in-game UI and there would be upvotes / downvotes and comments. The magic internet points earned by player uploads will be visible on their profile (but you can’t get downvoted below 0, so no need to worry about losing points).
In order to get this far though, there is a bunch of stuff I want to do first.
First of all, I want to tie up some loose ends. I need to actually implement the change mentioned in the above video, then fix a bunch of small UI glitches and quality of life issues and I want to finish translation support.
Secondly, I want to get to a stable point in terms of the basic components supported in the game. My opinions of many of these things have stabilized I think and I would like to make an honest attempt at never having to break things that have been committed to the sharing platform. So first I will add a lot of missing sandbox components, like more kinds of RAM, displays, networking and sound. The way the players should interact with these things will take some time to settle, so I will prioritize adding this first. I used to think that I should give players as much power as possible, but my opinion has been refined a bit. Providing players with finished building blocks for everything is like giving players the most powerful weapons in a first person shooter game. It makes them feel powerful but removes a lot of gameplay and fun. Instead I should provide players low level control of the IO of their computer, so they can build anything they want. I also want to have just one easy to understand way to do things and it is OK if it means it takes a bit of work to do common things, as long as it is not extremely tedious. This is also why the Random component was removed.
While we experiment with the sandbox components and give their interface some time to settle, I will add 16 and 32 bit variants of the 64 bit components. I like simplicity and you can use the 64 bit components for 16 or 32 bit operations, by simply ignoring the high bits (for all components except signed less). Further there is a neat symmetry of the byte maker taking 8 bits to produce a byte, while the 64 bit maker takes 8 bytes. However, actually watching a stream of someone building a 16 bit computer it became clear that it is a bit awkward and it just doesn’t feel right. I can’t see myself ever supporting odd bit widths, since for speed I want all components to map to a single x86 or ARM instruction as much as possible. If you want to build a 107 bit computer, you can still do it, but simple schematics should reduce to simple machine code and if you are doing something complicated, it should be obvious from your schematic.
To support all these new components I will also have to upgrade the component menu, so it doesn’t become completely cluttered.
Finally I want to mention that I had originally planned to bring back the old architecture scoring "perf score" system around this time, but thinking about it more, saving this effort in order to get to user generated levels faster is the better plan. User levels is the most important missing feature (although it will take much work) and users will likely create a better architecture scoring systems than I could.
What is Turing Complete?
Can you give a simple explanation, without going into too many theoretical details?
14 Answers 14
Here’s the briefest explanation:
A Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory).
So, if somebody says "my new thing is Turing Complete" that means in principle (although often not in practice) it could be used to solve any computation problem.
Sometimes it’s a joke. a guy wrote a Turing Machine simulator in vi, so it’s possible to say that vi is the only computational engine ever needed in the world.
Here is the simplest explanation
Alan Turing created a machine that can take a program, run that program, and show some result. But then he had to create different machines for different programs. So he created "Universal Turing Machine" that can take ANY program and run it.
Programming languages are similar to those machines (although virtual). They take programs and run them. Now, a programing language is called "Turing complete", if it can run any program (irrespective of the language) that a Turing machine can run given enough time and memory.
For example: Let’s say there is a program that takes 10 numbers and adds them. A Turing machine can easily run this program. But now imagine that for some reason your programming language can’t perform the same addition. This would make it "Turing incomplete" (so to speak). On the other hand, if it can run any program that the universal Turing machine can run, then it’s Turing complete.
Most modern programming languages (e.g. Java, JavaScript, Perl, etc.) are all Turing complete because they each implement all the features required to run programs like addition, multiplication, if-else condition, return statements, ways to store/retrieve/erase data and so on.
Informal Definition
A Turing complete language is one that can perform any computation. The Church-Turing Thesis states that any performable computation can be done by a Turing machine. A Turing machine is a machine with infinite random access memory and a finite ‘program’ that dictates when it should read, write, and move across that memory, when it should terminate with a certain result, and what it should do next. The input to a Turing machine is put in its memory before it starts.
Things that can make a language NOT Turing complete
A Turing machine can make decisions based on what it sees in memory — The ‘language’ that only supports + , — , * , and / on integers is not Turing complete because it can’t make a choice based on its input, but a Turing machine can.
A Turing machine can run forever — If we took Java, Javascript, or Python and removed the ability to do any sort of loop, GOTO, or function call, it wouldn’t be Turing complete because it can’t perform an arbitrary computation that never finishes. Coq is a theorem prover that can’t express programs that don’t terminate, so it’s not Turing complete.
A Turing machine can use infinite memory — A language that was exactly like Java but would terminate once it used more than 4 Gigabytes of memory wouldn’t be Turing complete, because a Turing machine can use infinite memory. This is why we can’t actually build a Turing machine, but Java is still a Turing complete language because the Java language has no restriction preventing it from using infinite memory. This is one reason regular expressions aren’t Turing complete.
A Turing machine has random access memory — A language that only lets you work with memory through push and pop operations to a stack wouldn’t be Turing complete. If I have a ‘language’ that reads a string once and can only use memory by pushing and popping from a stack, it can tell me whether every ( in the string has its own ) later on by pushing when it sees ( and popping when it sees ) . However, it can’t tell me if every ( has its own ) later on and every [ has its own ] later on (note that ([)] meets this criteria but ([]] does not). A Turing machine can use its random access memory to track () ‘s and [] ‘s separately, but this language with only a stack cannot.
A Turing machine can simulate any other Turing machine — A Turing machine, when given an appropriate ‘program’, can take another Turing machine’s ‘program’ and simulate it on arbitrary input. If you had a language that was forbidden from implementing a Python interpreter, it wouldn’t be Turing complete.
Examples of Turing complete languages
If your language has infinite random access memory, conditional execution, and some form of repeated execution, it’s probably Turing complete. There are more exotic systems that can still achieve everything a Turing machine can, which makes them Turing complete too: